Tron lightcycles AI dans Prolog

Question

J'ai le problème pour écrire l'IA dans le jeu (comme les vélos électriques tron). J'écris tous les graphiques et mouvements sur C en utilisant ncurses. Maintenant, j'ai besoin d'écrire l'IA du bot sur le prologue.J'utilise swi prolog.

Je sauvegarde le champ de jeu actuel (toute la matrice), la position humaine actuelle et la position actuelle du bot (comme les cellules de la matrice i, j).Ils sont sauvegardés comme des prédicats dans le fichier .pl de c.

Mon champ de jeu est une matrice qui contient 1 et 0 (1 - visité, 0 - non visité). Comme ceci:

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]]).

Ensuite, je dois analyser cette matrice comme:

analyze(matrix).

Ainsi, la fonction d'analyse dans prolog retournera une direction (gauche, bas, haut ou droite) sauvegardée dans le fichier et mon programme c lit ce fichier et déplace le bot.

J'ai donc la question - Comment puis-je analyser cette matrice dans Prolog. J'ai lu quelque chose sur l'algorithme min-max, mais je ne peux pas m'en rendre compte dans Prolog. Quelqu'un peut-il aider ou montrer comment faire fonctionner l'algorithme min max avec ma matrice et mes positions actuelles dans Prolog?

Answer 1

Je ne sais pas si min-max conduit à de bons résultats pour tron. Puisque sur une grille on a généralement de nombreux mouvements commutatifs, faisant exploser l'espace de recherche. Peut-être pour un petit champ et / ou une petite profondeur de recherche. Mais vous pouvez essayer d'utiliser la négation comme un échec pour min-max et vous obtenez la taille alfa-beta gratuitement (je suppose).

Dans les jeux sans incertitude, l'algorithme min-max calcule le gain minimal de l'adversaire supposé que l'adversaire essaie par contre de maximiser son gain. Laissez i sur les mouvements des joueurs et j sur les mouvements de l'adversaire. Cela conduit à une formule récursive comme suit:

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

Puisque nous avons affaire à un jeu à somme nulle, le gain des adversaires est notre victoire. Pour que nous ayons Opponents-Gain= - Win. Nous pouvons reformuler la recherche min-max en une recherche max. Chaque joueur est un maximisateur.

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

Lorsque vos valeurs de gain sont dans la plage {-1, 0, 1}, vous pouvez utiliser la négation comme échec. Il suffit de mettre en œuvre les prédicats suivants pour modéliser votre jeu:

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

Les prédicats ci-dessus modéliseront complètement le jeu dans les arguments, ainsi un état du jeu sera stocké dans une variable locale. Le jeu est ensuite "analysé" via le prédicat suivant:

% 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,_)).

Vous souhaiterez peut-être ajouter des paramètres supplémentaires pour limiter la profondeur de recherche ou pour renvoyer une représentation symbolique du mouvement.

Au revoir

PS: Vous trouvez un exemple de tic-tac-toe ici .