© 2010 Hein Pragt

Het spel Reversi (ook wel othello genoemd) is een bordspel voor twee personen dat in 1888 bedacht is door Lewis Waterman in Engeland. Het spel Othello werd later door een Japanner genaamd Goro Hasegawa bedacht in 1971 en James R. Becker ontwikkelde het spel en bracht het op de markt. Het spel is heel bekend geworden op de computer, maar is ook nog steeds als bordspel te koop. Er is een bordspel met de naam Rolit te koop waarmee reversi door vier personen tegelijk gespeeld kan worden. De steentjes zijn bij deze variant balletjes die in vier standen op het bord kunnen worden gelegd, met een bepaalde kleur boven. Het spel leent zich ook perfect voor de computer en aangezien de spelregels vrij simpel zijn is het ook snel en eenvoudig te implementeren. Het spel is in bijna elke programmeertaal gemaakt en er zijn ook veel online versies van het spel. Aangezien javascript en flash script niet uitblinken in snelheid zijn de meeste van deze programma's niet erg sterk en hebben ze meestal een 2 ply (spelzet niveau) min/max berekening met soms wat uitbreidingen met tabellen met veld waarden. Maar deze programma's zijn vaak te gretig in het veroveren van stukken waardoor ze met een beetje tactiek al snel verliezen. De wat betere versies van het programma zijn tegenwoordig in java geschreven maar zoals voor elk spel opgaat is de taal C en C++ natuurlijk de meest voor de hand liggende keuze als het om snelheid gaat. Er zijn veel versies van het spel verkrijgbaar op het web, betaalde versies en gratis versies met verschillende sterkte en mogelijkheden. Ook is het spel voor veel mobiele telefoons te downloaden. Het spel werd bij de eerste Microsoft Windows versies gratis meegeleverd, in de laatste versies van Microsoft Windows ontbreekt het spel helaas. Mijn versies van het programma's zullen niet wereldschokkend zijn maar het is wel erg leuk om te maken en te programmeren.

Vriendelijke groet, Hein Pragt

© 2010 Hein Pragt

Nieuwe versie van het spel reversi

Momenteel werk ik aan een nieuwe versie die geheel vanaf het begin opnieuw gemaakt gaat worden, wel weer geheel in de taal C en als klein portable Microsoft Windows programme te downloaden zal zijn, binnenkort dus meer.

© 2010 Hein Pragt

Maximalisatie strategie

Een voor de hand liggende strategie is om te zorgen dat men met een zet de meeste stenen wint, dit heet de maximalisatie strategie. Dit kan bij onervaren spelers nog wel eens werken maar is meestal gedoemd tot falen. Een programma dat in dit opzicht te gretig is kan dus ook vrij eenvoudig door een tactische speler overwonnen worden. Ook is het bezitten van veel stenen op een bepaald moment in het spel geen garantie voor winnen omdat deze verhouding bij Reversi totaal omkeren kan. Een voorbeeld dat inde praktijk niet snel voorkomen zal maar wel mogelijk is toont aan dat een speler die nog slechts één stuk op het bord heeft toch binnen een paar zetten kan winnen. In deze opstelling moet wit namelijk alle zetten passen en kan zwart uiteindelijk met 40 - 24 winnen.

De hoeken

De hoeken zijn erg belangrijk in Reversi en een belangrijk onderdeel van de spel strategie. Een steen die eenmaal op een hoek staat, kan niet meer worden omgedraaid, Ook kan men deze hoek (en randstukken) gebruiken om rijen stenen te pakken die vanuit deze hoeken ook niet meer terug te winnen zijn. Het winnen van de hoeken is daarom vrijwel altijd gunstig, de velden die aan de hoek grenzen zijn dus erg ongunstig, want via deze velden kan de andere kleur naar de hoeken komen. Vooral de velden die schuin aan de hoek grenzen zijn erg gevaarlijk omdat stukken in het middenveld nog wel eens van kleur wisselen en zo een brug naar de hoeken vormen. De meeste spelers zullen deze velden alleen als ze gedwongen worden (omdat er geen andere zet meer mogelijk is) spelen of als de hoek al bezet is en men hierdoor een andere hoek kan winnen. . Ervaren spelers zetten daar meestal pas als ze ertoe gedwongen worden, of uit speciale tactische motieven, bijvoorbeeld wanneer nadat de tegenstander de hoek neemt, men zelf een andere hoek kan veroveren.

De randen

Ook de randen zijn zeer belangrijk omdat deze stenen in iedere geval aan één kant stabiel zijn en dus niet zo snel overgenomen kunnen worden. Ook kan men via de randen series stenen pakken in het middenveld die minder snel terug te pakken zijn. Maar aangezien de randen ook een opstapje naar de hoeken zijn moet men heel zorgvuldig spelen en bruggen naar hoeken proberen te vermijden. Ook is een ingesloten stuk van de tegenstander (X O X of O X O) aan de rand een gevaar omdat deze als wig blijft staan en (bijna) niet meer teruggepakt kan worden en uiteindelijk een brug naar een hoek kan zijn. Dus over het algemeen wordt er meteen geslagen als twee stenen van verschillende kleur op de rand tegen elkaar liggen om de rand in bezit te houden.

Mobiliteit strategie

