Spil
Tic-tac-toe er et meget populært spil for to spillere, X og O, der skiftes mærkning rum i en 3×3 gitter. Den spiller, der lykkes med at placere tre af deres karakterer i en lodret, vandret eller diagonal række, vinder spillet.,
Matematiske Egenskaber
Fra et matematisk synspunkt spillet har to meget vigtige egenskaber:
Ejendom 1:
spillet indrømmer, at den spiller, som anvender en optimal strategi, vil vinde eller få uafgjort, men det vil ikke miste.
ejendom 2:
antallet af mulige forskellige kampe er relativt lille.
i starten kan den første spiller markere et af de 9 mellemrum. I den følgende tur kan den anden spiller markere et af de resterende 8 mellemrum og så videre., Spillet fortsætter, indtil alle rum er markeret eller en af spillerne vinder.
det er så let at forstå, at det samlede antal forskellige kampe er lavere end:
987….1 = 9! = 362880
det er et rimeligt lille tal for en computer.
algoritmen
fra Egenskaber 1 og 2 følger det, at en praktisk og generel algoritme til at vinde / tegne spillet er at bruge Alpha Beta-søgningen.,
Ved hver tur evaluerer algoritmen alle de mulige konsekvenser af hvert træk (mulig på grund af ejendom 2) og vælger den, der vil sikre en sejr eller Uafgjort (mulig på grund af Ejendom 1).
En AI-spiller, der vælger hver flytte med alpha-beta-søgning algoritmen aldrig vil miste. For at gøre spillet mere realistisk er det rart at introducere en stokastisk faktor, så AI-afspilleren hver gang med en foruddefineret Sandsynlighed bevæger sig tilfældigt i stedet for at følge alpha beta-algoritmen., Dette vil gøre spillet mere realistisk, da det vil gøre AI-afspilleren mere menneskelig og nogle gange vil den tabe.