XOX (Tic-Tac-Toe): Oyun Teorisi (Game Theory) ve Minimax Yapay Zeka Algoritması
Basit bir XOX oyunu gibi görünse de, yapay zekâ modunda arkada Minimax algoritması çalışır. Bilgisayar her hamlesinde kalan tüm olasılıkları oyun sonuna kadar hesaplar, her sonucu puanlar ve kendisi için en kötü durumda bile en iyi sonucu veren hamleyi seçer. Bu yüzden bilgisayarın kaybetmesi mümkün değildir; kusursuz oynarsanız beraberlik alabilirsiniz.
Algoritma, tahtadaki mevcut durumu puanlamak (Heuristic Evaluation) için derinlik öncelikli arama (DFS) kullanır. Kendi kazanma ihtimaline +10, sizin kazanma ihtimalinize -10 puan verir. Üzerine eklenen Alpha-Beta Budama (Alpha-Beta Pruning) optimizasyonu, sonucu değiştiremeyecek dalları hiç hesaplamadan keser. XOX'ta tüm hamle sıralamalarının sayısı en fazla 9! yani 362.880 olduğundan, budamayla birlikte bu hesaplama tarayıcınızda gözle fark edilmeyecek bir sürede tamamlanır.
Minimax Algoritması S.S.S.
Bilgisayarı yenmek neden imkânsız?
Çünkü XOX "sıfır toplamlı" ve "tam bilgili" bir oyundur; tüm olasılıkları sonuna kadar hesaplanabildiği için çözülmüş bir oyun sayılır. Bilgisayar her hamlede bu hesabı yaptığından hata yapmaz. En iyi sonucunuz beraberliktir: kusursuz oynarsanız oyun berabere biter, tek bir hata yaparsanız bilgisayar kazanır. Bilgisayarın kaybetmesi mümkün değildir.
Alpha-Beta Pruning (Budama) tam olarak ne işe yarar?
Karar ağacında, daha önce bulunmuş bir seçenekten daha iyi sonuç vermesi artık mümkün olmayan dalları hiç hesaplamadan keser. Sonuç aynı kalır, incelenen konum sayısı ise belirgin biçimde azalır. Kazancın ne kadar olacağı hamlelerin inceleme sırasına bağlıdır; sabit bir oran vermek doğru olmaz.