Spill
Tic-tac-toe er et meget populært spill for to spillere, X og O, som bytter på å markere områder i en 3 x 3 rutenett. Den spilleren som har lykkes i å plassere tre av sine merker i en vertikal, horisontal eller diagonal rad vinner spillet.,
Matematiske Egenskaper
Fra et matematisk synspunkt spillet har to svært viktige egenskaper:
Eiendom 1:
spillet innrømmer spilleren som bruker denne optimal strategi vil vinne eller tegn, men det vil ikke miste.
Eiendom 2:
antall mulige ulike kamper er relativt små.
Til å begynne med, den første spilleren kan merke noen av de 9 mellomrom. I det følgende slå den andre spilleren kan markere en av de gjenværende 8 områder og så videre., Spillet fortsetter til alle plassene er merket eller en av spillerne vinner.
Det er da lett å forstå at det totale antall av ulike kamper er lavere enn:
987….1 = 9! = 362880
Det er relativt lite antall for en datamaskin.
Algoritmen
Fra egenskaper 1 og 2 følger det at en praktisk og generell algoritme for å vinne/draw-spillet er å bruke Alpha Beta søk.,
På hver tur algoritmen vurderer alle mulige konsekvenser for hvert trekk (mulig på grunn av eiendommen 2) og velger en som vil sikre en seier eller uavgjort (mulig på grunn av holderen 1).
En AI-spilleren som velger hvert trekk med alfa-beta søk algoritmen vil aldri miste. For å gjøre spillet mer realistisk det er hyggelig å innføre en stokastisk faktor slik at hver gang med en forhåndsdefinert sannsynlighet AI-spilleren beveger seg tilfeldig i stedet for å følge alpha beta-algoritmen., Dette vil gjøre spillet mer realistisk som det vil gjøre AI-spilleren mer menneskelig og noen ganger vil det tape.