Хорошее минимаксное представление в Гомоку? - PullRequest
1 голос
/ 29 марта 2011

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

У меня такой вопрос: Что такое хорошее представление для узла в минимаксном дереве?

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

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

Ответы [ 2 ]

4 голосов
/ 29 марта 2011

Поиск в пространстве состояний осуществляется по различным состояниям платы.Есть много ходов, так как вы можете поместить камень в любом месте, где нет места.Каждое состояние может быть представлено, например, в виде матрицы 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 подряд.

и т. д.

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

1 голос
/ 29 марта 2011

Я бы рассмотрел функцию оценки в следующей форме: рассмотрим каждый набор, скажем, 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.

...