Évaluer une position au tic tac toe :) — Les-mathematiques.net The most powerful custom community solution in the world

Évaluer une position au tic tac toe :)

Modifié (25 Apr) dans Combinatoire et Graphes
Bonjour ! (ça faisait longtemps que je n'était pas venu :))
Je me suis demandé comment faire une IA sur scratch imbattable (en tout cas la meilleur possible) sur un tic tac toe avec un quadrillage N×N.
Première question. Sur un tic tac toe N×N où il faudrait aligner N' trucs, à partir de quel N' la partie est nulle ? 
Après il me faudra faire un algorithme mini-max(jamais essayé mais je pense que c'est faisable sur scratch avec un peu d'astuce :)) avec élagage alpha béta, pour le 3×3 l'arbre est petit, 4×4 je pense que ça passerait avec l'élagage  alpha béta mais pour N plus grand ça risque d'être difficile.
Il me faudrait une fonction qui arrive à dire, dans un maximum de cas si une position est perdante ou gagnante ou nulle. Mais encore une fois je n'ai pas trop d'idée (à part des trucs comme conter compter le nombre de trucs alignés au carré pour chaque alignement qui n'ont pas l'air de marcher). (!!! plus de coups son joués plus la fonction serait efficace. !!!)
Merci d'avance pour votre aide :)
[Pense à te relire avant d'envoyer. Merci ! AD]
La patience est un plat qui se mange sans sauce.

Réponses

  • Tu veux faire ça avec Scratch ? :/ Tu n’as pas peur.
    Pour le 3×3, tu peux étudier tous les cas, il y en a 9!, c’est petit (sauf peut-être pour Scratch).
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Modifié (25 Apr)
    Oui je n'ai pas peur :) 
    @nicolas.patrois pour le 3×3 c'est plutôt facile, scratch est assez rapide pour des jeux 3D ou des jeux complexes (jeux 100% pen) alors je pense que c'est petit même pour scratch :)
    (On peut diviser par 72 en automatisant les premiers coups par exemple).
    La patience est un plat qui se mange sans sauce.
  • Modifié (25 Apr)
    Sinon j'ai une idée tordue pour la fonction heuristique : faire un machine learning avec scratch (honnêtement pour des gros trucs ça serait le plus simple je pense :)  Donc je vais déjà réfléchir à un reconnaisseur de chiffre écrit à la main, ça me permettra de découvrir le machine learning après je pourrai tenter le truc plus compliqué
    La patience est un plat qui se mange sans sauce.
  • Sinon pour la fonction d'évaluation il y a un truc ici https://john.cs.olemiss.edu/~dwilkins/CSCI531/fall12/slides/AI_09_games.pdf
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!