Хорошее минимаксное представление в Гомоку?

Question

Я пытаюсь закодировать игру Gomoku (пять в ряд) на Java как отдельный проект. Что касается ИИ, я понимаю, что использование минимаксной функции с отсечкой альфа-бета - хороший способ приблизиться к этому. Тем не менее, я немного затрудняюсь представить, как это будет работать.

Мой вопрос заключается в следующем: что такое хорошее представление для узла в минимаксном дереве?

Я думаю, что моя функция оценки будет "весить" все пустые места на доске. Затем он примет лучшее значение от этой платы в качестве узла дерева решений minmax. Я в правильном направлении?

И любые другие советы также приветствуются! Заранее спасибо!

Answer 1

Поиск в пространстве состояний осуществляется через различные состояния платы. Есть много ходов, так как вы можете поместить камень в любом месте, где нет места. Каждое состояние может быть представлено, например, в виде матрицы 9x9 с 3 значениями - белым, черным или незанятым. Таким образом, при использовании платы 9x9 существует 3 ^ 81 возможных состояний платы.

Из любого состояния доски количество ходов - это количество незанятых вершин. Вы можете поместить камень в любую из этих вершин. Вы можете играть только своим цветом. Таким образом, самое большее 81 возможный ход. 81 за первый ход, 80 за второй и так далее. Таким образом, вы можете искать до глубины 5 разумно, и, возможно, больше.. не так уж плохо.

Как уже упоминалось, правильное представление - это двумерная матрица - это может быть просто двумерный массив целых чисел со значениями, например, 0 для незанятых, 1 для белых, 2 для черных. ... int[9,9].

Ваша функция оценки звучит не очень хорошо. Вместо этого я бы дал очки за следующее:

- получить 5 подряд - в основном, дать ему максимальный счет за этот, так как это выигрыш - 4 подряд с 2 открытыми концами - также максимальный счет, так как противник не может заблокировать вас от получения 5. - 4 в ряд с 1 открытым концом - все еще очень угрожающая позиция, так как противник должен играть в одном месте, чтобы блокировать. - 3 в ряд с 2 открытыми концами - снова очень высокий счет --- 4, 3, 2, 1 с обоими закрытыми концами - 0, так как никогда не может сделать 5 подряд.

и так далее.

Затем вы просто применяете стандартный минимаксный алгоритм - т.е. альфа-бета-обрезку - он будет точно таким же, как шахматы, но у вас есть другой генератор пространства состояний и функция оценки.

Answer 2

Я бы рассмотрел функцию оценки в следующей форме: рассмотрим каждый набор, скажем, 6 позиций в строке. (На доске 19x19 по 14 на каждой линии и от 0 до 14 по каждой диагонали; я думаю, что на всей доске их будет 742. Моя арифметика может быть неправильной.) Для каждого сета есть 729 возможных расстановок черного, белого и пустого пространства. Или 378, если принять во внимание сквозную симметрию. Или, ну, меньше этого, но я не могу потрудиться выяснить, сколько их меньше, если принять во внимание также черно-белую симметрию.

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

Может оказаться, что на самом деле большая таблица (полученная из более длинного ряда позиций) работает лучше.

Но что идет в таблице? Позвольте вашей программе решить это. Начните с произвольных значений в таблице (вы можете, например, взять eval(line) = #black(line)-#white(line) или что-то еще). Пусть ваша программа играет сама, используя альфа-бета-поиск. Теперь обновите записи таблицы в соответствии с тем, что происходит. Есть много разных способов сделать это; Вот несколько (схематично описанных) немногих.

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

Для более сложной версии этих идей (применимо к шахматам, но те же идеи будут хорошо работать для гомоку), взгляните на http://cs.anu.edu.au/~Lex.Weaver/pub_sem/publications/knightcap.pdf.