gra
Tic-Tac-toe to bardzo popularna gra dla dwóch graczy, X i O, którzy na zmianę zaznaczają przestrzenie w siatce 3×3. Gracz, któremu uda się umieścić trzy znaki w pionowym, poziomym lub ukośnym rzędzie, wygrywa grę.,
właściwości matematyczne
z matematycznego punktu widzenia gra ma dwie bardzo ważne właściwości:
Właściwość 1:
Gra przyznaje, że gracz, który używa tej optymalnej strategii, wygra lub zremisuje, ale nie przegra.
właściwość 2:
liczba możliwych dopasowań jest stosunkowo niewielka.
na początku pierwszy gracz może zaznaczyć dowolne z 9 miejsc. W następnej turze drugi gracz może zaznaczyć jedno z pozostałych 8 miejsc i tak dalej., Gra trwa do momentu, aż wszystkie pola zostaną zaznaczone lub jeden z graczy wygra.
wtedy łatwo zrozumieć, że łączna liczba różnych meczów jest mniejsza niż:
987….1 = 9! = 362880
To jest dość mała liczba jak na komputer.
algorytm
z właściwości 1 i 2 wynika, że praktycznym i ogólnym algorytmem do wygrania / remisu jest użycie wyszukiwania Alfa Beta.,
w każdej turze algorytm ocenia wszystkie możliwe konsekwencje każdego ruchu (możliwe ze względu na właściwość 2) i wybiera ten, który zapewni zwycięstwo lub remis (możliwe ze względu na Właściwość 1).
gracz AI, który wybiera każdy ruch za pomocą algorytmu wyszukiwania alpha beta, nigdy nie przegra. Aby gra była bardziej realistyczna, warto wprowadzić czynnik stochastyczny, aby za każdym razem z predefiniowanym prawdopodobieństwem gracz AI porusza się losowo, a nie zgodnie z algorytmem alfa beta., To uczyni grę bardziej realistyczną, ponieważ sprawi, że gracz AI będzie bardziej ludzki, a czasami przegra.