Une tentative de résolution du morpion à l'aide de Keras et de LSTM
Deep Learning n'est pas le moyen de résoudre le Tic-Tac-Toe mais c'est certainement une expérience éducative agréable.
Après avoir implémenté mon premier modèle Deep Learning LSTM pour un projet, je me suis demandé si Deep Learning pouvait aussi résoudre un jeu. Le premier jeu qui me vient à l'esprit est le Tic-Tac-Toe. Ensuite, vous faites des recherches sur Internet et il semble que de nombreuses personnes aient eu la même idée. Bien sûr.
Je présente ci-dessous ma solution pour résoudre le jeu du morpion en utilisant Keras et LSTM (mémoire à long terme). Il s'agit de Deep Learning et non d'une solution d'apprentissage par renforcement, qui est un sujet totalement différent.
La solution n'utilise pas un seul modèle, mais un modèle pour chaque mouvement. Pourquoi ? Parce que je voulais éviter que les données d'entraînement d'un premier coup soient "polluées" par les données d'entraînement des coups suivants.
À propos du jeu Tic-Tac-Toe
Il existe 255168 façons de jouer à ce jeu. Parmi ces parties, 131184 sont gagnées par le premier joueur, 77904 reviennent à l'adversaire et 46080 se terminent par un match nul.
Un plateau est constitué de cases dont le contenu est vide, X et O. Le nombre total de plateaux possibles est 3^9 = 19 683.
Ce que nous savons sur le jeu du morpion
Notre boîte noire Deep Learning sait ce qui suit sur le jeu :
- Il y a deux joueurs
- Il se joue sur 9 cases, appelons-le plateau de jeu
- Les joueurs effectuent un déplacement à tour de rôle
- Effectuer un déplacement signifie attribuer un champ inutilisé à un joueur.
- Cela signifie que nous savons quels champs sont disponibles lorsque nous effectuons un déplacement.
- Après quelques coups, quelqu'un nous dit que la partie est terminée et qui a gagné, perdu ou fait match nul.
C'est tout ce que nous savons, pas grand chose. Peut-on utiliser la Deep Learning pour jouer des parties gagnantes ?
Quelques questions et réponses
- Comment représenter le plateau ?
- Comment représenter un coup ?
- Doit-on utiliser la régression ou la classification et comment l'utiliser ?
- Faut-il utiliser le MLP (Multilayer Precepion) ou le LSTM (Long Short Term Memory) ou autre chose ?
- Chaque coup doit-il avoir son propre modèle ?
- Les deux joueurs doivent-ils avoir leur propre modèle ?
Comment représenter le plateau ?
Le plateau est un vecteur de neuf nombres, un pour chaque champ. Le numéro est 0 quand il peut être utilisé par le joueur1 ou le joueur2. Il vaut 1 lorsqu'il est pris par le joueur1 et 2 lorsqu'il est pris par le joueur2.
Comment représenter le coup ?
Ce n'est pas vraiment important, utilisons une liste d'une position de ligne et de colonne.
Régression ou classification et comment l'utiliser ?
Avec la régression, nous pouvons essayer de prédire une valeur pour le prochain coup.
Avec la classification, nous pouvons essayer de prédire un vecteur des meilleurs coups.
Je choisis ici la régression. Nous avons deux joueurs. Les valeurs pour le joueur 1 :
- 2 : victoire
- 1 : nul
- 0 : perdu
La prédiction sera une valeur entre 2 et 0. Si c'est notre tour, nous prédisons la valeur pour tous les coups disponibles. Ensuite, nous choisissons la meilleure valeur disponible, c'est-à-dire la valeur maximale. Cela donne notre coup. Pour le joueur 2, la meilleure valeur disponible est le minimum.
MLP (Multilayer Precepion) ou LSTM (Long Short Term Memory) ou autre chose ?
Je ne sais pas, essayons LSTM.
Chaque mouvement a son propre modèle ?
Je pense que c'est important. Si nous n'avons qu'un seul modèle, alors les données après l'étape N sont également incluses. Cela semble totalement faux.
Les deux joueurs devraient-ils avoir leur propre modèle ?
Je pense que oui. Le joueur 1 a toujours un coup d'avance, le joueur 2 a toujours un coup de retard.
Données d'entraînement
Nous utilisons la régression, voir ci-dessus, pour générer une valeur pour chaque coup possible à un moment donné. Le joueur 1 choisit le coup avec la valeur maximale, l'adversaire, le joueur 2 choisit le coup avec la valeur minimale.
Le plateau est un vecteur de neuf champs. Les champs peuvent être vides, X pour le joueur 1 et O pour le joueur 2. Un jeu est constitué de plusieurs vecteurs. Nous attribuons le résultat du jeu à tous les vecteurs d'un jeu.
Par exemple, les données d'un jeu ressemblent à ceci :
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> 2 # player1 makes a move
[1, 0, 0, 0, 0, 0, 0, 2, 0, 0] -> 2 # player2
[1, 1, 0, 0, 0, 0, 0, 2, 0, 0] -> 2 # player1
[1, 1, 0, 0, 0, 0, 0, 2, 0, 2] -> 2 # player2
[1, 1, 1, 0, 0, 0, 0, 2, 0, 2] -> 2 # player1 won
Pour plus d'informations sur le modèle LSTM , veuillez consulter le document "Comment développer des modèles LSTM pour la prévision des séries temporelles", voir les liens ci-dessous. Le modèle est un multivariate LSTM utilisant n_steps_in=2 et n_steps_out=1.
Pour générer les données d'entraînement, nous jouons le jeu plusieurs fois.
Données provenant uniquement de jeux uniques
Pour entraîner notre modèle, nous générons des données en jouant un certain nombre de parties. Pour ce faire, nous utilisons des mouvements aléatoires. Cela signifie qu'il peut y avoir de nombreux jeux en double dans notre ensemble de données, en d'autres termes, l'ensemble de données est pollué. Pour l'instant, je m'assure qu'il n'y a pas de parties en double, en utilisant une signature du plateau et du résultat final.
Un modèle pour chaque coup
Si nous utilisons un seul modèle, les données d'apprentissage sont "polluées" par les données futures. Lorsque notre coup est joué, nous voulons savoir quel est le meilleur coup suivant. Tout ce qui suit cette étape pollue nos données existantes. C'est pourquoi j'utilise plusieurs modèles, un pour chaque étape.
move[n] model[n] with data upto step[n+1]
move[n+1] model[n+1] with data upto step[n+2]
etc.
Pour le joueur 1, cela signifie qu'au coup [n], nous utilisons le modèle [n] qui a été entraîné avec des données jusqu'au coup n+1. De cette façon, nous pouvons sélectionner le meilleur coup disponible à effectuer.
Le paramètre n_steps_in=2 signifie que nous n'avons pas de modèle pour le premier coup. Ce que nous faisons, c'est que le premier coup est aléatoire, pour les deux joueurs.
De même, nous n'utilisons pas de modèle s'il ne reste qu'un seul coup.
Performance
Ok, j'ai implémenté ceci. Quelles sont les performances ? Le résultat de l'entraînement montre pour tous les modèles que l'erreur_absolue moyenne est réduite d'environ 0,8 à 0,6. Ce n'est pas très bon.
Dans les résultats ci-dessous, j'ai les deux joueurs. Un joueur peut être :
- RD : fait des mouvements aléatoires
- NN : fait des mouvements Neural Network
Le premier joueur est le joueur1, le second est le joueur2. Les données d'entraînement sont générées comme décrit ci-dessus. Elles sont générées jusqu'à ce que nous ayons, par exemple, 1000 x gagné-tiré-perdu = 1000xwon, 1000xlost, et 1000xdraw.
1. RD vs RD
Les deux joueurs effectuent des mouvements aléatoires.
Résultats de 4 séries de 1000 parties :
+-------+-------+-------+----------+-----------+-----------+
| won | lost | draw | won/lost | avg_moves | perc draw |
+-------+-------+-------+----------+-----------+-----------+
| 578 | 293 | 129 | 1.97 | 7.7 | 12.9% |
| 593 | 274 | 133 | 2.16 | 7.7 | 13.3% |
| 590 | 276 | 134 | 2.14 | 7.6 | 13.4% |
| 589 | 296 | 115 | 1.99 | 7.6 | 11.5% |
Cela ne semble pas déraisonnable. Le joueur 1 commence la partie et a donc un avantage sur le joueur 2.
2. NN vs RD, entraînement avec 1000 x gagné-tiré-perdu
Le joueur 1 fait des mouvements Neural Network , le joueur 2 fait des mouvements aléatoires.
Résultats de 4 séries de 1000 parties :
+-------+-------+-------+----------+-----------+-----------+
| won | lost | draw | won/lost | avg_moves | perc draw |
+-------+-------+-------+----------+-----------+-----------+
| 706 | 192 | 102 | 3.68 | 7.4 | 10.2% |
| 690 | 203 | 107 | 3.40 | 7.3 | 10.7% |
| 721 | 172 | 107 | 4.19 | 7.4 | 10.7% |
| 726 | 168 | 106 | 4.32 | 7.4 | 10.6% |
Meilleur que les mouvements aléatoires mais loin d'être parfait !
3. NN vs RD, entraînement avec 2000 x gagnés-tirés-perdus
Le joueur 1 fait des mouvements Neural Network , le joueur 2 fait des mouvements aléatoires.
Résultats de 4 séries de 1000 parties :
+-------+-------+-------+----------+-----------+-----------+
| won | lost | draw | won/lost | avg_moves | perc draw |
+-------+-------+-------+----------+-----------+-----------+
| 706 | 192 | 102 | 3.68 | 7.4 | 10.2% |
| 690 | 203 | 107 | 3.40 | 7.3 | 10.7% |
| 721 | 172 | 107 | 4.19 | 7.4 | 10.7% |
| 726 | 168 | 106 | 4.32 | 7.4 | 10.6% |
Encore mieux, mais encore loin de la perfection !
4. NN vs RD, entraînement avec 5000 x gagnants-tirants-perdants
Le joueur 1 fait des mouvements Neural Network , le joueur 2 fait des mouvements aléatoires.
Résultats de 4 séries de 1000 parties :
+-------+-------+-------+----------+-----------+-----------+
| won | lost | draw | won/lost | avg_moves | perc draw |
+-------+-------+-------+----------+-----------+-----------+
| 901 | 49 | 50 | 18.39 | 7.0 | 5.0% |
| 888 | 58 | 54 | 15.31 | 7.0 | 5.4% |
| 889 | 56 | 55 | 15.88 | 7.0 | 5.5% |
| 898 | 48 | 54 | 18.71 | 7.0 | 5.4% |
Cela ressemble plus à cela ! Peut-on faire mieux ?
5. NN vs RD, entraînement avec 20000 x gagnants-tirants-perdants.
Le joueur 1 fait des mouvements Neural Network , le joueur 2 fait des mouvements aléatoires.
Résultats de 4 séries de 1000 parties :
+-------+-------+-------+----------+-----------+-----------+
| won | lost | draw | won/lost | avg_moves | perc draw |
+-------+-------+-------+----------+-----------+-----------+
| 955 | 21 | 24 | 45.48 | 6.7 | 2.4% |
| 959 | 15 | 26 | 63.93 | 6.7 | 2.6% |
| 962 | 13 | 25 | 74.00 | 6.7 | 2.5% |
| 969 | 12 | 19 | 80.75 | 6.7 | 1.9% |
Amélioration considérable, plus de données (d'entraînement) sont importantes ! Les victoires du joueur 2 sont-elles simplement de la chance ?
6. RD vs NN, entraînement avec 20 000 x gagnants-tirés-perdus.
Maintenant, nous changeons l'ordre. Le joueur 1 fait des mouvements aléatoires et le joueur 2 fait des mouvements Neural Network .
Résultats de 4 séries de 1000 parties :
+-------+-------+-------+----------+-----------+-----------+
| won | lost | draw | won/lost | avg_moves | perc draw |
+-------+-------+-------+----------+-----------+-----------+
| 145 | 739 | 116 | 0.20 | 6.8 | 11.6% |
| 127 | 761 | 112 | 0.17 | 6.8 | 11.2% |
| 142 | 735 | 123 | 0.19 | 6.8 | 12.3% |
| 142 | 750 | 108 | 0.19 | 6.8 | 10.8% |
Cela semble raisonnable. Les résultats du joueur 2 ne sont pas aussi bons que ceux du joueur 1 ci-dessus. Le nombre de parties nulles a également augmenté. Est-ce que cela a à voir avec le fait que le joueur 1 commence en premier ?
7. NN vs NN, entraînement avec 20000 x gagnants-tirants-perdants.
Les deux joueurs font des coups Neural Network !
Résultats des séries de 1000 parties :
+-------+-------+-------+----------+-----------+-----------+
| won | lost | draw | won/lost | avg_moves | perc draw |
+-------+-------+-------+----------+-----------+-----------+
| 684 | 104 | 212 | 6.58 | 7.2 | 21.2% |
| 672 | 102 | 226 | 6.59 | 7.2 | 22.6% |
| 675 | 112 | 213 | 6.03 | 7.2 | 21.3% |
Nous nous attendons à ce que les gains et les pertes soient proches, mais ce n'est pas le cas. Nous nous attendons également à voir beaucoup plus de parties nulles. Cela semble bien.
Nous ne pouvons que conclure : Notre boîte noire n'est pas assez intelligente ... :-(
Le code
Voici le code pour que vous puissiez essayer vous-même. Keras Tuner est utilisé pour optimiser les hyperparameters.
Variables importantes :
- tuner_dir
C'est le répertoire créé par Keras Tuner. - must_train
Définissez True si vous voulez former les modèles.
Définissez False si vous voulez utiliser les modèles formés. - won_draw_lost_count
Ceci concerne les données d'entraînement, voir ci-dessus.
En général, vous voulez vous entraîner une fois, puis faire plusieurs essais. Si vous modifiez won_draw_lost_count, assurez-vous d'abord de supprimer le répertoire tuner_dir ! L'augmentation de won_draw_lost_count augmentera le temps d'entraînement.
# tictactoe.py
# std
import copy
import os
import random
import sys
import time
import operator
# optimizing hyperparameters with keras tuner
from keras.callbacks import EarlyStopping
from keras.models import load_model, Sequential
from keras.layers import Dense, Dropout, LSTM
import keras_tuner as kt
import numpy as np
import plotly.graph_objects as go
from sklearn.model_selection import train_test_split
from tensorflow.keras.optimizers import Adam
# get reproducible results
from numpy.random import seed
seed(1)
import tensorflow
tensorflow.random.set_seed(2)
# constants: game results
# note(s):
# - the order for player1, higher is better
# - result is float
GAME_RESULT_PLAYER1_WON = 2.
GAME_RESULT_DRAW = 1.
GAME_RESULT_PLAYER2_WON = 0.
# tuner parameters
class TunerParameter:
def __init__(self, name, val):
self.name = name
self.val = val
self.args = (name, val)
class TunerParameters:
def __init__(self, pars=None):
self.t_pars = []
for p in pars:
tpar = TunerParameter(p[0], p[1])
self.t_pars.append(tpar)
setattr(self, p[0], tpar)
def get_pars(self):
return self.t_pars
# subclassed hyperband tuner to add hyperparameters (here, batch_size)
class HyperbandTuner(kt.tuners.Hyperband):
def __init__(self, *args, **kwargs):
self.t_pars = None
if 't_pars' in kwargs:
self.t_pars = kwargs.pop('t_pars')
super(HyperbandTuner, self).__init__(*args, **kwargs)
def run_trial(self, trial, *args, **kwargs):
if self.t_pars is not None:
for tpar in self.t_pars:
kwargs[tpar.name] = trial.hyperparameters.Choice(tpar.name, tpar.val)
return super(HyperbandTuner, self).run_trial(trial, *args, **kwargs)
# tuner class
class Tuner:
def __init__(
self,
input_shape=None,
t_pars=None,
t_dir='tuner_dir',
):
self.input_shape = input_shape
self.t_dir = t_dir
self.t_pars = t_pars
def get_model(self, hp):
# model params: layer_input
model_params_layer_input = dict(
units=hp.Choice(*self.t_pars.layer_input_units.args),
activation='relu',
input_shape=self.input_shape,
)
'''
# model params: layer_hidden_1
model_params_layer_hidden_1 = dict(
units=hp.Choice(*self.t_pars.layer_hidden_1_units.args),
activation='relu',
input_shape=self.input_shape,
)
'''
# model params: compile
model_params_compile = dict(
#optimizer=Adam(learning_rate=hp.Choice(*self.t_pars.learning_rate.args)),
optimizer='adam',
loss='mean_absolute_error',
metrics=['mean_absolute_error'],
#metrics=['mean_absolute_error', 'val_mean_absolute_error'],
#metrics=['mean_absolute_error', 'val_mae'],
)
# model
model = Sequential()
model.add(LSTM(**model_params_layer_input))
model.add(Dense(
units=1,
))
# compile
model.compile(**model_params_compile)
return model
def get_model_path(
self,
model_num,
):
return os.path.join(self.t_dir, 'best_model_' + str(model_num))
def tune(
self,
X,
y,
model=None,
model_num=0,
use_early_stopping=False,
search_split_size=0.33,
fit_verbose=0,
plot_loss=False,
):
if model is None:
model = self.get_model
# use subclassed HyperBand tuner
tuner = HyperbandTuner(
model,
objective=kt.Objective('val_mean_absolute_error', direction='min'),
#allow_new_entries=True,
tune_new_entries=True,
hyperband_iterations=2,
max_epochs=260,
directory=self.t_dir,
project_name='model_' + str(model_num),
t_pars=[self.t_pars.batch_size],
)
print('\n{}\ntuner.search_space_summary()\n{}\n'.format('-'*60, '-'*60))
tuner.search_space_summary()
callbacks = []
if use_early_stopping:
callbacks = [EarlyStopping('val_loss', patience=3)]
print('\n{}\ntuner.search()\n{}\n'.format('-'*60, '-'*60))
tuner.search(
X,
y,
validation_split=search_split_size,
shuffle=False,
callbacks=callbacks
)
print('\n{}\ntuner.results_summary()\n{}\n'.format('-'*60, '-'*60))
tuner.results_summary()
print('\n{}\nbest_hps\n{}\n'.format('-'*60, '-'*60))
best_hps = tuner.get_best_hyperparameters()[0]
best_hps_dict = {}
for tpar in self.t_pars.get_pars():
try:
best_val = best_hps[tpar.name]
print('- {} = {}'.format(tpar.name, best_val))
best_hps_dict[tpar.name] = best_val
except:
pass
# add tuner epochs
best_hps_dict['epochs'] = best_hps['tuner/epochs']
# get best model
h_model = tuner.hypermodel.build(best_hps)
print('\n{}\nh_model.summary()\n{}\n'.format('-'*60, '-'*60))
h_model.summary()
# train best model
epochs = 50
print('training ...')
history = h_model.fit(
X,
y,
epochs=epochs,
workers=4,
use_multiprocessing=True,
verbose=fit_verbose,
)
if plot_loss:
fig_title = 'Loss - model[{}]'.format(model_num)
fig = go.Figure()
fig.add_trace(go.Scattergl(y=history.history['mean_absolute_error'], name='Train'))
##fig.add_trace(go.Scattergl(y=history.history['val_mean_absolute_error'], name='Valid'))
#fig.add_trace(go.Scattergl(y=history.history['loss'], name='Loss'))
fig.update_layout(height=500, width=1200, title=fig_title, xaxis_title='Epoch', yaxis_title='Mean Absolute Error')
fig.show()
# save best model
h_model.save(self.get_model_path(model_num))
print('\n{}\nh_model.evaluate()\n{}\n'.format('-'*60, '-'*60))
h_eval_dict = h_model.evaluate(X, y, return_dict=True)
print('h_eval_dict = {}'.format(h_eval_dict))
return dict(
h_model=h_model,
h_eval_dict=h_eval_dict,
best_hps_dict=best_hps_dict,
)
def load_model(
self,
model_num,
):
try:
return load_model(self.get_model_path(model_num))
except:
return None
class DataUtils:
@classmethod
def get_model_boards_and_results(cls, game_results):
# generate datasets
model_boards_and_results = {}
for m in range(9):
model_boards_and_results[m] = []
for game_result in game_results:
result = game_result.result
for i, board in enumerate(game_result.boards):
if i == 0:
# skip board0
continue
# model_boards_data
if i < 4:
# store for all models
for m in range(2, 9):
model_boards_and_results[m].append((board, result))
else:
# store for models[i - 1]
for m in range(i - 1, 9):
model_boards_and_results[m].append((board, result))
return model_boards_and_results
@classmethod
def get_model_data(cls, model_boards_and_results):
model_data = {}
for model_num in model_boards_and_results:
boards_and_results = model_boards_and_results[model_num]
boards = []
results = []
for board, result in boards_and_results:
boards.append(board)
results.append(result)
boards_len = len(boards)
results_len = len(results)
print('model[{}]: boards_len = {}, results_len = {}'.format(model_num, boards_len, results_len))
print('model[{}]:'.format(model_num))
#print('- boards = {}'.format(boards))
#print('- results = {}'.format(results))
if boards_len == 0:
continue
# create data for model
# player1 models: 2, 4, 6, 8
# player2 models: 3, 5, 7
# but we don't about this here
# 2 = player1 won
# 1 = draw
# 0 = player2 won
# this means:
# - player1 looks for the maximum
# - player2 looks for the minimum
dataset = []
for i, board in enumerate(boards):
result = results[i]
flattened_board_and_result = []
for row in board:
print('row = {}'.format(row))
flattened_board_and_result.extend(row)
flattened_board_and_result.append(result)
dataset.append(flattened_board_and_result)
dataset = np.array(dataset, dtype=object)
print('dataset = {}'.format(dataset))
X_in, y_in = cls.split_sequences(dataset, n_steps_in, n_steps_out)
print('X_in = {}'.format(X_in))
print('y_in = {}'.format(y_in))
X_in_shape = X_in.shape
print('X_in_shape = {}'.format(X_in_shape))
model_data[model_num] = dict(
X_in=X_in,
y_in=y_in,
)
return model_data
# split a multivariate sequence into samples
@classmethod
def split_sequences(cls, sequences, n_steps_in, n_steps_out):
X, y = list(), list()
for i in range(len(sequences)):
# find the end of this pattern
end_ix = i + n_steps_in
out_end_ix = end_ix + n_steps_out-1
# check if we are beyond the dataset
if out_end_ix > len(sequences):
break
# gather input and output parts of the pattern
seq_x, seq_y = sequences[i:end_ix, :-1], sequences[end_ix-1:out_end_ix, -1]
X.append(seq_x)
y.append(seq_y)
if n_steps_out == 1:
y1 = []
for v in y:
y1.append(v[0])
y = y1
return np.array(X), np.array(y)
@classmethod
def split_datasets(cls, X, y):
return train_test_split(X, y, test_size=0.33, shuffle=False, random_state=42)
class GameResult:
def __init__(
self,
boards=None,
moves=None,
result=None,
):
self.boards = boards
self.moves = moves
self.result = result
class GamePlay:
def __init__(
self,
n_steps_in=None,
n_steps_out=None,
n_features=None,
):
self.n_steps_in = n_steps_in
self.n_steps_out = n_steps_out
self.n_features = n_features
self.player_value2displays = {0: ' ', 1: 'X', 2: 'O'}
def get_empty_board(self):
return [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
def show_boards(self, boards, show_board_num=True, horizontal=True):
boards_strs = []
for i, board in enumerate(boards):
strs = self.show_board(board, board_num=i, return_strs=horizontal)
boards_strs.append(strs)
if horizontal:
for i in range(len(strs)):
line_parts = []
for b in boards_strs:
line_parts.append(b[i])
print('{}'.format(' '.join(line_parts)))
def show_board(self, board, board_num=None, return_strs=False):
strs = []
if board_num is not None:
strs.append('board: {:<6}'.format(board_num))
ds = '+---+---+---+'
strs.append('{}'.format(ds))
for r in range(3):
row_items = []
for c in range(3):
row_items.append(self.player_value2displays[board[r][c]])
dr = '| {} |'.format(' | '.join(row_items))
strs.append('{}'.format(dr))
strs.append('{}'.format(ds))
if return_strs:
return strs
for s in strs:
print(s)
def get_available_moves(self, board):
moves = []
for r in range(3):
for c in range(3):
if board[r][c] == 0:
moves.append([r, c])
return moves
def player_won(self, player, board):
# row, col win
for r in range(3):
if board[r][0] == player and board[r][1] == player and board[r][2] == player:
return True
for c in range(3):
if board[0][c] == player and board[1][c] == player and board[2][c] == player:
return True
# diag win
if board[0][0] == player and board[1][1] == player and board[2][2] == player:
return True
if board[2][0] == player and board[1][1] == player and board[0][2] == player:
return True
return False
def get_other_player(self, player):
return 2 if player == 1 else 1
def get_inverted_board(self, board):
board = copy.deepcopy(board)
inverted_board = self.get_empty_board()
for r in range(3):
for c in range(3):
if board[r][c] == 1:
inverted_board[r][c] = 2
elif board[r][c] == 2:
inverted_board[r][c] = 1
return inverted_board
def get_deeplearning_move(self, h_model, player, board, dbg=False):
# get moves
available_moves = self.get_available_moves(board)
if len(available_moves) == 1:
return available_moves[0]
board = copy.deepcopy(board)
move_vs = []
X_pred = []
for i, move in enumerate(available_moves):
next_board = copy.deepcopy(board)
self.make_move(player, next_board, move)
# create X_pred
x_pred = [
self.board2vector(board),
self.board2vector(next_board),
]
if dbg: print('x_pred = {}'.format(x_pred))
X_pred.append(x_pred)
y = [0, move[0], move[1]]
move_vs.append(y)
X_pred_len = len(X_pred)
if X_pred_len > 0:
if dbg: print('X_pred = {}'.format(X_pred))
X_pred = np.array(X_pred).reshape(X_pred_len, self.n_steps_in, self.n_features)
predictions = h_model.predict(X_pred)
if dbg: print('for X_Pred = {}, predictions = {}'.format(X_pred, predictions))
for i, y in enumerate(predictions):
move_vs[i][0] = y[0]
if dbg: print('move_vs = {}'.format(move_vs))
# get maximum or minimum
if player == 1:
reverse = True
else:
reverse = False
sorted_move_vs = move_vs.sort(key=operator.itemgetter(0), reverse=reverse)
sorted_move_vs = move_vs
if dbg: print('sorted_move_vs = {}'.format(sorted_move_vs))
#sys.exit()
move = [sorted_move_vs[0][1], sorted_move_vs[0][2]]
if dbg: print('player = {}, y = {} -> selected move = {}'.format(player, y, move))
#sys.exit()
return move
# random move
if dbg: print('player = {}, dont know, move = {}'.format(player, move))
move = random.choice(available_moves)
return move
def get_random_move(self, board):
moves = self.get_available_moves(board)
return random.choice(moves)
def make_move(self, player, board, move):
board[move[0]][move[1]] = player
return board
def play_game(self, player1_type=0, player2_type=0, h_models=[], show_game=False):
# player_type: 0 = random, 1 = dl
# first board is empty
board = self.get_empty_board()
boards = [board]
moves = []
player = 1
i = 0
while True:
if player == 1:
if player1_type == 0 or len(moves) < 2:
print('rd move: i = {}, player = {}'.format(i, player))
move = self.get_random_move(board)
else:
print('nn move: i = {}, player = {}'.format(i, player))
move = self.get_deeplearning_move(h_models[i], player, board)
else:
if player2_type == 0 or len(boards) <= 2:
print('rd move: i = {}, player = {}'.format(i, player))
move = self.get_random_move(board)
else:
print('nn move: i = {}, player = {}'.format(i, player))
move = self.get_deeplearning_move(h_models[i], player, board)
# make the move
self.make_move(player, board, move)
if show_game:
print('player = {}, made move = {}'.format(player, move))
self.show_board(board)
# store for players
boards.append(copy.deepcopy(board))
moves.append(copy.deepcopy(move))
# check won, lost, draw
if self.player_won(player, board):
# player won
if player == 1:
result = GAME_RESULT_PLAYER1_WON
else:
result = GAME_RESULT_PLAYER2_WON
return GameResult(
boards=boards,
moves=moves,
result=result,
)
other_player = self.get_other_player(player)
if self.player_won(other_player, board):
# other_player won
if other_player == 1:
result = GAME_RESULT_PLAYER1_WON
else:
result = GAME_RESULT_PLAYER2_WON
return GameResult(
boards=boards,
moves=moves,
result=result,
)
if len(self.get_available_moves(board)) == 0:
# draw
return GameResult(
boards=boards,
moves=moves,
result=GAME_RESULT_DRAW,
)
# change player
player = other_player
i += 1
def play_games(self, n_games, player1_type=0, player2_type=0, h_models=None, show_games=False):
player_wins = [0, 0]
draws = 0
total_moves = 0
result_to_text = {
0: 'lost',
1: 'draw',
2: 'won',
}
for i in range(n_games):
print('playing game {} of {} ...'.format(i, n_games))
game_result = self.play_game(
player1_type=player1_type,
player2_type=player2_type,
h_models=h_models,
show_game=False,
)
self.show_boards(game_result.boards)
total_moves += len(game_result.moves)
last_move = game_result.moves[-1]
if game_result.result == GAME_RESULT_DRAW:
draws += 1
elif game_result.result == GAME_RESULT_PLAYER1_WON:
player_wins[0] += 1
elif game_result.result == GAME_RESULT_PLAYER2_WON:
player_wins[1] += 1
if player_wins[1] == 0:
won_div_lost_fmt = '{:<8}'.format('')
else:
won_div_lost = player_wins[0]/player_wins[1]
won_div_lost_fmt = '{:8.2f}'.format(won_div_lost)
moves_avg = total_moves/n_games
print('summary for player1 after {} games\n--------'.format(n_games))
sep_line = '+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+'.format('-'*5, '-'*5, '-'*5, '-'*8, '-'*9, '-'*9)
print(sep_line)
print('| {:<5} | {:<5} | {:<5} | {:<8} | {:<9} | {:<9} |'.format('won', 'lost', 'draw', 'won/lost', 'avg_moves', 'perc draw'))
print(sep_line)
print('| {:5d} | {:5d} | {:5d} | {} | {:9.1f} | {:8.1f}% |'.format(player_wins[0], player_wins[1], draws, won_div_lost_fmt, moves_avg, (100*draws)/n_games))
print('')
print('')
def board2vector(self, board):
b = []
for r in range(3):
for c in range(3):
b.append(board[r][c])
return b
def get_game_result_signature(self, game):
sig = ''
for board in game.boards:
for r in range(3):
for c in range(3):
sig += str(board[r][c])
for move in game.moves:
sig += str(move[0]) + str(move[1])
sig += str(game.result)
return sig
def generate_datasets(self, n_games):
# game_result signatures to prevent duplicate data
sigs = []
won_count = 0
lost_count = 0
draw_count = 0
# generate game data
game_results = []
game_count = 0
while won_count < n_games or lost_count < n_games or draw_count < n_games:
if game_count > 255000:
break
print('playing game {}'.format(game_count))
game_count += 1
game_result = self.play_game()
boards_len = len(game_result.boards)
moves_len = len(game_result.moves)
result = game_result.result
print('boards_len = {}, moves_len = {}, result = {}'.format(boards_len, moves_len, result))
if boards_len != (moves_len + 1):
print('boards_len != moves_len:')
print('game_result.boards = {}'.format(game_result.boards))
print('game_result.moves = {}'.format(game_result.moves))
sys.exit()
# skip identical games
sig = self.get_game_result_signature(game_result)
if sig in sigs:
continue
# distribute won, draw, lost
if result == GAME_RESULT_DRAW:
if draw_count >= n_games:
continue
draw_count += 1
elif result == GAME_RESULT_PLAYER1_WON:
if won_count >= n_games:
continue
won_count += 1
elif result == GAME_RESULT_PLAYER2_WON:
if lost_count >= n_games:
continue
lost_count += 1
sigs.append(sig)
game_results.append(game_result)
print('game_count = {}'.format(game_count))
print('len(sigs) = {}'.format(len(sigs)))
print('won_count = {}, lost_count = {}, draw_count = {}'.format(won_count, lost_count, draw_count))
input('Press ENTER to continue ...')
return game_results
# start
# hyperparameters name and value, are the inputs for hp.Choice()
t_pars = TunerParameters(
pars=[
('layer_input_units', [64, 128]),
#('layer_hidden_1_units', [64, 128]),
('batch_size', [8, 32]),
],
)
# lstm
n_steps_in = 2
n_steps_out = 1
n_features = 9
# other
tuner_dir = 'tuner_dir_tictactoe'
won_draw_lost_count = 5000
#won_draw_lost_count = 20000
# train or use
must_train = True
#must_train = False
game_play = GamePlay(
n_steps_in=n_steps_in,
n_steps_out=n_steps_out,
n_features=n_features,
)
h_models = [None]*9
if must_train:
game_results = game_play.generate_datasets(won_draw_lost_count)
model_boards_and_results = DataUtils.get_model_boards_and_results(game_results)
model_data = DataUtils.get_model_data(model_boards_and_results)
model_data_lens = [None]*9
print('model_data:')
for model_num in model_data:
data = model_data[model_num]
print('model_num = {}'.format(model_num))
X_in = data['X_in']
y_in = data['y_in']
print('- X_in = {}'.format(X_in))
print('- y_in = {}'.format(y_in))
model_data_lens[model_num] = len(X_in)
#continue
# split into train and test
X_train, X_test, y_train, y_test = DataUtils.split_datasets(X_in, y_in)
# convert
X_in = np.asarray(X_in).astype(int)
y_in = np.asarray(y_in).astype(int)
X_train = np.asarray(X_train).astype(int)
y_train = np.asarray(y_train).astype(int)
print('type(X_train) = {}, len(X_train) = {}, X_train = {}'.format(type(X_train), len(X_train), X_train))
print('type(y_train) = {}, len(y_train) = {}, y_train = {}'.format(type(y_train), len(y_train), y_train))
n_features = X_train.shape[2]
print('n_features = {}'.format(n_features))
tuner = Tuner(
input_shape=(n_steps_in, n_features),
t_pars=t_pars,
t_dir=tuner_dir,
)
tune_result = tuner.tune(
X_train,
y_train,
model_num=model_num,
#plot_loss=False,
plot_loss=True,
)
h_model = tune_result['h_model']
# add to our list of models
h_models[model_num] = h_model
h_eval_dict = tune_result['h_eval_dict']
print('h_model = {}'.format(h_model))
print('h_eval_dict = {}'.format(h_eval_dict))
# debug: show a prediction for the h_model
X = [
[
[ [0, 0, 0], [1, 0, 0], [0, 0, 0] ],
[ [0, 0, 0], [1, 2, 0], [0, 0, 0] ],
],
[
[ [0, 0, 0], [0, 1, 0], [0, 0, 0] ],
[ [0, 0, 0], [0, 1, 2], [0, 0, 0] ],
]
]
X_pred = np.array(X).reshape(2, n_steps_in, n_features)
predictions = h_model.predict(X_pred)
print('h_model: for X_pred = {}, predictions = {}'.format(X_pred, predictions))
# debug: show a prediction for the previously saved h_model
loaded_h_model = tuner.load_model(model_num)
predictions = loaded_h_model.predict(X_pred)
print('loaded_h_model: for X_pred = {}, predictions = {}'.format(X_pred, predictions))
# here we have trained and saved the models
print('model_data_lens = {}'.format(model_data_lens))
input('Press ENTER to continue ...')
# load saved models
if h_models[2] is None:
# load saved
print('loading saved models ...')
h_models = [None]*9
for model_num in range(9):
print('loading saved model {} ...'.format(model_num))
tuner = Tuner(
input_shape=(n_steps_in, n_features),
t_pars=t_pars,
t_dir=tuner_dir,
)
loaded_h_model = tuner.load_model(model_num)
if loaded_h_model is None:
continue
'''
# debug: show a prediction for the previously saved h_model
X = [
[
[ [0, 0, 0], [1, 0, 0], [0, 0, 0] ],
[ [0, 0, 0], [1, 2, 0], [0, 0, 0] ],
],
[
[ [0, 0, 0], [0, 1, 0], [0, 0, 0] ],
[ [0, 0, 0], [0, 1, 2], [0, 0, 0] ],
]
]
X_pred = np.array(X).reshape(2, n_steps_in, n_features)
predictions = loaded_h_model.predict(X_pred)
print('loaded_h_model: for X_pred = {}, predictions = {}'.format(X_pred, predictions))
sys.exit()
'''
h_models[model_num] = loaded_h_model
# debug: show models
for model_num in range(9):
print('h_models[{}] = {}'.format(model_num, h_models[model_num]))
print('play some games')
# play games and see results, player[1|2]_type: 0 = RD (random move), 1 = NN (neural network move)
game_play.play_games(
1000,
player1_type=1,
player2_type=1,
h_models=h_models,
show_games=True,
)
Amélioration des performances
Nous pouvons essayer d'améliorer les performances de la manière suivante :
- ajouter plus de données d'entraînement
- ajouter plus de choix hyperparameter
- ajouter plus de choix de hyperparameter
- ajouter plus de hyperparameter aux modèles, comme le taux d'apprentissage
- ajouter des couches supplémentaires aux modèles
- sauter les premiers coups, ce qui réduit les données d'entraînement de
Il serait intéressant d'implémenter des statistiques qui montrent également le nombre de parties terminées en 5, 6, 7, 8 ou 9 coups.
Résumé
Utiliser Deep Learning de cette manière n'est pas la solution pour résoudre ce jeu. Je le savais quand j'ai commencé, mais je voulais tout de même essayer cette solution avant de me pencher sur l'apprentissage par renforcement. Il y a beaucoup d'améliorations possibles et je vais certainement en essayer certaines à l'avenir. L'utilisation de Keras Tuner pour régler les hyperparameters m'a encore facilité la vie. C'était un beau projet mais aussi beaucoup de travail. Mais j'ai beaucoup appris.
Liens / crédits
How many tic tac toe games are there?
https://tictactoebeast.com/post/how-many-tic-tac-toe-games-are-there
How many Tic-Tac-Toe (noughts and crosses) games are possible?
http://www.se16.info/hgb/tictactoe.htm
How to Develop LSTM Models for Time Series Forecasting
https://machinelearningmastery.com/how-to-develop-lstm-models-for-time-series-forecasting
Part 4 — Neural Network Q Learning, a Tic-Tac-Toe player that learns — kind of
https://medium.com/@carsten.friedrich/part-4-neural-network-q-learning-a-tic-tac-toe-player-that-learns-kind-of-2090ca4798d
Tic-Tac-Toe and Reinforcement Learning
https://medium.com/swlh/tic-tac-toe-and-deep-neural-networks-ea600bc53f51
Tic-Tac-Toe and Reinforcement Learning
https://medium.com/swlh/tic-tac-toe-and-deep-neural-networks-ea600bc53f51
En savoir plus...
Deep Learning Machine Learning
Récent
- Masquer les clés primaires de la base de données UUID de votre application web
- Don't Repeat Yourself (DRY) avec Jinja2
- SQLAlchemy, PostgreSQL, nombre maximal de lignes par user
- Afficher les valeurs des filtres dynamiques SQLAlchemy
- Transfert de données sécurisé grâce au cryptage à Public Key et à pyNaCl
- rqlite : une alternative à haute disponibilité et dist distribuée SQLite
Les plus consultés
- Utilisation des Python's pyOpenSSL pour vérifier les certificats SSL téléchargés d'un hôte
- Utiliser UUIDs au lieu de Integer Autoincrement Primary Keys avec SQLAlchemy et MariaDb
- Connexion à un service sur un hôte Docker à partir d'un conteneur Docker
- Utiliser PyInstaller et Cython pour créer un exécutable Python
- SQLAlchemy : Utilisation de Cascade Deletes pour supprimer des objets connexes
- Flask RESTful API validation des paramètres de la requête avec les schémas Marshmallow