Minimax Ağaçları (Minimax Tree)

 

Minimax Ağaçları (Minimax Tree)

Yazan : Şadi Evren ŞEKER

Bilgisayar mühendisliğinde, yapay zeka konusunda kullanılan bir karar ağacı türüdür. Aslında minimax ağaçları bilgisayar bilimlerine işletme bilimindeki oyun teorisinden (game theory) girmiştir.

Temel olarak sıfır toplamlı bir oyunda (zero sum game), yani birisinin kaybının başka birisinin kazancı olduğu (veya tam tersi) oyunlarda karar vermek için kullanılışlıdırlar. Örneğin çoğu masa oyunu (satranç, othello, tictactoe gibi) veya çoğu finansal oyunlar (borsa gibi) veya çoğu kumar oyunları sıfır toplamlı oyunlar arasında sayılabilir (yani birisinin kaybı başka birisinin kazancıdır ve sonuçta toplam sıfır olur).

Yukarıda bahsedilen bu oyunlarda doğru karar verilmesini sağlayan minimax ağacı basitçe kaybı asgariye indirmeye (mimize etmeye) ve dolayısyıla kazancı azamiye çıkarmaya (maximize etmeye) çalışır.

Ağaç basitçe her düğümde (node) farklı alternatiflerin değerlerini hesaplar. Son düğümden (yapraklardan ,leaf) yukarıya doğru değerleri seçerek gelir ve en sonunda bütün ağaçtaki en doğru seçenek seçilmiş olur.

Örneğin Tic Tac Toe oyununu ele alalım. 3×3 boyutundaki kare bir tabloda sırasıyla X ve O harflerinin taraflarca yazıldığı bu oyunda, oyunun durumuna göre aşağıdakine benzer bir karar ağacı çıkması mümkündür:

Yukarıda ağacın kökünü (root) oluşturan ilk durumda oyunun mevcut hali görülmektedir. Ardından karar verecek taraf olan ve tahtaya X sembolü koyan oyuncu kendi oyununu analiz eder. X ‘in oynanabileceği 3 ayrı ihtimal bulunmaktadır ve bütün bu ihtimaller ağaçta farklı birer alt düğüm (node) olarak gösterilmiştir.

Ağacın daha alt seviyesinde ise X’in oyananabileceği her ihtimalde, O’nun oyananabileceği ihtimaller gösterilmiştir.

Bu durumda X oynayacak olan oyuncu bütün ihtimalleri görmüş olur ve ilave olarak kendisinin yapacağı son hamleleri aşağıdaki şekilde hesaplar:

Yukarıdaki şekile X’in yapacağı son hamleninde hesaplanışını görüyoruz. Bir minimax ağacının hesaplanması sırasında kaç seviye gidileceğine seviye (ply) ismi verilir. Örneğin yukarıdaki ilk şekildeki minimax ağacımı 2 seviye (ply) bir ağaçken, yukarıdaki son ağacımız 3 seviyeli bir ağaçtır.

Minimax ağacının seviyesinin artması sonucun daha kesin bulunması ve yapay zekamızın başarısını arttırır. Ancak bunun karşılığında bilgisayarın hafızasında (RAM, memory) daha fazla bilginin tutulması gibi bir bedel ödenir. Örneğin satranç veya GO gibi ihtimallerin çok yüksek olduğu oyunlarda seviyenin belirli bir limitin altında tutulması gerekir.

Bilgisayarın yukarıdaki ağaca bakarak bir karar vermesi çok güçtür. Kararın sayısal bir değere oturması için yukarıdaki her hamle durumunu puanlamamız ve bundan sonra bilgisayarın minimax yaklaşımı ile seçim yapmasını istememiz gerekir.

Örneğin bilgisayarın (Burada X olarak oynadığını düşünelim) kazanma durumlarına 1 ve kaybetme durumlarına 0 diyelim.

Bu durumda ihtimaller ve puanlar aşağıdaki şekilde olacaktır:

Yukarıdaki şekilden de anlaşılacağı üzere bilgisayar kazancının en fazla olduğu ihtimali seçmek ister. Basit bir hesapla bilgisayarın kazanç durumlarının toplamlarını ağacın bir üst seviyesine taşıyalım:

Yukarıda ağacın son seviyesinden karar vermemiz gereken pozisyona doğru bir seviye puanlar taşınmıştır. Yani kararın verilmesi gereken pozisyon ağacın kökündeki (en üst seviyesindeki) pozisyondur ve oyun sonu en altta gösterilmektedir. İşte bizde puanlarımızı karara bir seviye yaklaştırıyoruz.

Bu yaklaştırma işlemi sırasında dikkat edilmesi gereken X’in hamle sırasındaki azami (maximum) değerlerin taşınmasıdır çünkü X kendi hamlesinin en çok puan getirdiği durumu almak ister. Ancak yukarıdaki grafikteki son seviyede X’in tek hamlesi olduğu için mecburen (bir seçim yapılmaksızın) puanlar bir seviye yukarı taşınmıştır.

O’nun hamlesinin bulunduğu bir üst seviyede ise bir seçim yapılabilir. Çünkü O hamlesini iki farklı yere yapabilir. Bu durumda O’nun kendisi için en avantajlı yere oynayacağını düşünürsek bu seviyede asgari (minimum) değerlerin alınması gerekir.

Aşağıda O’nun hamlesi için alınmış asgari değerler bulunuyor :

Görüldüğü gibi ihtimallerin en düşük değerleri alınmıştır.

Taşınan bu son seviyeyle artık bilgisayar hamlesine karar verebilir çünkü mevcut durum için hangi hamlenin en kârlı olduğu (max) görülmektedir. Yukarıdaki ağaçta en sağdaki değer olan 1 puanındaki hamleyi yapması durumunda bilgisayar her ihtimalde oyunu kazanmaktadır.

Sonuç olarak alınan değerler aşağıdaki şekilde gösterilebilir:

Yani bir min bir max alınmaktadır ve bu işlem bu şekilde devam etmektedir. Ağacımızın ismi de zaten buradan türetilmiş minimax ağacı olarak geçmektedir. Aynı anlamda farklı başlangıç değerinde maximin ağacı da literatürde geçmektedir. Bu ağaç da tamamen aynıdır ancak kaygı kendi hamleleri üzerine değil rakibin hamleleri üzerine kuruludur.