andere opgaven: acht koninginnen | boter, kaas en eieren | logiquiz | sudoku | laatste wint

Boter, kaas en eieren

Op deze webpagina wordt uitgelegd hoe een computer onverslaanbaar kan worden gemaakt met het spelletje boter, kaas en eieren (andere benamingen: 'kruisje rondje', 'tik-tak-tor', 'tic-tac-toe').

Inhoud:
het spel
benadering
programma afloop
code

Het spel:

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.).

Benadering:

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.

Programma afloop:

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.

De code



#!/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()