Алгоритм определения игры Tic Tac Toe закончен - PullRequest
Новая
       40

Алгоритм определения игры Tic Tac Toe закончен

85 голосов
/ 29 июня 2009

Я написал игру в крестики-нолики на Java, и мой текущий метод определения конца игры учитывает следующие возможные сценарии игры:

  1. Доска заполнена, а победитель пока не объявлен: игра - ничья.
  2. Крест выиграл.
  3. Круг победил.

К сожалению, для этого он считывает предварительно определенный набор этих сценариев из таблицы. Это не обязательно плохо, если учесть, что на доске всего 9 мест, и, следовательно, таблица немного мала, но есть ли лучший алгоритмический способ определить, закончена ли игра? Определение того, выиграл кто-то или нет, является основной проблемой, так как проверка, заполнены ли 9 пробелов, тривиальна.

Табличный метод может быть решением, но если нет, то что? Кроме того, что если бы плата не была размером n=9? Что если бы это была намного большая доска, скажем, n=16, n=25 и т. Д., В результате чего количество последовательно размещенных предметов для выигрыша составляло x=4, x=5 и т. Д.? Общий алгоритм для использования для всех n = { 9, 16, 25, 36 ... }?

Ответы [ 21 ]

0 голосов
/ 07 июля 2013

Другой вариант: создать таблицу с кодом. До симметрии, есть только три способа выиграть: крайний ряд, средний ряд или диагональ. Возьми эти три и разверни их всеми возможными способами: 

def spin(g): return set([g, turn(g), turn(turn(g)), turn(turn(turn(g)))])
def turn(g): return tuple(tuple(g[y][x] for y in (0,1,2)) for x in (2,1,0))

X,s = 'X.'
XXX = X, X, X
sss = s, s, s

ways_to_win = (  spin((XXX, sss, sss))
               | spin((sss, XXX, sss))
               | spin(((X,s,s),
                       (s,X,s),
                       (s,s,X))))

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

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

Страница:
...