Comment implémenter l'IA pour les dames / brouillons?

J'ai vu ce jeu de dames et je me suis demandé comment l'IA était implémentée.

Comment dois-je implémenter une IA pour les dames (brouillons, dama, dame)? Existe-t-il des algorithmes connus?

Très thnaks plein à tous. Je suis très étonné de voir cet article de blog sur le tutoriel du jeu Tic Tac Toe .

Donc, je veux un code source ouvert et un article de blog sur l'algorithme de jeu de dama .. Y a-t-il un lien utile ou un fichier doc ..? s'il vous plaît, faites-moi savoir..

Oh j'adore ces jeux!

Donc, tout d'abord, pour qu'un ordinateur joue à un jeu, il faut:

1. une structure avec laquelle travailler
2. règles de jeu
3. une condition de victoire pour travailler

Abordons cette pièce à la fois.

Structure

Puisque la carte est une grille 8x8 (mais pourrait facilement évoluer), et chaque espace de grille peut exister dans un seul des cinq états, définissons ces états:

[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]

Respectivement ENUM'd à:

[0, 1, 2, 3, 4]

Maintenant que nous savons ce que peut être chaque espace, nous avons besoin d'un moyen de représenter tous les espaces, ou le tableau si vous voulez. Presque tous les langages forts prendront en charge un tableau multidimensionnel (un tableau où chaque élément est un tableau contenant des données). Prenez donc le slack-code suivant pour définir notre tableau:

BOARD_ARRAY = array(8, 8)

