J'ai écrit un code Tic tac toe très bien à un point. J'ai Alpha-Beta Pruning qui travaille aussi. J'ai rencontré un problème pour lequel j'ai besoin d'idées, PAS CODE. Comment puis-je choisir un coup qui va gagner en 4 coups contre un coup qui va gagner en 8 coups. Le problème que je rencontre est que la branche qui retourne un score optimal à partir de minimax/AB prunning gagnera peut-être en 8 coups donc elle élimine éventuellement une branche qui va gagner en 4 coups. J'ai rencontré plusieurs idées telles que l'heuristique de tueur, les tables de transposition et la recherche d'approfondissement itérative. Toutes les idées seraient trèsTaille Tic Tac Toe Moves
Répondre
Une façon que vous pouvez faire:
Effectuez votre recherche avec une profondeur maximum de 2, si aucune victoire sont à trouver, puis augmenter votre limite de profondeur, jusqu'à ce que vous trouviez une victoire. Pour le tic-tac-toe, l'heuristique tueur, la table de transposition, c'est peut-être peu à peu depuis, vous pouvez garder en mémoire toutes les possibilités de la carte.
Dans mon projet j'utilise le Proof-Number Search. Mais il y a tellement d'algorithmes que vous pouvez utiliser. Vous pouvez aussi trouver une idée dans this site, mais même si c'est sur les échecs, la plupart des idées peuvent être utilisées pour votre projet.
Alors, suggérez-vous que j'abandonne mon élagage alpha-bêta? Je sais qu'avec un jeu de tic tac toe standard, ne pas élaguer un arbre de jeu n'est pas si dur sur la mémoire de mes ordinateurs; Cependant, ce jeu de base est plus d'une première étape pour créer un jeu de tic tac toe quantique qui a beaucoup plus de mouvements que de base. –
Gardez Alpha-bêta taille, il est utile dans la plupart des cas, même le vôtre. Mais vous pouvez programmer une limite de profondeur – Nettogrof
Je crois que tictactoe a été réellement "résolu" dans le sens où il y a un algorithme qui garantira un gain ou un tirage, au moins former l'état initial donc une recherche alpha-bêta semble excessive. (sauf si vous apprenez simplement à l'implémenter sur un jeu plus simple que les échecs ou quoi que ce soit)
C'est un précurseur pour développer un jeu de tic-tac-toe quantique –
Pourquoi? Alpha beta est un moyen simple de mettre en œuvre une force brute pour un jeu comme celui-ci. Il n'est pas si trivial d'écrire un algorithme de recherche arborescente récursive même pour TIC-TAC-TOE. Utilisez l'alphabet whit dept = taches restantes. –
Je voudrais approfondir l'approfondissement itératif. Cela vous aidera à trouver le coup 4 avant la victoire de 8 coups.
(Voulait inclure dans un commentaire, mais il est devenu trop long)
approfondissement itératives serait probablement la question de cette « solution » plus facile. Il suffit de coller la recherche alpha-bêta dans une boucle qui augmente régulièrement la profondeur à laquelle va l'alpha-bêta. Vous pouvez inclure quelques tests dans votre boucle pour l'amener à se terminer tôt (par exemple, un coup gagnant trouvé).
ex:
while (!win_found && depth < 8)
{
alphaBetaSearch(win_found, depth);
depth++;
}
approfondissement peut sembler inutile itératives, car les états sont générés plusieurs fois, mais il se ce n'est pas coûteuse. La raison en est que dans un arbre de recherche avec le même (ou presque le même facteur de branchement à chaque niveau, la plupart des nœuds sont dans le niveau inférieur donc peu importe que les niveaux supérieurs soient générés plusieurs fois.)
Votre évaluation devrait évaluer les états gagnants de jeu plus fortement quand il y a moins de coups pris.Cela devrait être assez facile à implémenter.Allons que vous attribuez généralement à tous les états de jeu gagnants une valeur de 100. Pour un conseil de taille 9, ajoutez simplement la quantité Donc, un plateau gagnant après 8 tours évalue à 101 et un plateau gagnant après 5 tours évalue à 104.
J'ajouterais aussi que le moyen le plus simple de suivre le nombre de mouvements effectués est de suivre la profondeur de votre récursivité avec la recherche alpha-bêta. – Geoff
Si vous écrivez en langage compilé, vous pouvez rechercher tout l'arbre depuis le premier mouvement sans toute heuristique en moins de deux secondes (juste la fonction alpha beta et eval ce qui revient -1,0, + 1), sinon cela ne devrait pas prendre plus de 5 secondes pour le premier mouvement et beaucoup moins pour les autres mouvements.
Gagner au tic-tac-toe nécessite au moins 5 coups: 3 du gagnant, 2 du perdant. Droite? –
Pas si votre petit frère détourne le regard et vous mettez en bas et en plus X – SwDevMan81
Notti grand frère, vous êtes!: P –