Tron lightcycles AI на Прологе

У меня проблема с написанием ИИ для игры (например, tron ​​lightcycles). Я пишу всю графику и движения на C с помощью ncurses. Теперь мне нужно написать ai бота на прологе. Я использую пролог swi.

Я сохраняю текущее игровое поле (всю матрицу), текущую позицию человека и текущую позицию бота (например, ячейки матрицы i, j). Они сохраняют как предикаты в файле .pl из c.

Мое игровое поле представляет собой матрицу, содержащую 1 и 0 (1 - посещено, 0 - не посещено). Нравится:

human_current_position(0,1).
bot_current_position(1,2).
matrix([[1,1,0,0],
[1,1,1,0],
[0,0,0,0],
[0,0,0,0]]).

Затем мне нужно проанализировать эту матрицу, например:

analyze(matrix).

Таким образом, функция анализа в прологе вернет некоторое направление (влево, вниз, вверх или вправо), сохраненное в файл, и моя программа c прочитает этот файл и переместит бота.

Итак, у меня вопрос - как я могу проанализировать эту матрицу на Прологе. Я читал что-то об алгоритме min-max, но не могу понять это на Prolog. Может ли кто-нибудь помочь или показать направление, как заставить работать алгоритм min max с моей матрицей и текущими позициями в Prolog?


artificial-intelligence algorithm minmax prolog
person nub    schedule 12.09.2011    source источник
comment
Почему нельзя использовать минимакс в Прологе?   -  person templatetypedef    schedule 12.09.2011
comment
Я могу использовать. Но я не понимаю, как это сделать.   -  person nub    schedule 13.09.2011
comment
Получите копию книги Ивана Братко Программирование на Прологе для искусственного интеллекта, которая содержит объяснение минимакса на Прологе.   -  person Fred Foo    schedule 13.09.2011

Ответы (1)


arrow_upward
2
arrow_downward

Я не уверен, приводит ли min-max к хорошему результату для tron. Так как на сетке обычно много коммутативных ходов, увеличивая пространство поиска. Может быть, для небольшого поля и / или небольшой глубины поиска. Но вы можете попытаться использовать отрицание как сбой для min-max, и вы получите обрезку альфа-бета бесплатно (я так думаю).

В играх без неопределенности алгоритм min-max вычисляет минимальный выигрыш оппонента, предполагаемый, с другой стороны, противник пытается максимизировать свой выигрыш. Пусть i перемещается над ходами игроков, а j - над ходами оппонента. Это приводит к следующей рекурсивной формуле:

Worst-Opponents-Gain = min_i (max_j ( Worst-Opponents-Gain_i_j) )

Поскольку мы имеем дело с игрой с нулевой суммой, выигрыш оппонентов - это наша победа. Итак, у нас есть Оппоненты-Прибыль = - Победа. Мы можем переформулировать поиск min-max в поиск max. Каждый игрок - максимайзер.

Best-Win = max_i ( - Best-Win_i).

Когда ваши выигрыши находятся в диапазоне {-1, 0, 1}, вы можете использовать отрицание как неудачу. Просто реализуйте следующие предикаты для моделирования своей игры:

% move(+Board,+Player,-Board)  
% init(+Board)  
% win(+Board,+Player)  
% oposite(+Player,-Player)  
% tie(+Board,+Player)

Вышеупомянутые предикаты будут полностью моделировать игру в аргументах, поэтому состояние игры будет сохранено в локальной переменной. Затем игра «анализируется» с помощью следующего предиката:

% best(+Board,+Player,-Board)  
best(X,P,Y) :-  
  move(X,P,Y),  
  (win(Y,P) -> true;  
    oposite(P,Q),  
    \+ tie(Y,Q),  
    \+ best(Y,Q,_)).

Возможно, вы захотите добавить дополнительные параметры, чтобы ограничить глубину поиска или вернуть символическое повторение хода.

Пока

PS: Вы найдете пример крестиков-ноликов здесь.

person Mostowski Collapse    schedule 08.12.2011