Minimax Algoritması ile TicTacToe Oyunu

Bu yazıda Minimax Algoritması’nı ve onu örneklemek için, oldukça popüler bir oyun olan TicTacToe’dan bahsedeceğiz. Tarayıcı üzerinde çalışacak şekilde basitçe kodlayıp, yapay zekaya karşı mücadele etmeye çalışacağız. Hazırsanız başlayalım!

Minimax Algoritması Nedir?

Minimax algoritması, ihtimaller havuzu içinden en iyi ve en kötü senaryoları değerlendiren bir karar verme algoritmasıdır.

Satranç, TicTacToe ve dama gibi sıra tabanlı oyunları ele alalım. Her bir oyuncu, sıra kendine geldiğinde, elindeki taşı/taşları kurallara riayet ederek bir noktaya götürüp hamlesini yapar. Her bir hamle için, taşların gidebileceği noktalar kadar ihtimal bulunur. Örneğin TicTacToe oyununda: Her hamlede bir nokta kapatılmış olduğu için, sonraki hamlenin ihtimal sayısı öncekinden bir eksilerek gider. nxn noktadan oluşan bir TicTacToe oyunu için:

Şekil 1. 3x3 TicTacToe için ihtimaller

Birinci hamlede n², ikinci hamlede n²-1, üçüncü hamlede n²-2, … ihtimal vardır. Toplam ihtimal sayısı ise, her bir hamledeki ihtimal sayısının çarpımı olacağından, n² faktöriyel kadardır. Satranç gibi derinlikli strateji oyunlarında bu ihtimallerin sayısı muazzam seviyelere ulaşabilir.

Eğer bütün bu ihtimalleri hesaplamış olsaydık, bunlar arasından bize galibiyeti getirebilecek en iyi hamleleri seçebilirdik, öyle değil mi?

Minimax algoritması da tam olarak bunu yapıyor. Her bir hamlede son duruma bakarak, bundan sonraki hamlelerin ne olabileceğini hesaplıyor. Ta ki, oyunculardan biri kazanasıya veya beraberlik durumu ortaya çıkasıya kadar. Bu hesaplamalar, aşağıdaki gibi bir ihtimal ağacı ortaya çıkarıyor:

Şekil 2. İhtimal ağacı

Şekil 2.de görüldüğü gibi, ilk durum olan 0. durumdan itibaren toplam 11 durum hesaplanmış ve 5 farklı sona ulaşılmış. 2, 8 ve 9'uncu son durumlarda X galip gelirken, diğer iki durumda kazanan olmamış.

İhtimaller hesaplandıktan sonra, son durumlardan başlayarak yukarıya doğru hamleleler puanlandırılır. Eğer son hamlede galip gelmişsek +1 puan, mağlup olduysak -1 puan, beraberlik oluştuysa da 0 puan verilebilir:

Şekil 3. Puanlandırma

Şimdi ise, Minimax’ın adında da geçtiği gibi, puanları minimize ve maksimize etmemiz gerekiyor. Yapacağımız şey basitçe: Her bir hamledeki puanların minimumunu veya maksimumunu yukarıya taşımak. Minimax algoritması, rakibin her zaman en iyi hamleyi yapacağını varsaymaktadır. Bu yüzden ihtimaller arasından; eğer o hamle rakibinse, en düşük puanlı ihtimal seçilir ve onun puanı yukarıya taşınır. Örneğin 4 ve 5 ihtimallerinin bulunduğu hamleye bakalım. Kırmızı renkli taşlar, o hamlenin sahibini göstermektedir (X’in kendimiz, O’nun rakip olduğunu varsayıyoruz). Hamle sırası rakipte olduğu için, oraya kadar taşınan +1 ve 0 puanlarından minimun olanı, yani 0 yukarıya taşınacaktır. Hamle sırası bizde olduğu zamanlarda da, bu durumun tam tersi olarak maksimum olanı yukarıya taşınacaktır. Nitekim Şekil 3.te de görüldüğü gibi, oyunun bittiği bütün durumlarda son hamle X’e ait olduğu için, yukarıya doğru gidilmeye maksimum alınarak başlanmıştır.

Şekil 4. Son durum

Başlangıç durumundayken yapılacak hamleye ulaşasıya kadar, bu işlemler tekrarlanır. Bir maksimum bir minimum alarak gittiğimiz için, Minimax algoritması rekürsif olarak çalıştırılabilir.

Son durumda en yukarıya ulaşan puanlara bakılır. En yüksek puanı tutan dallardan birisi seçilir. Şekil 4.te en yukarıya sırasıyla: 0, +1 ve 0 puanlarının ulaştığı görülmektedir. Bu durumda +1 puanını tutan dal seçilir ve algoritma oyunu kazanır.

