Benutzer-Werkzeuge
Seitenleiste
Dies ist eine alte Version des Dokuments!
Hinweise von Stefan Born Für das Spiel fällt mir zweierlei ein:
Tic-Tac-Toe hat einen so kleinen Zustandsraum, dass man das Spiel 'lösen', also mit einem Backtracking-Algorithmus einen optimalen Zug finden kann. So ähnlich kann man es noch bis etwa zur Größe von 'Mühle' machen, dann geht das nicht mehr.
Für komplexere Spiele wird man so etwas wie 'deep Q-Learning' brauchen. einige Quellen u.a. das Buch von Sutton und Barto über Reinforcemen Learning, dass die grundlegenden Ideen von Reinforcement Learning gut erklärt.
Protokoll für den 21.11.2019
Wir haben uns mit einem Backtracking-Algorithmus auseinander gesetzt und teilweise versucht ihn anzuwenden und außerdem ein TicTacToe Spiel anhand der Turtle angefangen zu Programmieren.
Protokoll für den 28.11.2019
Heute haben wir mit der Turtle erflogreich ein TicTacToe-Spiel programmiert welches zwei Spieler gegeneinander spielen lässt und uns mit dem Thema „Reinforcement Learning“ auseinander gesetzt.
Protokoll für den 05.12.2019
Anfangs infomierten wir uns noch in Bezug zu „Reinforcement Learning“ und einigten uns recht schnell darauf den Gegner mit Q-Learning zu entwickeln. Daraufhin haben wir uns mit der Methode intensiver beschäftigt und auch schon einen ersten Plan mithilfe des Buches von Richard S. Sutton „Reinforcement Learning An Introduction second edition“ für den Spieler vom Tic-Tac-Toe-Spiel aufgestellt. Reinforcemts Learning funktioniert indem ein „Agent“ auf seine Umgebung reagiert und für seine Handlung belohnt oder bestraft wird. Er handelt entweder zufällig oder in dem Interesse eine Aktion durchzuführen, welche die größte Belohnung gibt. Beide Handlungsmöglichkeiten sind wichtig, da der Agent auch durch schlechte Aktionen dazulernt. Um den Computer dazu zu bringen so zu lernen, werden wir es mit der q-Formel versuchen, welche anhand seiner Aktionen die Bewertung für die Aktionen, die anfangs noch sehr ungenau sind, spezialisiert. In den nächsten Stunden werden wir uns dann damit beschäftigen wie man das auch in die Tat umsetzen kann.
Protokoll für den 19.12.2019
Eine Woche vor Weihnachten haben wir nun einen selbstlernendem Gegner, den wir im Internet gefunden haben (https://github.com/agrawal-rohit/playing-games-with-python/blob/master/Tic%20Tac%20Toe/training_(AIvsAI)_ReinforcementLearning.py), versucht in Bens TikTakToe Spiel einzubauen. Außerdem haben wir schon angefangen den Computer aus dem Internet zu analysieren und auf ein „vier gewinnt“ Spiel zu übertragen. Für die nächsten Wochen haben wir uns vorgenommen, zum einen ein „vier gewinnt“ Spiel mit der Turtle zu schreiben, dass sich ähnlich wie Bens TicTacToe-Spiel verhält und zum anderen den Computeer weiter zu analysieren und anfangen ein AI für ein „vier gewinnt“ zu schreiben. Bens TicTacToe-Spiel: import turtle as t import numpy as np tttmatrix=np.zeros(9) tttmatrix=tttmatrix.reshape1) kreuz = 0 Anzahl = 0 spielende = 10 siegkreuz = 0 siegkreis = 0 keinsieg = 0 start = t.Turtle() start.speed(0) def neuanfang():
global spielende
global siegkreis
global siegkreuz
global keinsieg
global tttmatrix
global Anzahl
if(spielende!=10):
start.up()
start.clear()
start.setx(-2)
start.hideturtle()
start.write(siegkreuz)
start.sety(start.ycor()+2)
start.write(siegkreis)
start.sety(start.ycor()+2)
start.write(keinsieg)
start.goto(0,0)
tttmatrix=0
tttmatrix=np.zeros(9)
tttmatrix=tttmatrix.reshape((3, 3))
spielende = 10
t.clear()
Anzahl = 0
def kreismalen(t):
t.up() t.right(90) t.forward(4) t.left(90) t.down() t.circle(4)
def kreuzmalen(t):
t.left(45) t.forward(5) t.backward(10) t.forward(5) t.left(90) t.forward(5) t.backward(10) t.forward(5) t.right(135)
def tttfeld():
"""
Malt ein 3x3 Feld.
"""
t.setworldcoordinates(0,30,30,0)
spalten = t.Turtle()
spalten.left(90)
zeilen = t.Turtle()
spalten.speed(0)
zeilen.speed(0)
spalten.hideturtle()
zeilen.hideturtle()
for i in range(4):
spalten.setx(i*10)
zeilen.sety(i*10)
spalten.forward(30)
zeilen.forward(30)
spalten.sety(0)
zeilen.setx(0)
zeilen.goto(0,0)
spalten.goto(0,0)
zeilen.up()
zeilen.setx(-3)
zeilen.write("Siege von Kreuz:", align="right")
zeilen.sety(zeilen.ycor()+2)
zeilen.write("Siege von Kreis:", align="right")
zeilen.sety(zeilen.ycor()+2)
zeilen.write("Unentschieden:", align="right")
zeilen.goto(0,0)
zeilen.down()
def ende():
zeile = np.sum(tttmatrix, axis=1)
spalte = np.sum(tttmatrix, axis=0)
diagonale1 = tttmatrix[0, 0]+tttmatrix[1, 1]+tttmatrix[2, 2]
diagonale2 = tttmatrix[2, 0]+tttmatrix[1, 1]+tttmatrix[0, 2]
if(3 in zeile or 3 in spalte or 3==diagonale1 or 3==diagonale2):
return 1
elif(-3 in zeile or -3 in spalte or -3==diagonale1 or -3==diagonale2):
return -1
else:
return 0
def malen(x, y):
global kreuz
global Anzahl
global spielende
global siegkreis
global siegkreuz
global keinsieg
global tttmatrix
if(x <=10):
spalte = 0
if(x >10 and x <=20):
spalte = 1
if(x >20 and x <=30):
spalte = 2
if(y <=10):
zeile = 0
if(y >10 and y <=20):
zeile = 1
if(y >20 and y <=30):
zeile = 2
t.up()
t.setx(spalte*10+5)
t.sety(zeile*10+5)
t.down()
if(tttmatrix[zeile, spalte]==0 and spielende==10):
Anzahl = Anzahl + 1
if(kreuz==0):
kreuzmalen(t)
kreuz = 1
tttmatrix[zeile, spalte]=1
if(ende()==1):
t.up()
t.goto(15,15)
t.write("Kreuz hat gewonnen", align="center", font=("Arial", 32, "normal"))
spielende = 1
siegkreuz = siegkreuz +1
t.down()
else:
kreismalen(t)
kreuz = 0
tttmatrix[zeile, spalte]=-1
if(ende()==-1):
t.up()
t.goto(15,15)
t.write("Kreis hat gewonnen", align="center", font=("Arial", 32, "normal"))
spielende = -1
siegkreis = siegkreis +1
t.down()
if(Anzahl==9 and ende()==0):
t.up()
t.goto(15,15)
t.write("Unentschieden", align="center", font=("Arial", 32, "normal"))
spielende = 0
keinsieg = keinsieg +1
t.down()
tttfeld() t.speed(0) t.hideturtle() screen=t.Screen() screen.onclick(t.goto) screen.onclick(malen) screen.onkeypress(neuanfang, „space“) screen.listen() t.mainloop() t.exitonclick()
09.01.2020: Nicht funktionierender Code mit selbstlernendem Gegner:
import turtle as t
import numpy as np
from math import inf as infinity
import itertools
import random
def play_move(state, player, block_num):
if state[int((block_num-1)/3)][(block_num-1)%3] is ' ':
state[int((block_num-1)/3)][(block_num-1)%3] = player
if(player == 'X'):
printX(int((block_num-1)/3), (block_num-1)%3)
else:
print0(int((block_num-1)/3), (block_num-1)%3)
def copy_game_state(state):
new_state = [[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]
for i in range(3):
for j in range(3):
new_state[i][j] = state[i][j]
return new_state
def check_current_state(game_state):
# Check horizontals
if (game_state[0][0] == game_state[0][1] and game_state[0][1] == game_state[0][2] and game_state[0][0] is not ' '):
return game_state[0][0], "Done"
if (game_state[1][0] == game_state[1][1] and game_state[1][1] == game_state[1][2] and game_state[1][0] is not ' '):
return game_state[1][0], "Done"
if (game_state[2][0] == game_state[2][1] and game_state[2][1] == game_state[2][2] and game_state[2][0] is not ' '):
return game_state[2][0], "Done"
# Check verticals
if (game_state[0][0] == game_state[1][0] and game_state[1][0] == game_state[2][0] and game_state[0][0] is not ' '):
return game_state[0][0], "Done"
if (game_state[0][1] == game_state[1][1] and game_state[1][1] == game_state[2][1] and game_state[0][1] is not ' '):
return game_state[0][1], "Done"
if (game_state[0][2] == game_state[1][2] and game_state[1][2] == game_state[2][2] and game_state[0][2] is not ' '):
return game_state[0][2], "Done"
# Check diagonals
if (game_state[0][0] == game_state[1][1] and game_state[1][1] == game_state[2][2] and game_state[0][0] is not ' '):
return game_state[1][1], "Done"
if (game_state[2][0] == game_state[1][1] and game_state[1][1] == game_state[0][2] and game_state[2][0] is not ' '):
return game_state[1][1], "Done"
# Check if draw
draw_flag = 0
for i in range(3):
for j in range(3):
if game_state[i][j] is ' ':
draw_flag = 1
if draw_flag is 0:
return None, "Draw"
return None, "Not Done"
def comstarts():
global playerChoice
newGame('O')
playerChoice = 0
def playerstarts():
global playerChoice
newGame('X')
playerChoice = 1
def newGame(player_choice):
global NoWin
global WinsPlayer
global WinsCom
if(check_current_state(game_state)== "Done" or NoWin == 0 and WinsPlayer == 0 and WinsCom == 0):
start.up()
start.clear()
start.setx(-2)
start.hideturtle()
start.write(WinsPlayer)
start.sety(start.ycor()+2)
start.write(WinsCom)
start.sety(start.ycor()+2)
start.write(NoWin)
t.clear()
if(player_choice == 'O'):
block_choice = getBestMove(game_state, players[0])
play_move(game_state ,players[0], block_choice)
def wheretogo(x, y):
'''
prüft, wo der Spieler hinklickt und gibt je nachdem eine Zahl zwischen 1 und 9 zurück.
'''
global game_state
if(x > 0 and x <=10):
spalte = 1
if(x >10 and x <=20):
spalte = 2
if(x >20 and x <=30):
spalte = 3
if(y > 0 and y <=10):
zeile = 0
if(y >10 and y <=20):
zeile = 1
if(y >20 and y <=30):
zeile = 2
block_choice = 3*zeile +spalte
if(game_state[int((block_choice-1)/3)][(block_choice-1)%3] == ' '):
t.up()
t.setx((spalte-1)*10+5)
t.sety(zeile*10+5)
game(block_choice)
def printX(zeile, spalte):
t.up()
t.setx(spalte*10+5)
t.sety(zeile*10+5)
t.down()
t.left(45)
t.forward(5)
t.backward(10)
t.forward(5)
t.left(90)
t.forward(5)
t.backward(10)
t.forward(5)
t.right(135)
t.up()
def print0(zeile, spalte):
t.up()
t.setx(spalte*10+5)
t.sety(zeile*10+5)
t.down()
t.up()
t.right(90)
t.forward(4)
t.left(90)
t.down()
t.circle(4)
t.up()
def tttfeld():
"""
Malt ein 3x3 Feld.
"""
t.setworldcoordinates(0,30,30,0)
spalten = t.Turtle()
spalten.left(90)
zeilen = t.Turtle()
spalten.speed(0)
zeilen.speed(0)
spalten.hideturtle()
zeilen.hideturtle()
for i in range(4):
spalten.setx(i*10)
zeilen.sety(i*10)
spalten.forward(30)
zeilen.forward(30)
spalten.sety(0)
zeilen.setx(0)
zeilen.goto(0,0)
spalten.goto(0,0)
zeilen.up()
zeilen.setx(-3)
zeilen.write("Siege vom Spieler:", align="right")
zeilen.sety(zeilen.ycor()+2)
zeilen.write("Siege vom Computer:", align="right")
zeilen.sety(zeilen.ycor()+2)
zeilen.write("Unentschieden:", align="right")
zeilen.goto(0,0)
zeilen.goto(31,15)
zeilen.write("Wer soll anfangen? Du(X) oder der Computer(O)?", align="left", font=("Arial", 8, "normal"))
zeilen.down()
def update_state_value(curr_state_idx, next_state_idx, learning_rate):
new_value = state_values_for_AI[curr_state_idx] + learning_rate*(state_values_for_AI[next_state_idx] - state_values_for_AI[curr_state_idx])
state_values_for_AI[curr_state_idx] = new_value
def getBestMove(state, player):
'''
Reinforcement Learning Algorithm
'''
moves = []
curr_state_values = []
empty_cells = []
for i in range(3):
for j in range(3):
if state[i][j] is ' ':
empty_cells.append(i*3 + (j+1))
for empty_cell in empty_cells:
moves.append(empty_cell)
new_state = copy_game_state(state)
#play_move(new_state, player, empty_cell)
next_state_idx = list(states_dict.keys())[list(states_dict.values()).index(new_state)]
curr_state_values.append(state_values_for_AI[next_state_idx])
best_move_idx = np.argmax(curr_state_values)
best_move = moves[best_move_idx]
return best_move
def game(block_choice):
global NoWin
global WinsPlayer
global WinsCom
global game_state
global playerChoice
current_player_idx=playerChoice
current_state = "Not Done"
winner = None
if current_player_idx == 0:
player_choice = 'X'
else:
player_choice = 'O'
curr_state_idx = list(states_dict.keys())[list(states_dict.values()).index(game_state)]
if current_player_idx == 0: #Mensch macht ersten Zug
play_move(game_state ,players[current_player_idx], block_choice)
current_player_idx = 1
block_choice = getBestMove(game_state, players[current_player_idx])
play_move(game_state ,players[current_player_idx], block_choice)
else: #Computer macht ersten Zug
play_move(game_state ,players[current_player_idx], block_choice)
current_player_idx = 0
block_choice = getBestMove(game_state, players[current_player_idx])
play_move(game_state ,players[current_player_idx], block_choice)
print(game_state)
winner, current_state = check_current_state(game_state)
if winner is not None:
t.up()
t.goto(15,15)
if(str(winner) == player_choice):
WinsPlayer = WinsPlayer +1
t.write("Du hast gewonnen", align="center", font=("Arial", 32, "normal"))
else:
WinsCom = WinsCom +1
t.write("Du hast verloren", align="center", font=("Arial", 32, "normal"))
t.goto(40,15)
t.write("Wer soll anfangen? Du(X) oder der Computer(O)?", align="left", font=("Arial", 8, "normal"))
if current_state is "Draw":
NoWin = NoWin +1
t.up()
t.goto(15,15)
t.write("Unentschieden", align="center", font=("Arial", 30, "normal"))
t.goto(40,15)
t.write("Wer soll anfangen? Du(X) oder der Computer(O)?", align="left", font=("Arial", 8, "normal"))
# PLaying
# Initialize state values
player = ['X','O',' ']
states_dict = {}
all_possible_states = [[list(i[0:3]),list(i[3:6]),list(i[6:10])] for i in itertools.product(player, repeat = 9)]
n_states = len(all_possible_states) # 2 players, 9 spaces
n_actions = 9 # 9 spaces
state_values_for_AI = np.full((n_states),0.0)
print("n_states = %i \nn_actions = %i"%(n_states, n_actions))
for i in range(n_states):
states_dict[i] = all_possible_states[i]
winner, _ = check_current_state(states_dict[i])
if winner == 'O': # AI won
state_values_for_AI[i] = 1
elif winner == 'X': # AI lost
state_values_for_AI[i] = -1
start = t.Turtle()
start.speed(0)
t.speed(0)
t.hideturtle()
screen=t.Screen()
WinsPlayer = 0
WinsCom = 0
NoWin = 0
playerChoice = 0
game_state = [[' ',' ',' '],
[' ',' ',' '],
[' ',' ',' ']]
players = ['X','O']
current_state = "Not Done"
tttfeld()
#LOAD TRAINED STATE VALUES
state_values_for_AI = np.loadtxt('trained_state_values_O.txt', dtype=np.float64)
screen.onclick(wheretogo)
screen.onkeypress(comstarts, "o")
screen.onkeypress(playerstarts, "x")
screen.listen()
t.mainloop()
t.exitonclick()
Protokoll für den 23.1.2020 Wir haben angefangen eine Funkiton zu schreiben um die umgebung eines neu gesetzten Stein zu prüfen und festzustellen ob dadurch eine Prtei gewinnt. Funktion zum checken von jedem Array: def Summe(self, zeile, spalte): #muss noch mit der umgebung verknüpft werden
for i in range(len(a)-3):
b=a[i:i+4]
if (sum(b)== 4 or sum(b)==-4):
return sum(b)
a=board[:6, s-1:s] #für die Spalte a=np.diagonal(board, s-z) #für die Diagonale a=board[:1] #für die Zeile
Seiten-Werkzeuge
