Een poging om Tic-Tac-Toe op te lossen met behulp van Keras en LSTM
Deep Learning is niet de manier om Tic-Tac-Toe op te lossen, maar het is zeker een leuke leerzame ervaring.
Na het implementeren van mijn eerste Deep Learning LSTM model voor een project zat ik te denken of Deep Learning ook een spelletje kon oplossen. Het eerste spel dat in je opkomt is Tic-Tac-Toe. Dan zoek je op internet en er blijken heel veel mensen te zijn die hetzelfde idee hadden. Natuurlijk.
Hieronder presenteer ik mijn oplossing om Tic-Tac-Toe op te lossen met behulp van Keras en LSTM (Long Short Term Memory). Het gaat hier om Deep Learning en niet om een Reinforcement Learning oplossing, dat is een heel ander onderwerp.
De oplossing gebruikt niet één model, maar een model voor elke zet. Waarom? Omdat ik wilde voorkomen dat de trainingsgegevens voor een vroege zet 'vervuild' worden met trainingsgegevens voor toekomstige zetten.
Over het Tic-Tac-Toe spel
Er zijn 255168 manieren om dit spel te spelen. Van deze spellen worden er 131184 gewonnen door de eerste speler, 77904 gaan naar de tegenstander, en 46080 eindigen in een gelijkspel.
Een bord bestaat uit velden met de inhoud leeg, X, en O. Het totaal aantal mogelijke borden is 3^9 = 19.683.
Wat we weten over het Tic-Tac-Toe spel
Onze Deep Learning black box weet het volgende over het spel:
- Er zijn twee spelers
- Het wordt gespeeld op 9 velden, laten we het een bord noemen
- De spelers doen om de beurt een zet
- Een zet doen betekent een ongebruikt veld aan een speler toewijzen
- Dit betekent dat we weten welke velden beschikbaar zijn als we een zet doen
- Na een aantal zetten vertelt iemand ons dat het spel voorbij is en wie er gewonnen, verloren of gelijk gespeeld heeft
Dat is alles wat we weten, niet echt veel. Kunnen we Deep Learning gebruiken om winnende partijen te spelen?
Enkele vragen en antwoorden
- Hoe stellen we het bord voor?
- Hoe stellen we een zet voor?
- Moeten we regressie of classificatie gebruiken en hoe?
- Moeten we MLP (Multilayer Precepion) of LSTM (Long Short Trem Memory) of iets anders gebruiken?
- Moet elke zet een eigen model hebben?
- Moeten beide spelers hun eigen model hebben?
Hoe moet het bord worden voorgesteld?
Het bord is een vector van negen getallen, één voor elk veld. Het getal is 0 als het gebruikt kan worden door speler1 of speler2. Het is 1 als het door speler1 wordt genomen en 2 als het door speler1 wordt genomen.
Hoe wordt de zet weergegeven?
Dit is niet echt belangrijk, laten we een lijst gebruiken met een rij en kolom positie.
Regressie of classificatie en hoe gebruiken we het?
Met regressie kunnen we proberen een waarde voor de volgende zet te voorspellen.
Met classificatie kunnen we proberen een vector van beste zetten te voorspellen.
Ik kies hier voor regressie. We hebben twee spelers. De waarden voor speler1:
- 2: gewonnen
- 1: gelijkspel
- 0: verloren
De voorspelling zal een waarde zijn tussen 2 en 0. Als het onze beurt is, voorspellen we de waarde voor alle beschikbare zetten. Dan kiezen we de beste beschikbare waarde, dat is het maximum. Voor speler 2 is de beste beschikbare waarde het minimum.
MLP (Multilayer Precepion) of LSTM (Long Short Term Memory) of iets anders?
Ik weet het niet, laten we LSTM proberen.
Elke zet heeft zijn eigen model?
Ik denk dat dit belangrijk is. Als we maar één model hebben, dan worden de gegevens na stap N ook meegenomen. Dat lijkt helemaal verkeerd.
Moeten beide spelers een eigen model hebben?
Ik denk van wel. Speler1 staat altijd 1 zet voor, speler2 staat altijd 1 zet achter.
Trainings gegevens
We gebruiken regressie, zie boven, om een waarde te genereren voor elke mogelijke zet op een bepaald moment. Speler1 kiest de zet met de maximale waarde, de tegenspeler, speler2 kiest de zet met de minimale waarde.
Het bord is een vector van negen velden. De velden kunnen leeg zijn, X voor speler1 en O voor speler2. Een spel bestaat uit meerdere vectoren. We kennen de uitkomst van het spel toe aan alle vectoren van een spel.
Bijvoorbeeld, de gegevens voor een spel zien er als volgt uit:
[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
Voor informatie over LSTM , zie "Hoe LSTM modellen voor tijdreeksprognoses te ontwikkelen", zie onderstaande links. Het model is een multivariate LSTM met n_steps_in=2 en n_steps_out=1.
Om de trainingsdata te genereren spelen we het spel vele malen.
Alleen gegevens van unieke spellen
Om ons model te trainen genereren we data door een aantal spellen te spelen. We doen dit met behulp van willekeurige zetten. Dit betekent dat we veel dubbele spellen in onze dataset kunnen hebben, met andere woorden, de dataset is vervuild. Op dit moment zorg ik ervoor dat er geen dubbele partijen zijn, door gebruik te maken van een handtekening van het bord en het eindresultaat.
Een model voor elke zet
Als we een enkel model gebruiken, worden de trainingsgegevens "vervuild" met toekomstige gegevens. Als wij aan zet zijn, willen we weten wat de volgende beste zet is. Alles na die stap vervuilt onze bestaande gegevens. Daarom gebruik ik meerdere modellen, één voor elke stap.
move[n] model[n] with data upto step[n+1]
move[n+1] model[n+1] with data upto step[n+2]
etc.
Voor speler 1 betekent dit dat we bij zet[n] model[n] gebruiken dat getraind is met gegevens tot en met zet n+1. Op deze manier kunnen we de beste beschikbare zet kiezen om te doen.
De parameter n_steps_in=2 betekent dat we geen model hebben voor de eerste zet. Wat we doen is de eerste zet een willekeurige zet maken, voor beide spelers.
Ook gebruiken we geen model als er nog maar één zet over is.
Prestatie
Ok, ik heb dit geïmplementeerd. Hoe presteert het? Het trainingsresultaat laat voor alle modellen zien dat de gemiddelde_absolute_error is teruggebracht van ongeveer 0.8 naar 0.6. Niet erg goed.
In de resultaten hieronder heb ik de twee spelers. Een speler kan zijn:
- RD: doet willekeurige zetten
- NN: doet Neural Network zetten
De eerste speler is speler1, de tweede speler is speler2. Trainingsgegevens worden gegenereerd zoals hierboven beschreven. Het wordt gegenereerd totdat we bijvoorbeeld 1000 x gewonnen-getrokken-verloren = 1000xgewonnen, 1000xverloren, en 1000xgetrokken hebben.
1. RD vs RD
Beide spelers doen willekeurige zetten.
Resultaten van 4 ronden van 1000 spellen:
+-------+-------+-------+----------+-----------+-----------+
| 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% |
Dit ziet er niet onredelijk uit. Speler1 begint het spel en heeft dus een voordeel op speler2.
2. NN vs RD, trainen met 1000 x gewonnen-getrokken-verloren
Speler1 doet Neural Network zetten, speler2 doet willekeurige zetten.
Resultaten van 4 runs van 1000 spellen:
+-------+-------+-------+----------+-----------+-----------+
| 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% |
Beter dan willekeurige zetten, maar verre van perfect!
3. NN vs RD, trainen met 2000 x gewonnen-getrokken-verloren
Speler1 doet Neural Network zetten, speler2 doet willekeurige zetten.
Resultaten van 4 runs van 1000 spellen:
+-------+-------+-------+----------+-----------+-----------+
| 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% |
Weer beter, maar weer verre van perfect!
4. NN vs RD, trainen met 5000 x gewonnen-getrokken-verloren
Speler1 doet Neural Network zetten, speler2 doet willekeurige zetten.
Resultaten van 4 runs van 1000 spellen:
+-------+-------+-------+----------+-----------+-----------+
| 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% |
Dit lijkt er meer op! Kunnen we het beter doen?
5. NN vs RD, trainen met 20000 x gewonnen-getrokken-verloren
Speler1 doet Neural Network zetten, speler2 doet willekeurige zetten.
Resultaten van 4 runs van 1000 spellen:
+-------+-------+-------+----------+-----------+-----------+
| 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 verbetering, meer (training) data is belangrijk! Zijn de overwinningen van speler2 gewoon geluk?
6. RD vs NN, trainen met 20000 x gewonnen-gelijkspel-verloren
Nu veranderen we de volgorde. Speler1 doet willekeurige zetten en speler2 doet Neural Network zetten.
Resultaten van 4 runs van 1000 spellen:
+-------+-------+-------+----------+-----------+-----------+
| 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% |
Dit lijkt redelijk. De resultaten voor speler2 zijn niet zo goed als voor speler1 hierboven. Ook het aantal remises is toegenomen. Heeft dit te maken met het feit dat speler1 als eerste begint?
7. NN vs NN, trainen met 20000 x gewonnen-trekking-verloren
Beide spelers doen Neural Network zetten!
Resultaten van runs van 1000 spellen:
+-------+-------+-------+----------+-----------+-----------+
| 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% |
We verwachten dat gewonnen en verloren dicht bij elkaar liggen, maar dat is niet het geval. We verwachten ook veel meer remises te zien. Dat ziet er goed uit.
We kunnen alleen maar concluderen: Onze black box is niet slim genoeg ... :-(
De code
Hieronder staat de code, zodat u het zelf kunt proberen. Keras Tuner wordt gebruikt om de hyperparameters te optimaliseren.
Belangrijke variabelen:
- tuner_dir
Dit is de directory die door Keras Tuner wordt aangemaakt. - must_train
Stel True in als u de modellen wilt trainen.
Stel False in als u de getrainde modellen wilt gebruiken. - won_draw_lost_count
Dit gaat over de trainingsdata, zie hierboven.
Typisch wil je één keer trainen en dan meerdere runs doen. Als je won_draw_lost_count wijzigt, zorg er dan voor dat je eerst de directory tuner_dir verwijdert! Het verhogen van won_draw_lost_count zal de trainingstijd verhogen.
# 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,
)
Verbeteren van de prestatie
We kunnen de performance op de volgende manieren proberen te verbeteren:
- meer trainingsdata toevoegen
- voeg meer hyperparameter keuzes toe
- meer hyperparameter keuzen toevoegen
- meer hyperparameter's aan de modellen toevoegen, zoals leersnelheid
- extra lagen aan de modellen toevoegen
- vroege zetten overslaan, waardoor de trainingsgegevens met
Het zou mooi zijn om statistieken te implementeren die ook laten zien hoeveel partijen in 5, 6, 7, 8, of 9 zetten voltooid zijn.
Samenvatting
Het gebruik van Deep Learning op deze manier is niet de oplossing om dit spel op te lossen. Ik wist dit toen ik begon, maar ik wilde dit toch eerst proberen voordat ik me ging verdiepen in Reinforcement Learning. Er zijn veel verbeteringen mogelijk en ik zal er in de toekomst zeker een aantal uitproberen. Het gebruik van Keras Tuner om de hyperparameters te tunen maakte mijn leven weer een stuk gemakkelijker. Dit was een leuk project maar ook een hoop werk. Maar wel veel geleerd.
Links / credits
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
Lees meer
Deep Learning Machine Learning
Recent
- Database UUID primaire sleutels van je webapplicatie verbergen
- Don't Repeat Yourself (DRY) met Jinja2
- SQLAlchemy, PostgreSQL, maximum aantal rijen per user
- Toon de waarden in SQLAlchemy dynamische filters
- Veilige gegevensoverdracht met Public Key versleuteling en pyNaCl
- rqlite: een alternatief voor SQLite met hoge beschikbaarheid en distributed
Meest bekeken
- Met behulp van Python's pyOpenSSL om SSL-certificaten die van een host zijn gedownload te controleren
- Gebruik van UUIDs in plaats van Integer Autoincrement Primary Keys met SQLAlchemy en MariaDb
- Maak verbinding met een dienst op een Docker host vanaf een Docker container
- PyInstaller en Cython gebruiken om een Python executable te maken
- SQLAlchemy: Gebruik van Cascade Deletes om verwante objecten te verwijderen
- Flask RESTful API verzoekparametervalidatie met Marshmallow-schema's