Cela nous donnera un tableau 8 x 8 dans lequel nous pouvons stocker des entiers (nos énumérations d'avant):

(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)

Maintenant, vous pouvez déjà voir comment cela commence à ressembler à une planche! Je n'ai jamais joué la variante mentionnée dans la vidéo youtube mais elle semble commencer avec 2 rangées de morceaux blancs une rangée du bas et 2 rangées de morceaux noirs une rangée du haut. Ce qui signifierait que lorsque nous commençons un jeu, notre tableau devrait ressembler à ceci:

(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)

(N'oubliez pas que 2 représente 'BLACK_PIECE' et 1 représente 'WHITE_PIECE')

Alors maintenant, l'ordinateur a une structure avec laquelle travailler. Étape 1 terminée!

Règles

Imaginons que vous disposiez d'un véritable plateau devant vous, jouant contre un maître. Si vous essayez de déplacer l'une de ses pièces, vous vous ferez gifler la main. Si vous essayez de déplacer un morceau d'une manière que vous ne pouvez pas, vous vous ferez gifler la main. Si vous avez bien essayé de tricher ... vous avez l'idée. Mais le problème est que les ordinateurs ne le font pas. C'est donc notre travail de fournir des règles strictes pour jouer.

Nous devons créer un moyen de vérifier si un mouvement donné est «légal». Ce qui signifie que nous devons d'abord trouver un moyen de représenter un «mouvement». Une façon serait d'utiliser des positions de tableau; Par exemple, pour déplacer une pièce de [0, 0] à [0, 1], nous pourrions créer une fonction qui mettra à jour la carte en fonction de ce mouvement. Revenons donc au mou:

MY_MOVE = array( [0, 0], [0, 1] )

Ce qui précède représente une pièce, se déplaçant d'un espace vers le bas depuis le coin supérieur de la planche (en supposant que 0, 0 est le coin supérieur gauche). Vous pouvez également remarquer que j'ai choisi d'utiliser un tableau multidimensionnel pour le déplacement. En effet, les pièces peuvent théoriquement se déplacer un grand nombre de fois en un tour (pour «sauter» d'autres pièces). Imaginons donc à 0, 1 qu'il y avait une pièce adverse, ce qui signifie que nous atterririons à 0, 2:

MY_MOVE = array( [0, 0], [0, 2] )

Assez simple hein. Le programme doit comprendre que si nous sautons un espace, nous sautons un autre morceau (ou bien c'est un mouvement illégal et nous devons lancer une erreur). Maintenant, sautons deux morceaux:

MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )

Cela nous donne un moyen de décrire tout mouvement sur le plateau. Yay! Maintenant que je ne comprends pas complètement les règles du jeu exact en question (même si j'ai joué un peu aux dames canadiennes de mon temps), la légalité exacte du mouvement devra être définie par vous. Un bon flux jusqu'à ce stade ressemblerait à:

FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn

Ce qui précède suppose que vous pouvez parcourir chaque pièce pour trouver tous ses mouvements légaux, puis étant donné une collection de tous les mouvements légaux, choisissez le meilleur (stratégie ici). Le coup est ensuite appliqué au plateau ou lance une erreur. Ensuite, le joueur suivant prend son tour. Nous avons donc une IA qui sait jouer! Joie! Continuons.

Gagnant

Les jeux simples sont merveilleux, car gagner est défini par un état très simple. Il n'y a pas de morceaux blancs sur le tableau? Eh bien, je suppose que vous avez gagné! Ceci est implémenté à l'étape 2 lorsque nous choisissons le meilleur coup pour nous rapprocher de la condition gagnante.

Pour créer une IA très intelligente, vous pouvez conserver une base de données qui stocke chaque tableau possible en tant qu'état, avec chaque mouvement possible de chaque état possible, pour trouver des chaînes vers la victoire.

Vous pouvez également créer des stratégies, comme: s'il y a un morceau qui SERA sauté, sauvegardez ce morceau ou si un morceau est capable de sauter plus d'un autre morceau, faites ce saut.

Cela devrait vous donner un bon point de départ, ce n'est qu'une méthode de possibilités littéralement illimitées. Vous pourriez théoriquement construire un robot géant pour dessiner avec des crayons de couleur, puis effectuer une analyse spectrale sur le dessin pour choisir des mouvements ... mais cela ne fonctionnerait pas très bien ou rapidement. Cette méthode a fonctionné dans le passé et a bien fonctionné (: J'espère que ça aide!

Quelques mots sur la mise en œuvre

Checkers est ce que l'on appelle un jeu «résolu», en ce sens que nous pouvons calculer chaque mouvement sans inconnu. Mais c'est toute une série de mouvements! Il n'y a donc aucun moyen de tout faire manuellement ... si seulement il y en avait ... oh c'est vrai nous sommes des programmeurs. Poing en l'air

SQL est un merveilleux outil pour stocker tous ces mouvements apparemment sans fin. Pour ceux qui n'ont aucune expérience avec SQL, mySQL est un serveur SQL gratuit (assez facile à utiliser) et open source. SQL est utilisé pour gérer les bases de données, comme une feuille de calcul sur les stéroïdes. Il est également capable de stocker de grandes quantités de données et de les utiliser très rapidement.

Alors, comment pouvons-nous utiliser cela? Puisque nous savons que si la planche est dans un état exact (chaque pièce dans une certaine position), nous pouvons calculer tous les mouvements disponibles et les enregistrer. Par exemple:

+Board State+          +All Possible Moves+               +Best Move+
([0,0,1,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([7,6],[7,7])
([0,0,2,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([5,5],[5,4])
([0,0,1,3,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([4,4],[4,3])
etc...

Ainsi, lorsque l'ordinateur doit effectuer un mouvement, il recherche simplement l'état de la carte (stocké en tant que clé primaire) dans la base de données et peut choisir le meilleur mouvement (devrait être imbattable) ou l'un des autres mouvements pour le rendre plus convivial. AI.

Génial maintenant, construisons cette base de données. Nous devons d'abord calculer chaque état de la carte. Ce qui peut être fait avec une grande grosse boucle méchante, si quelqu'un veut passer du temps et travailler, ce serait génial. Regardez le tableau comme un grand nombre, puis comptez vers le haut, sauf dans la base 5 (0, 1, 2, 3, 4), et conditionnez que chaque joueur ne peut avoir que 16 pièces.

À ce stade, nous devrions avoir tous les états de la carte stockés et pouvons passer par le calcul de tous les mouvements possibles.

Une fois que tous les mouvements possibles sont calculés, vient la partie amusante de trouver les meilleurs mouvements possibles. C'est là que mes connaissances commencent à manquer et que des choses comme Minimax ou A * entrent en jeu. Désolé, je ne peux pas être plus utile à ce sujet: /

À tout moment dans le jeu, le nombre de mouvements possibles pour un joueur est assez faible * (environ 5), ce qui signifie qu'il est possible de penser à quelques mouvements, d'évaluer chaque mouvement possible et de sélectionner le meilleur mouvement.

Cette approche est appelée minimax (wikipedia) .

Pour implémenter minimax, vous aurez besoin d'une fonction d'évaluation qui renvoie un score pour une disposition de plateau et un joueur donnés. Pour les brouillons, une implémentation naïve serait une fonction qui renvoie un point pour chaque pièce que le joueur a en vie.

Une visualisation d'un arbre de décision minimax (de l'article de wikipedia). En bas à gauche se trouve le numéro de tour. Les nœuds foliaires ont chacun un score évalué qui est remonté dans l'arbre pour prendre une décision.

*cependant les dames sont le jeu avec le facteur de branchement le plus élevé qui a été complètement résolu .

L'élagage alpha – bêta est un algorithme de recherche qui cherche à diminuer le nombre de nœuds évalués par l'algorithme minimax dans son arbre de recherche. Il s'agit d'un algorithme de recherche contradictoire utilisé couramment pour jouer à la machine des jeux à deux joueurs (Tic-tac-toe, Chess, Go, etc.). Il arrête d'évaluer complètement un mouvement lorsqu'au moins une possibilité a été trouvée qui prouve que le mouvement est pire qu'un mouvement précédemment examiné. Ces mouvements n'ont pas besoin d'être évalués plus avant. Lorsqu'il est appliqué à un arbre minimax standard, il renvoie le même mouvement que le ferait minimax, mais élague les branches qui ne peuvent pas influencer la décision finale.