Het spel reversi

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

De regels van het spel Reversi

© 2010 Hein Pragt

Reversi wordt gespeeld op een bord van 8 bij 8 vakjes net als een schaakbord. De velden hebben een aanduiding door middel van een letter en een cijfer net als bij het schaken, maar de nummering van de rijen is andersom. De spel stenen hebben elk een witte en een zwarte kant (ook soms rood en groen) en als men spreekt over witte en zwarte stenen dan bedoelt men stenen waarvan de witte of de zwarte zijde boven liggen. Een speler speelt met wit, de ander zwart waarbij zwart altijd begint. In de begin positie zijn de vier velden in het centrum bezet, met een witte steen op d4 en e5, en een zwarte steen op e4 en d5. In sommige versies is dit precies andersom, deze begin stelling wordt echter op geen enkel officieel toernooi gebruikt. Een zet bestaat uit het neerleggen van een steen, met de eigen kleur boven op een leeg veld naast een steen van de tegenstander waarbij minimaal één steen van de tegenstander ingesloten moet worden tussen de zet en stukken met de kleur van de speler. Alle rijen van stenen van stenen van de kleur van de tegenstander die ingesloten worden door deze zet (horizontaal, verticaal en schuin) worden omgedraaid en krijgen dus de kleur van de speler. Wanneer de speler geen stenen van de tegenstander kan insluiten, kan deze geen zet doen en moet de speler een beurt overslaan, in alle andere gevallen is zetten verplicht. Het spel is voorbij wanneer beide spelers geen stenen meer kunnen plaatsen, dit is meestal omdat het bord vol is maar het kan door slim spelen ook voor de tijd gebeuren. Het spel duurt dus maximaal 60 zetten en kan ook vrij snel gespeeld worden, de winnaar is de speler die de meeste stenen van de eigen kleur op het bord heeft.

Hmp_reversi voor windows 3.02 (freeware / gratis) 64 Bit

Dit is een recente versie van mijn reversi (of othello) programma waarbij ik meerdere optimalisaties heb toegepast. Ten eerste is het programma nu 64 bits waardoor een veld in twee 64 bit woorden opgeslagen kan worden. Het spel maakt gebruik van bitboards, een heel efficiënt en slim flip algoritme, alpha beta pruning, hashing / caching, move ordering, openingsboek en evaluatie op basis van patterns. Het spel kan 12 tot 20 ply diep kijken en heeft geen instelling om het zwakker te laten spelen. Het spel speelt altijd op het beste niveau net als een menselijke tegenspeler. Voor mij is het winnen van een reversi programma dat op een laag niveau ingesteld staat net zoiets als winnen in een hardloopwedstrijd wanneer de tegenstander een touw om beide benen heeft. Dit is geen echt winnen wanneer je de tegenstander een handicap geeft. Het spel is zeer basis opgezet met alleen de mogelijkheid om zetten terug te nemen en een spel op te slaan of te laden. Het spel speelt behoorlijk sterk, het verliest helaas nog wel (maar laat zich niet van het bord spelen) van zebra en nboard wanneer deze op hoog niveau ingesteld staan. Het spel is portable, het bestaat uit één exe bestand dat niet geïnstalleerd hoeft te worden. Ik wens u veel speelplezier met dit reversi programma. Het programma is gezipt opgeslagen en moet wel uitgepakt worden na download. (64 bit versie 3.02) Download hier: Hmp_reversi voor windows.

Reversi voor windows. (freeware / gratis)

Mijn eerste versie van reversi of othello schreef ik in basic op de trs80 computer. Dit was een hele simpele versie met O en X als stukken op het veld en een simpele 2 niveau min/max berekening. Later op de eerste pc schreef ik het spel voor windows 95 opnieuw maar deze keer in visual studio en de programmeertaal C en assembler. Aangezien de computers nog niet zo snel waren, was elke kleine optimalisatie welkom om nog meer zetten te kunnen doorrekenen. De routines om velden te spelen en te evalueren was dan ook in heel compacte assembler geschreven. Mijn zoon vond de achtergrond te saai en heeft een grappig uiterlijk voor het spel bedacht. De laatste versie van het spel maakte ik in 1999 maar aangezien de opzet van het spel een min/max met slimme dynamische veld waarden was en de evaluatie van 4 tot 6 niveaus diep was en grote delen in assembler waren geschreven, was verder verbeteren van het spel erg moeilijk. In 2000 ben ik door een backup fout de sources kwijtgeraakt waardoor deze versie de laatste versie was die ik kan maken. Dit is dus een kleine en portable versie van het spel reversi voor windows, het is niet een super sterke versie maar soms wel verassend in zijn spel. De grafische achtergrond is door mijn zoon Robert (op 12 jarige leeftijd) gemaakt. (Versie 1.04) Download hier: Mickey reversi voor windows.

Reversi strategie

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

Het belang van de hoeken bij reversi

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 bij het spel reversi

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 bij reversie

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.

Minimax algoritme en Alpha-Beta Pruning

© 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]=
  
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]=

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
}