Python Kullanarak Tic-Tac Toe Oyununun Yapay Zekâ Algoritması ve Minimax

undefined

Performansın Kilidi: Alpha-Beta Pruning

Tic-Tac-Toe’da bilgisayar her hamleyi saniyeler içinde hesaplayabiliyor çünkü toplam olasılık sayısı az. Ancak hamle dallanması arttıkça algoritmanın bakması gereken düğüm sayısı üstel olarak artar. Alpha-Beta Pruning, sonucu etkilemeyeceği kesin olan dalları baştan budayarak işlem yükünü ciddi oranda (bazen %50’den fazla) azaltır.

Daha Büyük Oyunlar ve Heuristic Kavramı

Minimax’ı Satranç veya Connect-4 gibi oyunlara uyarlamak istediğinde, oyunun sonuna kadar tüm ihtimalleri hesaplamak imkansız hale gelir. Satrançta ortalama bir oyun 10¹²⁰ olasılık barındırır.

• Derinlik Sınırlaması: Algoritmanın sadece önündeki 5-10 hamleye bakmasını sağlarız.
• Heuristic Fonksiyonlar: Oyun bitmediği halde o anki tahta durumuna bir puan veririz. “Merkezi kontrol ediyor muyum?” gibi kriterlerle tahtayı puanlayıp minimax’ı bu puanlara göre çalıştırırız.

Zaman Karmaşıklığı

Mevcut implementasyonun zaman karmaşıklığı O(b^d) şeklindedir (b: dallanma katsayısı, d: derinlik). Alpha-Beta ekleyerek bu karmaşıklığı en iyi ihtimalle O(b^(d/2)) seviyesine çekebilirsin. Bu, aynı sürede iki kat daha derin hamleleri görebilmek demektir!