Taille Tic Tac Toe Moves

Question

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ès

Answer 1

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.

Answer 2

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)

Answer 3

Je voudrais approfondir l'approfondissement itératif. Cela vous aidera à trouver le coup 4 avant la victoire de 8 coups.

Answer 4

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

Answer 5

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.

Answer 6

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.