Крестики-нолики: оптимальная стратегия

[_Ivana]

Думал, куда поместить тему - сюда или в программирование, решил сюда, ибо задачу можно рассматривать в отрыве от собственно программирования, и здесь больше людей могут заинтересоваться и подсказать. Итак, детская игра крестики-нолики 3*3. Хочется формализовать оптимальную стратегию (выбор хода при любом состоянии поля на входе), при этом чтобы она была по возможности наименее громоздкая. Пока придумал кустарщину вроде:
1) если можем закончить победой (есть 2 моих символа в каком-то ряду и третий свободный) - заканчиваем, иначе
2) если соперник может закончить - не даем ему это (занимаем клетку), иначе
3) если можем поставить "вилку" 2*2 - ставим, иначе
4) если соперник может поставить такую вилку - мешаем, иначе
5) если не занят центр - занимаем, иначе
6) если не занят угол - занимаем.
У меня сомнения в переходе к пунктам 5 и 6, да и вообще, весь алгоритм не производит впечатление стройного и аккуратного. Что посоветуете?

[Xaositect]

Первым ходом центр занимать невыгодно.
http://xkcd.com/832/

[_Ivana]

Пытаюсь разобраться в Вашей ссылке. А насчет первого хода - я как-то настолько считал этот вопрос очевидным, что даже не задумывался глубоко. Плюс, другая кустарная стратегия - максимизировать разность количества потенциально закрываемых направлений моих и соперника предлагает первым ходом центр, как дающий 4 направления мне и 0 сопернику. Но подозреваю, что эта кустарщина тоже неоптимальна...

[Aritaborian]

_Ivana, зачем кустарщина, если оптимальная стратегия давно известна. Помнится, у Гарднера о ней читал.

[_Ivana]

Aritaborian, да думал вопрос простой - сам за 10 минут придумаю, а не получилось. Я подозревал, что уже все придумано, но мне кажется что в таком малом диапазоне, как 3*3, можно реализовать функционал оптимальной стратегии простыми и лаконичными средствами.

(Оффтоп)

книжка Гарднера "Математические головоломки" была в детстве и юности на полке, тогда не открывал, а теперь придется искать в инете...

[Утундрий]

Алгоритмъ:
1) Перебрать все варианты и составить граф непроигрышных ходов (занятие на вечер).
2) Играть поглядывая в результат пункта 1.

[Nikolai Moskvitin]

я тоже думал на эту тему...как-то доказывал с помощью принципа Дирихле, какие могут существовать конфигурации. Например, доказывал, что в обычных «X-O» при ничье обязательно будет по паре соседних знаков (и «X», и «O»)-если считать, что заполняются все 9 клеток.
Если смогу и заинтересует, дам ссылку.

[_Ivana]

Утундрий, то есть, Вы предлагаете считать соперника максимально умным и не надеяться на выигрыш (независимо от того, кто начал ходить), а считать за счастье свести игру вничью, даже упуская при этом возможные подаренные соперником гарантированные выигрыши?
В таком случае проще запомнить таблицу исходных позиций (благо есть осевая симметрия) и наилучших ходов при них? Может для поля 3*3 это и будет оптимальным способом написания программы?

Nikolai Moskvitin давайте, почитаю.

[Null]

Xaositect в сообщении #707848 писал(а):

Первым ходом центр занимать невыгодно.
http://xkcd.com/832/

Я правильно понял таблицу? У них при правильной игре ничья?

[Утундрий]

_Ivana в сообщении #707881 писал(а):

считать соперника максимально умным и не надеяться на выигрыш (независимо от того, кто начал ходить), а считать за счастье свести игру вничью

Конечно.

_Ivana в сообщении #707881 писал(а):

даже упуская при этом возможные подаренные соперником гарантированные выигрыши?

А вот этого не требуется. Как только ход противника выведет его за пределы нашей диаграммки, это однозначный сигнал к добиванию.

[Xaositect]

Null в сообщении #707882 писал(а):

Я правильно понял таблицу? У них при правильной игре ничья?

При правильной игре ничья, да.

[_Ivana]

Кажется начинаю понимать. То есть, если мы хором идем к ничьей по моему графу, то и идти по нему, а если соперник делает ход вне графа - тогда добивать. Но вообще-то надо ещё грамотно добить - например, догадаться и суметь поставить вилку 2*2, если после моего первого хода в центр соперник сходил не в угол. А для правильных стратегий добития тоже нужен свой граф или алгоритм.

[arseniiv]

А что за вилка $2\times2$? Мне часто попадались вилки из двух углов одной стороны и центра, на $2\times2$ не похоже.

_Ivana в сообщении #707891 писал(а):

То есть, если мы хором идем к ничьей по моему графу, то и идти по нему, а если соперник делает ход вне графа - тогда добивать. Но вообще-то надо ещё грамотно добить

Весь граф игры не такой уж и большой, чтобы иметь его с собой. Тогда всегда ясно, как ходить.

[_Ivana]

arseniiv, это просто моя наколенная терминология. Например, я играю крестиками, вы ноликами:
я - центр
вы - нижняя середина
я - нижний левый угол
вы - верхний правый угол (иначе я выиграю следующим ходом)
я - левая середина (получаем вилку 2*2 - по 2 незакрытых крестика в 2 направлениях)

ЗЫ наверное вы правы, проще забить вручную весь граф игры... или мою таблицу ходов по исходным позициям с учетом симметрии... А саму таблицу или граф рассчитать для алгоритма вручную. Но я хотел чтобы компьютер не "втупую" играл по карте, а "думал по стратегии", мне это надо в целях демонстрации и обучения сына (Я вообще задал ему написать генератор ходов, сказав что я в свою очередь напишу свой и мы потом запустим 1000 игр между ними А потом мы внедрим в них управляемый процент глупости - уровень сложности игрока)

[Aritaborian]

Я, возможно, туплю и думаю не в ту сторону, но ведь существует же — и давно — оптимальная стратегия для этой игры. Она даже описывается какой-то просто запоминающейся мнемоникой. К сожалению, не помню, где об этом читал. Пролистал книгу Гарднера «Крестики-нолики», гл. 9, но там об этом ничего нет. Значит, в другой его книге...