Construisez une IA pour gagner le jeu 2048
La chose la plus importante à propos de 2048 est d'atteindre le score le plus élevé en déplaçant les carreaux et en fusionnant la même tuile.
Nous devons définir comment déplacer les carreaux dans un jeu et comment générer de nouvelles carreaux après chaque mouvement.
Les codes sont dans l' Env.py
Ma première tentative est d'utiliser la méthode de recherche de Monte Carlo Tree pour gagner le jeu. J'ai essayé de passer par tous les mouvements possibles dans la profondeur de recherche donnée, puis j'ai comparé les scores dans le résultat pour choisir la meilleure décision dans la situation spécifique.
Les codes se trouvent dans le 2048_Search.py
Dans cette méthode, j'ai réglé la profondeur de 1 à 5 et j'ai fonctionné 100 fois dans chaque profondeur.
Voici quelques résultats.
PS: le taux de victoire moyen représente la possibilité d'atteindre 2048.
Score max moyen: 210,24
Taux de victoire moyen: 0%
| MAX REACH | Comptes | Accumuler% | Accumulé inversé% |
|---|---|---|---|
| 32 | 1 | 1% | 100% |
| 64 | 6 | 7% | 99% |
| 128 | 39 | 46% | 93% |
| 256 | 47 | 93% | 54% |
| 512 | 7 | 100% | 7% |
| 1024 | 0 | 100% | 0% |
Score max moyen: 1223,68
Taux de victoire moyen: 30%
| MAX REACH | Comptes | Accumuler% | Accumulé inversé% |
|---|---|---|---|
| 256 | 4 | 4% | 100% |
| 512 | 19 | 23% | 96% |
| 1024 | 47 | 70% | 77% |
| 2048 | 29 | 99% | 30% |
| 4096 | 1 | 100% | 1% |
| 8192 | 0 | 100% | 0% |
Score max moyen: 1646,08
Taux de victoire moyen: 54%
| MAX REACH | Comptes | Accumuler% | Accumulé inversé% |
|---|---|---|---|
| 256 | 1 | 1% | 100% |
| 512 | 9 | 10% | 99% |
| 1024 | 36 | 46% | 90% |
| 2048 | 48 | 94% | 54% |
| 4096 | 6 | 100% | 6% |
| 8192 | 0 | 100% | 0% |
Score max moyen: 2216,96
Taux de victoire moyen: 78%
| MAX REACH | Comptes | Accumuler% | Accumulé inversé% |
|---|---|---|---|
| 256 | 0 | 0% | 100% |
| 512 | 3 | 3% | 100% |
| 1024 | 19 | 22% | 97% |
| 2048 | 58 | 80% | 78% |
| 4096 | 20 | 100% | 20% |
| 8192 | 0 | 100% | 0% |
Score max moyen: 2467,84
Taux de victoire moyen: 78%
| MAX REACH | Comptes | Accumuler% | Accumulé inversé% |
|---|---|---|---|
| 256 | 0 | 0% | 100% |
| 512 | 2 | 2% | 100% |
| 1024 | 20 | 22% | 98% |
| 2048 | 48 | 70% | 78% |
| 4096 | 29 | 99% | 30% |
| 8192 | 1 | 100% | 1% |
Mon ordinateur MacBook Pro 15 "2012 (Mid) ne peut pas gérer le montant de calcul massif. Pour ceux qui sont intéressés par ce sujet peuvent essayer de définir le nombre de profondeurs plus grand pour voir ce qui se passe.
J'ai essayé une approche différente de ce problème. Au début du jeu, j'ai utilisé une petite profondeur pour rechercher pour accélérer le processus. La profondeur commence à partir de 2 et obtient un plus grand après les 400 mouvements jusqu'à atteindre la profondeur de set.
J'ai couru 200 époques et seulement 42,5% du total des jeux atteignent la profondeur 6. Cependant, le résultat de la profondeur 6 est assez impressionnant.
| MAX REACH | Comptes | Accumuler% | Accumulé inversé% |
|---|---|---|---|
| 1024 | 1 | 1,18% | 100% |
| 2048 | 50 | 60% | 98,8% |
| 4096 | 34 | 100% | 40% |
En profondeur 5, le score et le nombre de mouvements correspondants. Nous pouvons voir qu'en moyenne, nous devons dépasser 1600 étapes pour atteindre 2048.
| MAX REACH | Comptes | Somme de mouvements | Nombre moyen de mouvement par jeu |
|---|---|---|---|
| 512 | 2 | 1172 | 586 |
| 1024 | 25 | 25321 | 1012.84 |
| 2048 | 56 | 93276 | 1665.64 |
| 4096 | 17 | 48163 | 2833.12 |
Après avoir implémenté la méthode de recherche, j'ai étudié une méthode d'apprentissage de renforcement (RL). Afin de comprendre plus de manière exhaustive sur RL, j'implémente DQN qui est une branche principale de RL dans le jeu 2048.
DQN utilise la valeur Q comme récompense pour évaluer la décision que prend la machine.
Les codes se trouvent dans le dossier DQN.
Sarsa est également une sorte de RL. SARSA est légèrement différent de DQN.
En bref, la différence est que la politique de SARSA choisit le moyen le plus sûr d'éviter l'échec (jeu terminé) dans le jeu.
D'un autre côté, la politique DQN choisit toujours la façon d'atteindre les scores les plus élevés et parfois d'obtenir un échec en début de jeu.
Les codes sont dans le dossier SARSA.
