Inhoud:
- het spel
- benadering
- programma afloop
- code
Dit is het spelletje waarbij je om de beurt een rondje of een kruisje moet zetten, met als doel (als eerste) er drie op een rij te krijgen.
In de film 'War Games' (1983) wordt beweerd dat het voor iedere speler mogelijk moet zijn in een 'remise' te eindigen, oftewel je hoeft nooit te verliezen (zie dit fragment).
Dit heb ik gepoogd in te bouwen in een spel, waarbij de speler (jij) het tegen de computer opneemt. De computer zal niet verliezen (Q.E.D.).
Het doel is dus de 'beste zet' te kunnen laten berekenen door de computer. Het minimax algoritme is hiervoor uitermate geschikt.
Bij het minimax algoritme worden alle mogelijke eindzetten (of tot hoe 'diep' je dan ook wil gaan) gewaardeerd met een waarde (zie onderste rij in de boom). Wint de computer, dan wordt dit gewaardeerd met een hoog getal, bij verlies een groot negatief getal, of anders er tussen in (zie de onderste rij). De tegenspeler (jij) ziet dit echter andersom, en zal uit de verschillende spelsituaties de kleinste kiezen (zie de rij daar boven). Uiteindelijk zal dit resulteren in 1 'beste' zet.
Er wordt gebruik gemaakt van een klasse BKE waarvan een van de methoden ( beste_zet() ) het minimax algoritme bevat. Dat werkt zo:
De structuur (zoals in bovenstaande figuur) is niet van onderaf te bepalen, maar moet van bovenaf worden bepaald. Daartoe wordt van ieder dieper niveau gekeken of de gewenste diepte al bereikt is (of dat dat een eindstand is). Is dat het geval, dan wordt de waarde van dat bord berekend ( waarde_oordeel() ) en de waarde vergeleken met de andere waarden uit die tak; zo niet dan wordt recursief steeds een niveau dieper afgedaald.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# een 'boter-kaas-en-eieren' spel
# dit is een 1 speler spel (speler vs. computer)
# de computer zal tenminste gelijkspelen
# en zal winnen indien de speler een 'fout' begaat
# Om de beste zet te bepalen wordt een minimax algoritme toegepast
from math import inf
import pygame
import random
import sys
pygame.init()
screen = pygame.display.set_mode( (600, 600) )
pygame.display.set_caption("boter, kaas en eieren")
# het bord heeft een layout met posities oplopend van links-naar-rechts, boven-naar-onder:
# 0 1 2
# 3 4 5
# 6 7 8
winnende_lijnen = [[0,1,2],[3,4,5],[6,7,8],[0,3,6,],[1,4,7],[2,5,8],[0,4,8],[2,4,6] ]
bonus_lijnen = [ (0,1,2,5,8), (2,5,8,7,6), (8,7,6,3,0), (6,3,0,1,2) ]
bonus_lijnen = [ (0,1,2,5,8,4), (1,5,8,7,6,4), (8,7,6,4,2,5), (6,3,0,4,8,7) ]
rijen = [ [0,1,2], [3,4,5], [6,7,8] ]
alternatieven = [ [6,3,0,7,4,1,8,5,2], [8,7,6,5,4,3,2,1,0], [2,5,8,1,4,7,0,3,6], [6,7,8,3,4,5,0,1,2], [2,1,0,5,4,3,8,7,6], [8,5,2,7,4,1,6,3,0], [0,3,6,1,4,7,2,5,8] ]
SPELER_1 = 0
COMPUTER = 1
SPELER_LEEG = 9
SPELER_NAAM = { SPELER_1: 'speler (O)', COMPUTER: 'computer (X)' }
SPELER_TEKEN = { SPELER_1: 'O', COMPUTER: 'X' }
VIERKANT_AFM = 100
AFSTX, AFSTY = 100, 100
COORDS = [ (50+AFSTX,50+AFSTY), (150+AFSTX,50+AFSTY), (250+AFSTX,50+AFSTY), (50+AFSTX,150+AFSTY), (150+AFSTX,150+AFSTY), (250+AFSTX,150+AFSTY), (50+AFSTX,250+AFSTY), (150+AFSTX,250+AFSTY), (250+AFSTX,250+AFSTY) ]
BACKGROUND = (192,192,192)
BLACK =(0,0,0)
RED, DARK_RED = (255,0,0), (128,0,0)
GREEN, DARK_GREEN = (0,255,0), (0,128,0)
BLUE = (0,0,255)
YELLOW = (255,255,0)
GREY = (192,192,192)
GRAY = (192,192,192)
def tegenstander(speler):
'''
retourneert de opponent van de gegeven speler
-> speler
<- speler
'''
opp = SPELER_1
if speler == SPELER_1:
opp = COMPUTER
return opp
def alternatieve_zet(bord, zet):
'''
onnderzoekt alternatieve zetten die resulteren het dezelfde gespiegelde/geroteerde bord
-> bord (list of int)
-> oorspronkelijke zet (int)
<- een van de alternatieven zetten (int)
'''
zelfde_indx = []
alternatieve_zetten = [ zet ]
for i in range(len(alternatieven)):
zelfde = alternatieven[i]
zelfde_bord = [ bord[x] for x in zelfde ]
if bord[:9] == zelfde_bord:
zelfde_indx.append(i)
for i in zelfde_indx:
alternatieve_zetten.append(alternatieven[i][zet])
return random.choice(alternatieve_zetten)
class BKE():
'''
class dat een boter-kaas-en-eieren spel beschrijft
'''
def __init__(self, start_speler, posities = [SPELER_LEEG]*9):
if type(start_speler) != int or type(posities) != list:
sys.exit('verkeerde klasse initialisatie')
self._start_speler = start_speler
self._posities = posities
def __str__(self, commentaar=''):
to_string = [ str(x) for x in self._posities ]
to_string = [ x.replace(str(SPELER_LEEG),'.').replace(str(SPELER_1),'O').replace(str(COMPUTER),'X') for x in to_string ]
rijen = [ ' '.join(to_string[i:i+3]) for i in [0, 3, 6] ]
out = rijen[0] + ' | 0 1 2\n' + rijen[1] + ' | 3 4 5' + '\t' + commentaar + '\n' + rijen[2] + ' | 6 7 8\n'
return out
@property
def vrije_posities(self):
vrij = [ pos for pos in [0, 1, 2, 3, 4, 5, 6, 7, 8] if self._posities[pos] == SPELER_LEEG ]
random.shuffle(vrij)
return vrij
@property
def waarde_oordeel(self):
speler = COMPUTER
waarde = []
for winlijn in winnende_lijnen:
reeks = [ self.posities[x] for x in winlijn ]
if reeks.count(speler) == 1 and reeks.count(SPELER_LEEG) == 2:
waarde.append(1)
if reeks.count(speler) == 2 and reeks.count(SPELER_LEEG) == 1:
waarde.append(4)
if reeks == [speler, SPELER_LEEG, speler]:
waarde.append(3)
if reeks.count(speler) == 3:
waarde.append(10)
if reeks.count(tegenstander(speler)) == 2 and reeks.count(SPELER_LEEG) == 1:
waarde.append(-3)
for winlijn in bonus_lijnen:
reeks = [ self.posities[x] for x in winlijn ]
if reeks.count(speler) == 3:
waarde.append(7)
return sum(waarde)
@property
def posities(self):
return self._posities
@property
def start_speler(self):
return self._start_speler
@property
def winnaar(self):
'''
onderzoekt of er een winnende lijn is
retourneert de winnaar (SPELER_1 of COMPUTER), of SPELER_LEEG als er geen winnaar is
'''
for winlijn in winnende_lijnen:
reeks = [ self.posities[x] for x in winlijn ]
for speler in [SPELER_1, COMPUTER]:
if reeks.count(speler) == 3:
return speler
return SPELER_LEEG
def reset(self, start_speler):
self._posities = [SPELER_LEEG]*9
self._start_speler = start_speler
@property
def beurt(self):
return [not self.start_speler, self.start_speler][len(self.vrije_posities) % 2]
@property
def game_over(self):
return self.posities.count(SPELER_LEEG) == 0 \
or self.winnaar == SPELER_1 \
or self.winnaar == COMPUTER
def is_vrije_positie(self, positie):
return positie in self.vrije_posities
def geldige_zet(self, speler, pos):
return speler in [SPELER_1, COMPUTER] and self.is_vrije_positie(pos)
def zet(self, speler, pos):
if self.geldige_zet(speler, pos):
self._posities[pos] = speler
def beste_zet(self, depth, is_max_speler):
'''
retourneert een tuple (positie, bord waarde)
'''
vrije_posities = self.vrije_posities[:]
if self.game_over or depth == 0:
if self.game_over:
if self.winnaar == SPELER_1:
return(None, -1000000)
elif self.winnaar == COMPUTER:
return (None, 1000000)
elif self.winnaar == SPELER_LEEG:
return (None, 0)
else: # depth == 0
return (None, self.waarde_oordeel)
pos = random.choice(vrije_posities)
if is_max_speler:
waarde = -inf
for vrije_pos in vrije_posities:
pos_kopie = self.posities[:]
pos_kopie[vrije_pos] = COMPUTER
nieuwe_waarde = BKE(self.start_speler, pos_kopie).beste_zet(depth-1, False)[1]
if nieuwe_waarde > waarde:
waarde = nieuwe_waarde
pos = vrije_pos
return (pos, waarde)
else:
waarde = inf
for vrije_pos in self.vrije_posities:
pos_kopie = self.posities[:]
pos_kopie[vrije_pos] = SPELER_1
nieuwe_waarde = BKE(self.start_speler, pos_kopie).beste_zet(depth-1, True)[1]
if nieuwe_waarde < waarde:
waarde = nieuwe_waarde
pos = vrije_pos
return (pos, waarde)
def teken_bord(bord_, status):
screen.fill(GRAY)
# teken het raster
pygame.draw.line(screen, DARK_GREEN, [100, 200], [400, 200], 5)
pygame.draw.line(screen, DARK_GREEN, [100, 300], [400, 300], 5)
pygame.draw.line(screen, DARK_GREEN, [200, 100], [200, 400], 5)
pygame.draw.line(screen, DARK_GREEN, [300, 100], [300, 400], 5)
for indx in range(9):
if bord_[indx] == SPELER_LEEG:
pass
else:
myfont = pygame.font.SysFont('Calibri', 100, False, False)
label = myfont.render(SPELER_TEKEN[bord_[indx]], True, BLUE)
label_rect = label.get_rect()
screen.blit(label, (COORDS[indx][0]-label_rect[2]//2, COORDS[indx][1]-label_rect[3]//2))
font = pygame.font.SysFont('MS Comic Sans', 24, False, False)
label = font.render(status[0], True, BLUE)
screen.blit(label, (50,50))
pygame.display.update()
def main():
status = ['', '']
stop = False
startspeler_ = SPELER_1
bord = BKE(startspeler_)
while True:
status[0] = 'nieuw spel'
if bord.start_speler == SPELER_1:
status[0] += '. jij begint'
while not bord.game_over:
teken_bord(bord._posities, status)
if bord.beurt == SPELER_1 and not bord.game_over:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit(0)
if event.type == pygame.KEYDOWN and event.key == pygame.K_ESCAPE:
sys.exit(0)
if event.type == pygame.MOUSEBUTTONDOWN:
clicked = None
posx, posy = event.pos
for indx in range(9):
if posx > COORDS[indx][0]-50 and posx < COORDS[indx][0]+ 50 and posy > COORDS[indx][1]-50 and posy < COORDS[indx][1]+ 50:
clicked = indx
if clicked is not None:
if bord.posities[clicked] == 9:
bord.zet(SPELER_1, clicked)
status[0] = 'Mijn beurt (X)'
break
teken_bord(bord._posities, status)
if bord.beurt == COMPUTER and not bord.game_over:
if bord.posities.count(SPELER_LEEG) == 9:
zet = random.randint(0,8)
else:
zet = bord.beste_zet(6, True)[0]
bord.zet(COMPUTER, zet)
status[0] = 'Jouw beurt (O):'
teken_bord(bord._posities, status)
if bord.game_over:
teken_bord(bord._posities, ['game over. wacht.', ''])
pygame.time.wait(3000)
startspeler_ = tegenstander(bord.start_speler)
bord.reset(startspeler_)
if __name__ == '__main__':
main()
pygame.quit()