Minimax algoritmasının çalışmasıyla ilgili bu animasyona da göz atabilirsiniz:

TicTacToe Uygulaması

Hazırsanız, Minimax algoritmasını uygulamak için TicTacToe oyununu kodlamaya geçebiliriz. Oyunumuzu tarayıcıda kolaylıkla çalıştırabilmek için JavaScript ile kodlayacağız. Ayrıca biraz görsellik katmak için de, güzel ve basit bir grafik kütüphanesi olan p5.js kütüphanesini kullanacağız.

Kütüphanenin web sayfasını buradan ziyaret edebilirsiniz. Ayrıca p5.js’nin ücretsiz ve kullanışlı bir web editörü de bulunuyor. Bilgisayarınıza herhangi bir dosya yüklemeden, tüm kodlarınızı buradan da yazıp çalıştırabilirsiniz.

• Öncelikle temel bir kaç adımla başlayalım:

• DIAMETER, ekrana çizilecek dairelerin çapını tutan bir sabit. İkinci satırdaki değişkenlerse, ekrana çizilecek grafiklerle ilgili bazı kısımlarda iş görecekler. Konuyla fazla ilgisi olmadığı için şimdilik detaylara girmiyorum. game değişkeni birazdan oluşturacağımız Game sınıfının bir nesnesi olacak. Oyunun ilerleyişi ve tabiki Minimax Algoritması’ndan gücünü alan yapay zekamız bu sınıfta tanımlı olacak. ai ve human değişkenlerini, hangisinin X hangisinin O olduğunu anlamak için kullanacağız. Nitekim players objesi de, arkaplanda X ve O’ların sayısal karşılıklarını tutmakta.

• setup fonksiyonu p5.js kütüphanesinin otomatik çalıştırdığı bir fonksiyondur. Uygulamamız ekrana yüklenirken, çalışmasını istediğimiz kodlar burada bulunmalıdır. Yine ilk satırlar ekrana çizdirelecek grafiklerle ilgili ayarlardan oluşuyor. Aşağısındaysa oyuncularımızı ve game nesnesini tanımlıyoruz. game nesnesini oluştururken, yapay zekanın ve insanın taşlarını da belirtiyoruz. Şimdi de Game sınıfını oluşturmaya geçelim.

• Game sınıfını ayrı bir dosyada, şekildeki gibi tanımlıyoruz. Oyun ile ilgili esas ayarlar restart fonksiyonunun içinde bulunuyor. Bu kodları ayrıca bir fonksiyona yazıp çağırmamın sebebi: Oyun her bittiğinde yeniden çalıştırmak için yeni bir nesne üretmek veya sayfayı yenilemek yerine bu fonksiyonu kullanmak. scores objesi ise Minimax algoritmasını uygularken, son durumları puanlamada işimize yarayacak. restart fonksiyonumuzu ise aşağıdaki gibi oluşturuyoruz:

• currentPlayer, son hamlenin kimde olduğunu tutmaktadır. map ise oyunun haritasını iki boyutlu bir dizi olarak tutuyor. Henüz oyun başlamadığı için bütün hücreler null değer tutmakta. Her bir hamle sonunda, hamleyi yapan oyuncunun değeri (‘X’ için 0 ve ‘O’ için 1) bu harita üzerinde ilgili koordinata yazılacak. winPath ise, oyunu kazanan taşları ekranda vurgulamak için gereken koordinatları tutacak. moveCounter kalan hamle sayısını, finished ise oyunun bitip bitmediğini tutan değişkenler olarak görev alacaklar.

• Game sınıfının geriye kalan fonksiyonları ise bu şekildedir. Her birini tek tek açıklamak, yazıyı çok fazla uzatacağı için yalnızca ne işe yaradıklarına değineceğim. Fakat detaylar için yazının sonunda paylaştığım kaynak kodlarını inceleyebilirsiniz.
• update: Her bir hamleden sonra çalıştırılır. Hamle sırasının kime geçtiği ve oynanan hamle sayısını bu fonksiyon günceller.
• finishGame: finished değişkenine true değer atayarak oyunu bitirir.
• Get ve Set fonksiyonları, haritaya veya haritada belirli bir hücrede tutulan değerlere ulaşmak ve güncellemek için kullanılmaktadır.
• checkWinner ve equals3 fonksiyonları, haritanın son durumuna bakarak yatayda, dikeyde veya çaprazda herhangi bir kazanan olup olmadığına bakar. Beraberlik durumunda -1, ‘X ‘kazandıysa 0 ve ‘O’ kazandıysa 1 değerini döndürür. Eğer henüz bir kazanan yoksa ve oyun halen devam edebiliyorsa null değerini döndürür.
• Sorgulama fonksiyonları ise; sıranın kimde olduğuna, oyunun bitip bitmediğine ve sorgulanan hücrenin boş olup olmadığın dair true/false değerler döndürür.
• Şimdi de asıl olayımız olan Minimax Algoritması’nı kodlamaya geçelim:

