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

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

например: плата 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

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

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

Ответ 1

Math

Фокус в том, чтобы использовать теорему перечисления Поляса:

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

Игнорируя дубликаты, существует 9 квадратов из трех состояний (x, o и -), поэтому существуют конфигурации 3 ^ 9 = 19683. Вам необходимо определить группу, которая обеспечивает действия на плате. Для вашей проблемы Dihedral Group 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, чтобы убедиться, что ваш алгоритм получил их все.

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

Сочетание некоторых идей из других ответов...

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

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

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

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

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

<p> 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 представляли "пусто" (потому что тогда операция я становится простым переворачиванием бит).

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

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

Ответ 5

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

Ответ 6

Tic tac toe связан с AI, в частности алгоритмом 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