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

Ein Versuch, Tic-Tac-Toe mit Keras und LSTM zu lösen

Deep Learning ist nicht der Weg, um Tic-Tac-Toe zu lösen, aber es ist sicherlich eine schöne pädagogische Erfahrung.

2 März 2022
post main image

Nachdem ich mein erstes Deep Learning LSTM Modell für ein Projekt implementiert hatte, überlegte ich, ob Deep Learning auch ein Spiel lösen könnte. Das erste Spiel, das mir einfällt, ist Tic-Tac-Toe. Dann sucht man im Internet und es scheint viele Leute zu geben, die die gleiche Idee hatten. Ja, natürlich.

Im Folgenden stelle ich meine Lösung vor, um Tic-Tac-Toe mit Keras und LSTM (Long Short Term Memory) zu lösen. Es handelt sich um Deep Learning und nicht um eine Reinforcement Learning Lösung, das ist ein ganz anderes Thema.

Die Lösung verwendet nicht ein einziges Modell, sondern ein Modell für jeden Zug. Und warum? Weil ich vermeiden wollte, dass die Trainingsdaten für einen frühen Zug mit Trainingsdaten für zukünftige Züge "verunreinigt" werden.

Über das Tic-Tac-Toe-Spiel

Es gibt 255168 Möglichkeiten, dieses Spiel zu spielen. Von diesen Spielen werden 131184 vom ersten Spieler gewonnen, 77904 gehen an den Gegner, und 46080 enden unentschieden.

Ein Brett besteht aus Feldern mit leerem Inhalt, X und O. Die Gesamtzahl der möglichen Bretter ist 3^9 = 19.683.

Was wir über das Tic-Tac-Toe-Spiel wissen

Unsere Blackbox Deep Learning weiß folgendes über das Spiel:

  • Es gibt zwei Spieler
  • Es wird auf 9 Feldern gespielt, nennen wir es ein Brett
  • Die Spieler machen abwechselnd einen Zug
  • Ein Zug bedeutet, einem Spieler ein unbenutztes Feld zuzuweisen.
  • Das bedeutet, dass wir wissen, welche Felder verfügbar sind, wenn wir einen Zug machen.
  • Nach einigen Zügen sagt uns jemand, dass das Spiel vorbei ist und wer gewonnen, verloren oder unentschieden gespielt hat.

Das ist alles, was wir wissen, nicht wirklich viel. Können wir Deep Learning verwenden, um Gewinnpartien zu spielen?

Einige Fragen und Antworten

  • Wie stellen wir das Brett dar?
  • Wie stellen wir einen Zug dar?
  • Sollen wir Regression oder Klassifikation verwenden und wie wird sie angewendet?
  • Sollten wir MLP (Multilayer Precepion) oder LSTM (Long Short Term Memory) oder etwas anderes verwenden?
  • Sollte jeder Zug sein eigenes Modell haben?
  • Sollen beide Spieler ihr eigenes Modell haben?

Wie stellt man das Brett dar?

Das Spielbrett ist ein Vektor aus neun Zahlen, eine für jedes Feld. Die Zahl ist 0, wenn es von Spieler1 oder Spieler2 genutzt werden kann. Sie ist 1, wenn es von Spieler1 genommen wird und 2, wenn es von Spieler1 genommen wird.

Wie wird der Zug dargestellt?

Das ist nicht wirklich wichtig, wir verwenden eine Liste mit Zeilen- und Spaltenpositionen.

Regression oder Klassifizierung und wie verwendet man sie?

Mit der Regression können wir versuchen, einen Wert für den nächsten Zug vorherzusagen.

Mit der Klassifizierung können wir versuchen, einen Vektor der besten Züge vorherzusagen.

Ich wähle hier die Regression. Wir haben zwei Spieler. Die Werte für Spieler 1:

  • 2: gewonnen
  • 1: unentschieden
  • 0: verloren

Die Vorhersage wird ein Wert zwischen 2 und 0 sein. Wenn wir am Zug sind, sagen wir den Wert für alle verfügbaren Züge voraus. Dann wählen wir den besten verfügbaren Wert, d.h. das Maximum. Daraus ergibt sich unser Zug. Für Spieler 2 ist der beste verfügbare Wert das Minimum.

MLP (Multilayer Precepion) oder LSTM (Long Short Term Memory) oder etwas anderes?

Ich weiß es nicht, versuchen wir es mit LSTM.

Jeder Zug hat sein eigenes Modell?

Ich denke, das ist wichtig. Wenn wir nur ein Modell haben, dann sind die Daten nach Schritt N auch enthalten. Das scheint völlig falsch zu sein.

