Tron lightcycles AI в Прологе - PullRequest
Новая
       20

Tron lightcycles AI в Прологе

2 голосов
/ 12 сентября 2011

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

Я сохраняю текущее игровое поле (вся матрица), текущую позицию человека и текущую позицию бота (например, ячейки матрицы 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, но я не могу понять это в Прологе.Может кто-нибудь помочь или показать направление, как заставить работать алгоритм min max с моей матрицей и текущими позициями в Прологе?

1 Ответ

2 голосов
/ 08 декабря 2011

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

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

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

Поскольку мы имеем дело с игрой с нулевой суммой, выигрыш оппонентов - это наша победа. Так что у нас Opponents-Gain = - Win. Мы можем переформулировать поиск 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,_)).

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

Bye

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

...