het spel
Tic-tac-toe is een zeer populair spel voor twee spelers, X en O, die om de beurt de spaties in een 3×3 raster markeren. De speler die erin slaagt om drie van hun punten in een verticale, horizontale of diagonale rij te plaatsen, wint het spel.,
wiskundige eigenschappen
vanuit een wiskundig oogpunt heeft het spel twee zeer belangrijke eigenschappen:
Eigenschap 1:
het spel geeft toe dat de speler die deze optimale strategie gebruikt zal winnen of draw, maar het zal niet verliezen.
eigenschap 2:
Het aantal mogelijke verschillende overeenkomsten is relatief klein.
aan het begin kan de eerste speler een van de 9 spaties markeren. In de volgende beurt kan de tweede speler een van de resterende 8 plaatsen markeren en ga zo maar door., Het spel gaat door totdat alle ruimtes zijn gemarkeerd of een van de spelers wint.
Het is dan gemakkelijk te begrijpen dat het totale aantal verschillende overeenkomsten lager is dan:
987….1 = 9! = 362880
dat is een redelijk klein getal voor een computer.
het algoritme
uit Eigenschappen 1 en 2 volgt dat een praktisch en algemeen algoritme om het spel te winnen/te tekenen is om de Alpha Beta zoekopdracht te gebruiken.,
bij elke beurt evalueert het algoritme alle mogelijke gevolgen van elke zet (mogelijk door eigenschap 2) en kiest het algoritme dat een overwinning of een gelijkspel verzekert (mogelijk door Eigenschap 1).
Een AI-speler die elke zet kiest met het Alpha beta zoekalgoritme zal nooit verliezen. Om het spel realistischer te maken is het leuk om een stochastische factor te introduceren, zodat elke keer met een vooraf gedefinieerde waarschijnlijkheid de AI-speler willekeurig beweegt in plaats van het alpha beta-algoritme te volgen., Dit maakt het spel realistischer omdat het de AI-speler menselijker zal maken en soms zal het verliezen.