Sollten beide Spieler ihr eigenes Modell haben?

Ich denke ja. Spieler1 ist immer einen Zug voraus, Spieler2 ist immer 1 Zug zurück.

Trainingsdaten

Wir verwenden Regression, siehe oben, um einen Wert für jeden möglichen Zug zu einem bestimmten Zeitpunkt zu generieren. Spieler1 wählt den Zug mit dem höchsten Wert, der Gegner, Spieler2 wählt den Zug mit dem niedrigsten Wert.

Das Brett ist ein Vektor aus neun Feldern. Die Felder können leer sein, X für Spieler1 und O für Spieler2. Ein Spiel besteht aus mehreren Vektoren. Wir ordnen das Ergebnis des Spiels allen Vektoren eines Spiels zu.

Zum Beispiel sehen die Daten für ein Spiel so aus:

[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

Informationen zu LSTM finden Sie unter 'How to Develop LSTM Models for Time Series Forecasting', siehe Links unten. Das Modell ist ein multivariate LSTM mit n_steps_in=2 und n_steps_out=1.

Um die Trainingsdaten zu generieren, spielen wir das Spiel viele Male.

Daten von nur einmaligen Spielen

Um unser Modell zu trainieren, erzeugen wir Daten, indem wir eine Reihe von Partien spielen. Dies geschieht mit zufälligen Zügen. Das bedeutet, dass wir viele doppelte Spiele in unserem Datensatz haben können, mit anderen Worten, der Datensatz ist verunreinigt. Im Moment stelle ich sicher, dass es keine doppelten Partien gibt, indem ich eine Signatur des Brettes und des Endergebnisses verwende.

Ein Modell für jeden Zug

Wenn wir ein einziges Modell verwenden, werden die Trainingsdaten mit zukünftigen Daten "verunreinigt". Wenn wir am Zug sind, wollen wir wissen, was der nächste beste Zug ist. Alles, was nach diesem Schritt kommt, verschmutzt unsere vorhandenen Daten. Aus diesem Grund verwende ich mehrere Modelle, eines für jeden Schritt.

move[n]    model[n] with data upto step[n+1]
move[n+1]  model[n+1] with data upto step[n+2]
etc.

Für Spieler 1 bedeutet dies, dass wir bei Zug[n] das Modell[n] verwenden, das mit Daten bis zum Zug n+1 trainiert wurde. Auf diese Weise können wir den besten verfügbaren Zug auswählen.

Der Parameter n_steps_in=2 bedeutet, dass wir kein Modell für den ersten Zug haben. Wir machen den ersten Zug zu einem Zufallszug, für beide Spieler.

Wir verwenden auch kein Modell, wenn nur noch ein Zug übrig ist.

Leistung

Ok, ich habe das implementiert. Wie ist die Leistung? Das Trainingsergebnis zeigt für alle Modelle, dass der mittlere_absolute_Fehler von etwa 0,8 auf 0,6 reduziert wurde. Das ist nicht sehr gut.

In den Ergebnissen unten habe ich die beiden Spieler. Ein Spieler kann sein:

  • RD: macht zufällige Züge
  • NN: macht Neural Network Züge

Der erste Spieler ist Spieler1, der zweite Spieler ist Spieler2. Die Trainingsdaten werden wie oben beschrieben erzeugt. Sie werden so lange generiert, bis wir zum Beispiel 1000 x gewonnen-gezogen-verloren = 1000xgewonnen, 1000xverloren, und 1000xgezogen haben.

1. RD gegen RD

Beide Spieler machen zufällige Züge.

Ergebnisse von 4 Durchgängen mit 1000 Spielen:

+-------+-------+-------+----------+-----------+-----------+
| 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% |

Das sieht nicht unvernünftig aus. Spieler1 beginnt das Spiel und hat somit einen Vorteil gegenüber Spieler2.

2. NN gegen RD, Zug mit 1000 x gewonnen-gezogen-verloren

Spieler1 macht Neural Network Züge, Spieler2 macht zufällige Züge.

Ergebnisse von 4 Durchläufen mit 1000 Spielen:

+-------+-------+-------+----------+-----------+-----------+
| 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% |

Besser als zufällige Züge, aber noch lange nicht perfekt!

3. NN gegen RD, Zug mit 2000 x gewonnen-gezogen-verloren

Spieler1 macht Neural Network Züge, Spieler2 macht zufällige Züge.

Ergebnisse von 4 Durchläufen mit 1000 Spielen:

+-------+-------+-------+----------+-----------+-----------+
| 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% |

Wieder besser, aber noch lange nicht perfekt!

4. NN gegen RD, Zug mit 5000 x gewonnen-gezogen-verloren

Spieler1 macht Neural Network Züge, Spieler2 macht zufällige Züge.

Ergebnisse von 4 Durchläufen mit 1000 Spielen:

+-------+-------+-------+----------+-----------+-----------+
| 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% |

Das sieht schon besser aus! Können wir es besser machen?

5. NN gegen RD, Training mit 20000 x gewonnen-gezogen-verloren

Spieler1 macht Neural Network Züge, Spieler2 macht zufällige Züge.

Ergebnisse von 4 Durchläufen mit 1000 Spielen:

+-------+-------+-------+----------+-----------+-----------+
| 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% |

Enorme Verbesserung, mehr (Trainings-)Daten sind wichtig! Sind die Siege von Spieler2 nur Glück?

6. RD vs NN, trainieren mit 20000 x gewonnen-gezogen-verloren

Jetzt ändern wir die Reihenfolge. Spieler1 macht zufällige Züge und Spieler2 macht Neural Network Züge.

Ergebnisse von 4 Durchläufen mit 1000 Spielen:

+-------+-------+-------+----------+-----------+-----------+
| 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% |

Dies scheint vernünftig zu sein. Die Ergebnisse für Spieler2 sind nicht so gut wie die von Spieler1 oben. Auch die Anzahl der Unentschieden ist gestiegen. Hat das damit zu tun, dass Spieler1 als Erster beginnt?

7. NN gegen NN, trainieren mit 20000 x gewonnen-gezogen-verloren

Beide Spieler machen Neural Network Züge!

Ergebnisse der Läufe von 1000 Spielen:

+-------+-------+-------+----------+-----------+-----------+
| 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% |

Wir erwarten, dass Gewinn und Verlust nahe beieinander liegen, aber das ist nicht der Fall. Wir erwarten auch, dass es viel mehr Unentschieden gibt. Das sieht gut aus.

Wir können nur schlussfolgern: Unsere Blackbox ist nicht intelligent genug ... :-(

Der Code

Nachfolgend der Code, damit Sie es selbst versuchen können. Keras Tuner wird verwendet, um die hyperparameters zu optimieren.

Wichtige Variablen:

  • tuner_dir
    Dies ist das von Keras Tuner erstellte Verzeichnis.
  • must_train
    Setzen Sie True, wenn Sie die Modelle trainieren wollen.
    Setzen Sie False, wenn Sie die trainierten Modelle verwenden wollen.
  • won_draw_lost_count
    Hier geht es um die Trainingsdaten, siehe oben.

Normalerweise wollen Sie einmal trainieren und dann mehrere Durchläufe machen. Wenn Sie won_draw_lost_count ändern, stellen Sie sicher, dass Sie zuerst das Verzeichnis tuner_dir löschen! Eine Erhöhung von won_draw_lost_count erhöht die Trainingszeit.

# 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,
)

Verbesserung der Leistung

Wir können auf folgende Weise versuchen, die Leistung zu verbessern:

  • mehr Trainingsdaten hinzufügen
  • Hinzufügen von mehr hyperparameter -Auswahlen
  • Hinzufügen weiterer hyperparameter -Auswahlmöglichkeiten
  • Hinzufügen weiterer hyperparameters zu den Modellen, z. B. Lernrate
  • Hinzufügen zusätzlicher Schichten zu den Modellen
  • Überspringen früher Züge, wodurch die Trainingsdaten um

Es wäre schön, Statistiken zu implementieren, die auch zeigen, wie viele Partien in 5, 6, 7, 8 oder 9 Zügen beendet wurden.

Zusammenfassung

Die Verwendung von Deep Learning auf diese Weise ist nicht die Lösung, um dieses Spiel zu lösen. Ich wusste das, als ich anfing, aber ich wollte es trotzdem erst einmal versuchen, bevor ich mich mit Reinforcement Learning beschäftige. Es gibt eine Menge möglicher Verbesserungen, und ich werde in Zukunft sicherlich einige ausprobieren. Die Verwendung von Keras Tuner zum Tunen der hyperparameters hat mir das Leben wieder leichter gemacht. Das war ein schönes Projekt, aber auch eine Menge Arbeit. Trotzdem habe ich viel gelernt.

Links / Impressum

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

Einen Kommentar hinterlassen

Kommentieren Sie anonym oder melden Sie sich zum Kommentieren an.

Kommentare

Eine Antwort hinterlassen

Antworten Sie anonym oder melden Sie sich an, um zu antworten.