Algorithme KNN pour Morpion

Signaler
-
Messages postés
29904
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
21 juin 2021
-
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

1 réponse

Messages postés
29904
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
21 juin 2021
7 125
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