Искусственный интеллект для логической игры

Доброго времени суток!
Правила игры "Так-тикль":
1. Играют двое, один за крестики, другой за нолики.
2. Исходное поле 4х4:

XOXO


OXOX

3. Игроки по очереди делают ход (влево, вправо, вверх, вниз)
4. Выигрывает тот, кто быстрее составит ряд хотябы из трех своих фишек. Считаются ряды по горизонтали, вертикали и диагоналям.

Суть в том, чтобы написать алгоритм выбора оптимального хода компьютером. В журнале "Наука и Жизнь" 1977 №1 есть небольшая статья про игру, там сказано, что при оптимальных ходах обоих участников, игра будет продолжаться бесконечно.
Я перебираю все возможные варианты поля на 7-8 ходов вперед. Если представить себе все это дело в виде дерева, то листы -- это либо поле с выигрышной комбинацией, либо поле, для которого дальнейшие ходы не посчитаны (ограничение глубины рекурсии). Как по такому дереву можно определить оптимальный ход?

Заранее благодарен.
Извините за глупые вопросы.
Sbtrn. Devil Постоялец www 19 мая 2010 21:57 #1
Интуиция подсказывает следующее:

1) для текущего состояния посчитать минимальное расстояние до вражеской победы X (найти листок с вражеской победой с минимальной глубиной, X = его расстояние от текущего состояния) и до нашей победы Y (аналогично),
2) аналогично посчитать X и Y для состояний после нашего хода (соседних),
3) если для текущего состояния X>Y или X не определён (нет листков с вражеской победой), то выбрать ближайший листок с нашей победой и сделать ход по его ветке (ход на приближение к победе),
4) иначе: если для текущего состояния X<=Y или Y не определён (нет листков с нашей победой), то выбрать из соседних состояний то, у которого самый большой X (ход на отдаление от поражения).
5) если же не определён ни X, ни Y, то без разницы, куда ходить.

Если у нас 3), и есть несколько соседних листков с одинаковым Y, выбрать из них тот, у которого максимальный X (при наличии нескольких ходов, равноприближающих к победе, выбираем тот, который больше отдаляет от поражения).
Если у нас 4), и есть несколько соседних листков с одинаковым X, выбрать из них тот, у которого минимальный Y (при наличии нескольких ходов, равноудаляющих от поражения, выбираем тот, который больше приближает к победе).
Если же есть несколько листков с одинаково максимальными X и минимальными Y, выбрать из них любой.
Arturchik Пользователь www 19 мая 2010 23:54 #2
Sbtrn. Devil
Спасибо за ответ.
Одинакого у нас интуиция работает =)
Данный метод дает сбой в такой ситуации ( E - пустые клетки ):

E E X E
E E O E
O X E O
X O X E

ходят крестиками ( третья сверху фишка во втором столбце вправо ):

E E X E
E E O E
O E Х O
X O X E

Ходят они так из соображений, что нолики уберут свою фишку из третьего столбца, что приведет к скорой победе крестиков. Именно так сработает алгоритм, т.к. для крестиков это ближайшая достижимая победа.
Нолики, ( считаем, что они не дураки ) ходят третьей сверху фишкой первого столбца вправо:

E E X E
E E O E
E O Х O
X O X E

И вот крестики в тупике, как бы они не ходили, победа следующим ходом за ноликами.

В ответ на данную тупость можно предложить следующую идею: найдем варианты, когда при любом моем ходе, победа противника наступит по-любому ( меня загнали в угол ) и будем стараться избегать ходов, которые ведут к этим ситуациям. Самая большая тут проблема в том, что ближайшая победа -- весьма неточная оценка, т.к. противник не достаточно туп, чтоб допустить мою эту самую ближайшую победу.

Правка: 19 мая 2010 23:55
Monstradamus Постоялец www 20 мая 2010 4:21 #3
Минимаксный метод и альфа-бета отсечения курить нужно, как я понимаю.
Sbtrn. Devil Постоялец www 20 мая 2010 11:44 #4
Arturchik
> Ходят они так из соображений, что нолики уберут свою фишку из третьего столбца,
> что приведет к скорой победе крестиков. Именно так сработает алгоритм, т.к. для
> крестиков это ближайшая достижимая победа.
> Нолики, ( считаем, что они не дураки ) ходят третьей сверху фишкой первого
> столбца вправо:

> И вот крестики в тупике, как бы они не ходили, победа следующим ходом за
> ноликами.

Но при таком раскладе "расстояние до поражения" и "расстояние до победы" должны быть одинаковыми (по 3), и в действие вступил бы пункт 4) (про отдаление от поражения). Или не?
Arturchik Пользователь www 21 мая 2010 11:56 #5
Sbtrn. Devil
При таком раскладе получается, что ранооцененные ходы:
1. ходить вверх крестиком вторго столбца, третий сверху
2. ходить им же вправо
3. ходить вверх крестиком третьего столбца, четвертый сверху
4. ходить им же вправо

во всех этих вариантах считается, что самая близкая победа наступит после "правильного" (выгодного крестикам) хода ноликов, а у ноликов, во всех вариантах, победа дальше на один ход.
Sbtrn. Devil Постоялец www 21 мая 2010 12:19 #6
Гм. Ну тогда, действительно, остаётся ходить только по веткам, по которым меньше поражений (или столько же, но они дальше), и только при отсутствии поражений в поддереве следующего хода искать ход на победу.
Как ещё вариант, ходить на победу, если ближайшее поражение дальше ближайшей победы не менее, чем на 2-3-4 хода, и веток с поражениями в этом поддереве меньше, чем веток без них - тогда можно будет успеть сориентироваться на следующем ходу.
Arturchik Пользователь www 21 мая 2010 16:20 #7
Может быть, стоит идти не к просто победам, а к победам, как в примере победа ноликов, потому как обычная победа слишком наивная и в этом вся проблема.
Sbtrn. Devil Постоялец www 21 мая 2010 22:39 #8
Если попадётся поддерево, заканчивающееся победами, то, конечно, логично двигаться к нему. Но часто ли оно такое бывает?
Arturchik Пользователь www 22 мая 2010 9:06 #9
нет, такое бывает крайне редко
Sbtrn. Devil Постоялец www 22 мая 2010 12:35 #10
Тогда остаётся ходить на избежание поражения и на победу только в том случае, если она лежит в поддереве, где меньше поражений.
Arturchik Пользователь www 23 мая 2010 23:23 #11
Это все тоже не прокатывает. Ладно, спасибо большое всем за помощь, сделал кое-как через одно место.