Simple tic-tac-toe AI

Je sais que cela a été demandé beaucoup et j'ai recherché d'autres codes, mais la plupart de ce que j'ai vu ne semble pas impeccable (ne perd jamais) et simple, élégant et efficace. Et je ne peux pas décider quel type de solution correspondrait à cette description.

Les solutions que j'ai vues sont:

(1) Utilisation de minimax avec élimination alpha-bêta. Cela me semble compliqué et peut-être inutile pour un jeu aussi simple? Est-ce probablement trop compliqué? Sinon, dois-je faire beaucoup de codage dur ou est-ce que je suis mal compris l'algorithme?

(2) Écrivez votre code en utilisant la stratégie de pseudo de Wikipédia … Je ne sais pas exactement comment mettre en œuvre ceci. Par exemple, il suffit de dire "vérifier les fourchettes". La plupart de ces contrôles seraient-ils effectués en disposant d'un éventail de lignes gagnantes et en vérifiant si elles seraient remplies ou quelque chose comme ça? Sinon, quelqu'un peut-il me donner des indications sur les structures de données ou les conseils de base sur la façon de mettre en œuvre les contrôles posés dans le pseudocode ici: http://fr.wikipedia.org/wiki/Tic-tac-toe#Strategy . J'ai également vu des algorithmes qui donnent une valeur numérique à un carré 'X' et un carré 'O' puis utilisent la somme pour décider le gagnant mais je ne vois pas pourquoi cela est particulièrement utile.

D'autres solutions raisonnables ?

Pour être honnête, lorsqu'il s'agit d'AI et d'heuristiques, les tâches les plus simples peuvent être compliquées très rapidement. L'approche minimax vous donnera les meilleurs résultats et ne devrait pas être trop difficile compte tenu du fait que vous mettez en œuvre l'IA. C'est une norme établie avec une logique de jeu basée sur le joueur à 2 joueurs.

Découvrez ce site … il donne un bon aperçu de l'IA tic-tac-toe et de la mise en œuvre minimax.

http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

Modifier:

En remarquant que quelqu'un a écrit "Brute Force" … cela finira par être une manière inefficace de la mise en œuvre des heuristiques impliquées dans le minimax. L'itération à travers tous les mouvements possibles en fonction des autres joueurs, le dernier mouvement, n'est qu'une autre façon de mettre en œuvre une heuristique … sauf s'il semble être, à mon avis, plus de travail. La mise en œuvre de Minimax sera simple et efficace.

Edit2:

La «mise en œuvre plus simple» est quelque peu relative. Minimax est la norme et, comme je l'ai dit dans le commentaire, vous pouvez manipuler la heuristique en fonction des cas que vous recherchez …

J'aimerais pouvoir vous dire la manière la plus simple, mais il y a tellement de variables qui dépendent de l'implantation de votre jeu dans le code.

Prenez les suggestions, regardez la mise en œuvre du jeu, puis voyez ce qui vous convient le mieux!

Ce qui est simple pour une personne peut être compliqué par une autre. J'essaie juste de vous donner des options et minimax est assez solide. Peut-être essayer de l'ajuster pour répondre à vos besoins.

Edit3:

Faites-moi savoir si vous avez besoin de plus de direction. Je suis heureux de vous aider.

Utilisez le format de votre choix pour «coder» cette image en un ensemble de mouvements. L'IA va toujours gagner ou s'attacher.

Par exemple, vous pouvez l'encoder comme suit:

var turns = { "mefirst":{ "move":0, "next":[ null, { "move":4, "next":[ null, null, {"move":8}, // win {"move":8}, // win null, {"move":8}, // win {"move":8}, // win {"move":8}, // win { "move":6, "next":[ null, null, /* AND SO ON... */ ] } };

Ensuite, vous pouvez commencer par:

 if( ai_goes_first) { game = turns.mefirst; makeMove(game.move); } else game = turns.themfirst; playerTurn();

Où playerTurn ressemble à quelque chose comme:

 function playerTurn() { when player clicks a valid squeare { game = game.next[chosenSquare]; makeMove(game.move); if( game.next) playerTurn(); } }