• Öncelikle yine Game sınıfının içinde minimax adlı fonksiyonu oluşturalım. Rekürsif çalışacağı için, isMaximizing parametresiyle rakibin mi yoksa kendisinin hamlesi mi olduğunun takibini yapacağız. Fonksiyonun en başında, son durumu checkWinner fonksiyonuyla kontrol ediyoruz. Yukarıda da bahsettiğimiz gibi, puanlamaya en alttaki durumdan başlıyorduk. Fonksiyonun bu kısmı da aslında son durumu puanlayan kısım olmaktadır. Sonuç her neyse, scores objesinde onun için önceden belirlediğimiz puanı alacak ve fonksiyon bu puanı geri döndürecek.

• Bir sonraki ihtimalin hesaplanmasına geçilirken, hamle sırasının kimle olduğuna isMaximizing ile karar verilecek. Eğer bu değer true gelirse, sıra yapay zekada anlamına gelecek ve haritadaki boş hücrelerden birine yapay zekanın taşı yazılacak. Daha sonra minimax algoritması, sonraki ihtimalleri de hesaplamak üzere tekrar çalıştırılacak. Fakat hamle karşı tarafa geçeceği için, bu sefer isMaximizing parametresini false göndereceğiz.
• Ardından gelen değer score değişkenine atanıyor ve az evvel üzerine yazdığımız hücre tekrar null değer alacak şekilde eski haline döndürülüyor. Bu sayede, en iyi ihtimali bulasıya kadar oyun haritasına kalıcı bir müdahalede bulunmuyoruz. Ardından hesaplanan en iyi değer, maksimize edileceğinden, max fonksiyonu ile bestScore değişkenine atıyoruz.
• Aynı işlemleri else durumu için de yapalım:

• Yukarıdaki kodlar da, rakip oyuncunun minimize ettiği durum için geçerli olacaktır.
• Son olarak minimax algoritmasını çalıştıracak fonksiyonu yazalım Game sınıfıyla ilgilenmeyi burada bitirelim:

• Minimax algoritmasını birazdan bu fonksiyon üzerinden çağıracağız.
• Oyunumuzun esas çalıştırıldığı sketch.js dosyasına geri döndük. draw fonksiyonu içinde oyun döngüsünü oluşturalım. (draw fonksiyonu da, tıpkı setup gibi, otomatik çalışan bir diğer p5.js fonksiyonudur. Uygulama çalıştığı müddetçe, belirli bir FPS değeriyle sürekli çalışıtırılmaktadır):

• Eğer oyun herhangi bir şekilde sonladıysa, finishGame fonksiyonu ile oyunu bitiriyoruz. Değilse ve eğer hamle sırası yapay zekadaysa, az evvel yazdığımız AI fonksiyonunu çalıştırıyoruz. Ardından oyunu güncellemek için update fonksiyonunu kullanıyoruz.
• İnsan olan oyuncunun da ekran üzerinde hamle yapabilmesi için, aşağıdaki kodları çalıştırıyoruz:

• mousePressed fonksiyonu, yine p5.js’in bir lütfu, olay fonksiyonudur. Ekran üzerinde bir tıklama olayı olduğunda çalışıyor. Eğer oyun bittikten sonra tıklanırsa, restart fonksiyonuyla oyunu yeniden başlatıyoruz. Oyun henüz devam ediyorsa ve hamle sırası insanda ise, kullanıcının fareyle işaret ettiği noktaya göre, oyun haritasındaki ilgili hücrenin değerini güncelliyoruz.

Oyunumuzun son hali aşağıdaki gibidir:

Buradaki bağlantı üzerinden oyunu oynayabilirsiniz.

Kaynak kodlarına buradan göz atabilirsiniz.

Son olarak

Bu yazıda TicTacToe oyununda insan zekasıyla mücadele edecek, Minimax Algoritması’nı kullanan, basit yapay zeka geliştirmeye çalıştık. Kodları denerken karşılaştığım bir kaç hatayı/yanlışı, siz değerli okuyucularımın dikkatine sunuyorum. :)

Okuduğunuz için teşekkür ederim.

Kaynak

• Tic Tac Toe AI with Minimax Algorithm