Algorithme KNN pour Morpion Fermé

Question

Bonjour, 
je suis actuellement à la recherche d'aide pour mettre à bien une (mini) intelligence artificielle pour résoudre un morpion. Il existe déjà des méthodes pour ne jamais perdre à ce jeu mais j'aimerais faire moi même cette intelligence qui va, en jouant, acquérir de nouvelles données.

Mon idée est d'utiliser un algorithme KNN (k Nearest Neighbors) avec apprentissage supervisé (ce que j'ai vu en cours) et le lui faire ensuite récupérer des données. Mais j'ai déjà un doute quant à la possibilité de faire le projet car il faut checker 
- quelle case vient d'être jouée (principe d'un tableau "ABC" et "123" pour s'y repérer)
- quelle case sont disponibles
- et le taux de réussite par case disponible

Normalement, après quelques parties le programme devrait vite apprendre à former des trios de symboles, mais il faudrait d'abord calculer la distance des voisins les plus proches. Sauf que là il y a plusieurs "dimensions" avec un pourcentage, et le numéro de case.
Donc mes questions :

Même si pas optimal, est ce que l'algo KNN peut réussir a anticiper des coups au morpion ?
Si oui, quelle "classes" dois-je donner pour pouvoir calculer la distance ?
Et puis quelle distance utilisé (Euclidienne, ou Manhattan) ?

Au niveau du code, je pense pouvoir le réussir mais comme j'ai pas l'idée de comment y parvenir je suis bloquer...
Merci à ceux qui prendrons le temps de comprendre et de m'aider.

(PS : je suis en première spé NSI)

Configuration: Windows / Chrome 90.0.4430.212

mamiemando · Answer

Bonjour,

L'algorithme KNN est un algorithme de clustering, basé sur une notion de distance, et traditionnellement utilisé pour résoudre des problèmes de classification, comme l'explique ce lien.

Je ne vois donc pas trop comment tu veux l'exploiter pour faire une IA de morpion. Il faudrait clarifier ton idée. Donc tu devrais te commencer par te poser deux questions :
1. Quels clusters espères-tu faire émerger (ce qui pemettrait de choisir une distance, si tant est que KNN ait du sens pour ton problème) ?
2. En quoi ces clusters t'aideraient-ils à prendre une bonne décision.

Il me paraît pour ma part de consider l'algorithme minimax traditionnellement utilisé pour les jeux impliquant deux adversaires.

Ensuite, dans tout problème d'apprentissage supervisé, il faut spécifier quelles données d'exemple tu utilises pour l'entraînement. S'agit-il par exemple de parties (donc séquence de coups + étiquetage de qui a gagné en cas de non égalité) ?

Bonne chance

Algorithme KNN pour Morpion

1 réponse

Discussions similaires