Mobiliteit is een belangrijke strategie in Reversi, zeker in het midden spel. Mobiliteit staat voor het aantal mogelijke zetten die een speler heeft in een bepaalde spelpositie. Hoe hoger de mobiliteitswaarde, hoe meer opties voor waarschijnlijk goede of veilige zetten men heeft een lage waarde voor de tegenstander is dus gunstig voor u. Wanneer de tegenstander bijvoorbeeld nog maar één zet kan doen en dit strategisch ook nog een zeer onvoordelige zet is kan men elkaar dus dwingen om zetten te doen. Door handig te spelen met mobiliteit kan men de tegenstander dwingen minder goede zetten te doen door de keuze van zetten voor de tegenstander te beperken.

© 2010 Hein Pragt

Het minimax algoritme is een methode om een goede keuze uit een enorme reeks van spelzetten en tegenzetten te kunnen berekenen. Het wordt specifiek toegepast in het zoeken van spelbomen om de beste zet voor de computer speler van een spel te bepalen. Het maakt gebruikt van het eenvoudige principe dat iedere speler bij zijn zet de best beschikbare zet zal kiezen. De spelboom bestaat dus in de bron uit alle mogelijke zetten van de computer en op het volgende niveau alle antwoord zetten die de tegenstander hier op kan uitvoeren. Een een dergelijk niveau noemt men een ply en bij ieder niveau kijkt het algoritme dus één zet verder. Door bij elke zet te berekenen wat de minimale winst voor de tegenstander is kan de computer dus de zet berekenen die voor de tegenstander het minste kan opleveren. Aangezien verlies bij de tegenstander winst voor de computer is zal een dit dus tot winst voor de computer leiden. In theorie kan men zo het spel tot het einde doorrekenen, maar in de praktijk zal de computer hier niet krachtig genoeg voor zijn. Zonder optimalisatie zal op elk niveau het aantal te berekenen zetten exponentioneel toenemen. Op het eerste niveau nog maat 10 zetten, op het tweede al 10 antwoorden op elke zet dus 100 zetten. Op niveau drie is het al 1000 en op vier al 10.000 zetten. Op niveau vijf zou het aantal te berekenen zetten al 100.000 zijn en het daaropvolgende niveau al 1000.000 zetten. Alleen in het eindspel kan men met puur minmax tot het einde doorrekenen omdat tegen het einde van het spel ook het aantal mogelijke tegenzetten evenredig afneemt.

De volgende figuur toont een boom van vier niveaus met Zwarte als huidige speler. Door middel van het minmax algoritme kan men recursief door deze boom lopen en zo de best mogelijke eigen zet met minimale winst voor de tegenstander te berekenen.

Het minimax algoritme is een recursief algoritme met als parameters het huidige bord de huidige diepte en de maximale diepte en de kleur van de speler heeft. Het geeft de beste zet en de score van deze zet terug.

Minimax Pseudocode

int MaxValue(Board b, int depth) {
    if ((GameOver(b) or depth>MaxDepth)
        return Analysis(b)
    int max = -infinity
    for each legal move m in board b {
        copy b to c
        make move m in board c
        int x = MinValue(c, depth + 1)
        if (x > max) max = x
    }
    return max
}

int MinValue(Board b, int depth) {
    if ((GameOver(b) or depth > MaxDepth)
        return Analysis(b)
    int min = infinity
    for each legal move m in board b {
        copy b to c
        make move m in board c
        int x = MaxValue(c, depth + 1)
        if (x < min) min = x
    }
    return min
}

NegaMax algoritme

Een eerste optimalisatie is het omzetten naar een NegaMax algoritme om de twee routines samen te voegen en bij elke iteratie de waarde om te keren.

const int sign[2]={1, -1}
  
int NegaMax(Board b, int depth, int color) {
    if (GameOver(b) or depth > MaxDepth)
        return sign[color] * Analysis(b)
    int max = -infinity
    for each legal move m in board b {
        copy b to c
        make move m in board c
        int x= - NegaMax(c, depth+1, 1-color)  // Notice the "-"
        if (x > max) max = x
    }
    return max
}

Alpha-Beta cutofs (afsnijding)

Om het aantal te bereken zetten enigszins te beperken en toch dieper te kunnen zoeken kunnen we via een slimme truc bepalen of het verder doorzoeken van een deel van de boom wel noodzakelijk is. Wanneer we ontdekken dat deze zet een slechter resultaat oplevert in de eerste paar eindzetten dan is het niet nodig alle eindzetten te berekenen omdat dit deel van de spelboom in ieder geval voor een slechter resultaat zal zorgen. Alleen de tak van de boom die wel een beter resultaat geeft dan de vorige tak rekenen we door. Met gebruik van Alpha-bèta cutoffs kan er veel snelheid winst gemaakt worden en de grootte van de boom die doorzocht moet worden kleiner gemaakt worden. De gemiddelde winst in tijd is c.a. 30 procent.

Alpha-Beta Pseudocode (negamax versie)

const int sign[2]={1, -1}

int NegaMax(Board b, int depth, int color, int alpha, int beta) {
    if ((GameOver(b) or depth > MaxDepth)
        return sign[color] * Analysis(b)
    int max = -infinity
    for each legal move m in board b {
        copy b to c
        make move m in board c
        int x= - NegaMax(c, depth+1, 1-color, -beta, -alpha)
        if (x > max) max = x
        if (x > alpha) alpha = x
        if (alpha >= beta) return alpha
    }
    return max
}