Эффективный алгоритм подсчета уникальных состояний крестиков

Question

Я пытаюсь создать игру «крестики-нолики», чтобы продемонстрировать и поэкспериментировать с алгоритмами машинного обучения, и обнаружил интересную проблему.

Например: доска Tic Tac Toe может быть зеркальной , но для целей машинного обучения оба эти состояния эквивалентны

x _ o     o _ x
o o x  =  x o o
_ _ _     _ _ _

аналогично вращений

x _ o   _ _ x   _ _ _   o _ _
_ _ _ = _ _ _ = _ _ _ = _ _ _ 
_ _ _   _ _ o   o _ x   x _ _

наконец, сопоставления

x _ o   o _ x
_ x _ = _ o _
_ _ x   _ _ o

Каков наилучший способ определить / посчитать уникальные состояния для крестиков?

Есть ли область изучения или математика, на которую я должен обратить внимание?

Answer 1

Math

Хитрость заключается в использовании теоремы перечисления Polyas:

http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem

Игнорируя дубликаты, существует 9 квадратов из 3 состояний (x, o и-), так что есть 3 ^ 9 = 19683 конфигурации.Вам необходимо определить группу, которая обеспечивает действия на доске.Для вашей проблемы диэдральная группа D4, кажется, работает для всего, кроме сопоставления.Но сопоставление легко, так как есть 2, когда это не доска, полная не заботится (все -, начальная конфигурация).

Вычисление

В то время как математика позволяет нам считатьконфигурации, это не помогает идентифицировать их.Возможно, самое простое решение - определить доску как кортеж: {p1, p2, p3, ..., p9}, где каждый pn равен {0,1,2}.Требуется 2 бита на квадрат, и их 9, всего 18 бит.Таким образом, доска может быть представлена ​​32-битным целым числом или менее.

Индексирование по платам легко выполняется с помощью хеш-таблицы.Есть только 19000 конфигураций, так что нас это не убьет.

Выполнение всех конфигураций платы лучше всего выполнить по арифметике radix-3 из 9-ти выше: {0,0,9,..., 0}, {0,0,0, ..., 1}, {0,0,0, ..., 1,0} и так далее.Это просто дополнение с переносом.Это генерирует все доски.Обратите внимание, как групповое действие и сопоставление преобразуют такое число.Возможностей ограничено (juxta смещает x на o и наоборот, остальные перемещаются по позициям на доске в соответствии с группой D4. Существует 8 таких преобразований.) Вы можете использовать Polya, чтобы убедиться, что ваш алгоритм получил их все.

Как и предполагалось, выбор самого маленького парня из набора является уникальным представителем конфигурации по модулю действий.

Answer 2

Я не знаю правильного математического способа, но я бы сделал это так. Придумайте способ преобразования любого состояния в одно число. Например, присвойте пустое поле нулю, O - 1, X - 2 и обработайте 9 цифр как число в системе base-3. Теперь преобразуйте это состояние во все 7 оставшихся зеркальных состояний. Подсчитайте их числа тоже. Выберите наименьшее из этих 8 чисел. Вот и все.

Answer 3

Объединение некоторых идей из других ответов ...

Не отображать конфигурации в числа.Используйте числа для представления конфигураций.Напишите методы для работы с представлением, если вам действительно нужно получить / установить координаты x, y.

Затем выберите представление, с которым вы можете эффективно работать, чтобы ответить на вопрос.Вот одна идея.

У вас есть три операции, поэтому давайте дадим им названия:

• R = повернуть доску на 90 градусов против часовой стрелки
• M = зеркальная доскао оси y
• I = доска инвертирования (то, что вы называете «сопоставить», но я думаю, что «инвертировать» более наглядно)

Вы хотите посчитать количество классов эквивалентностидосок под орбитой этих операций.В каждом классе эквивалентности не более 16 элементов.Имея плату, вы можете сгенерировать другие 15 эквивалентных плат, применив операции в следующей последовательности:

R, R, R, I, R, R, R, M, R, R, R, I, R, R, R

(есть и другие последовательности, которые тоже работают ...)

Так что хорошей идеей было бы выбрать представление, которое делает R быстрым, я несколько быстрым,и не слишком беспокоиться о M.

Поскольку R не меняет центр, я бы держал его где-то еще и использовал бы последовательность 2-битных чисел для представления остальных 8 квадратов.Я хотел бы, чтобы первое 2-разрядное число представляло нижний левый, следующее 2-разрядное число представляло квадрат рядом с ним, и так далее, перемещаясь против часовой стрелки вокруг доски.Я хотел бы, чтобы 00 представлял "O", 11 представлял "X", и оба 01 и 10 представляли "пустое" (потому что тогда операция I становится простым переключением битов).

Тогдаесли вы запишите эти 8 2-битных чисел как одно 16-битное число, операция R будет просто операцией поворота 16-битного числа, которую ваш ЦП может, вероятно, выполнить в одной инструкции.Операция I - это просто XOR с -1 (но не забудьте также инвертировать центральный квадрат).Операция M - сложная куча манипуляций с битами, но так как вы делаете это только один раз из 15, кого это волнует?

Это должно позволить вам принять любое представление и быстро сгенерировать остальные 15, которые эквивалентны.Затем, как предлагает Диалектик, выберите наименьшее по численности представление в качестве своего канонического члена класса эквивалентности и сосчитайте их.

Answer 4

Если вы заботитесь только об оптимальных ходах:

См. Эту систематическую карту оптимальных движений крестики-нолики (http://xkcd.com/832/).). Вы можете использовать некоторые (столбцы, строки) индексации для идентификации определенного состояния.

Если существует более одного эквивалентного состояния, используйте «самый низкий» индекс (вы должны определить, что означает «самый низкий»; например, та пара (столбец, строка), значение которой 3 * столбец + строка наименьший) из всех эквивалентных из них.

Answer 5

Крестики-нолики связаны с искусственным интеллектом, в частности, с алгоритмом minmax из теории игр, а точнее с AB Pruning для достижения хороших результатов. Вся тема огромна, но проста и процедурна. Это легко понять, и вы можете начать на следующих страницах:

http://en.wikipedia.org/wiki/Game_theory

http://www.cs.trincoll.edu/~ram/cpsc352/notes/minimax.html

Что-то ясное и простое, чем приведенная выше ссылка:

http://www.cs.ucla.edu/~rosen/161/notes/alphabeta.html

Answer 6

Я думаю, что теория графов хороша для этого, у вас будет пример с 9 вершинами для примера, который вы привели. Единственное, что все еще может быть проблемой, - это сопоставление.