angle-uparrow-clockwisearrow-counterclockwisearrow-down-uparrow-leftatcalendarcard-listchatcheckenvelopefolderhouseinfo-circlepencilpeoplepersonperson-fillperson-plusphoneplusquestion-circlesearchtagtrashx

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.

2 mars 2022
post main image

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

Laissez un commentaire

Commentez anonymement ou connectez-vous pour commenter.

Commentaires

Laissez une réponse

Répondez de manière anonyme ou connectez-vous pour répondre.