Minimax Algoritması

Yapay Zekanın (YZ) ortaya çıkışından bu yana, oyun oynamak AI’nın en ilginç uygulamalarından biri olmuştur.

İlk satranç programları, 1950’de bilgisayarların programlanabildiği anda Claude Shannon ve Alan Turing tarafından yazılmıştır.

Satranç, tic-tac-toe ve Go gibi oyunlar ilginç çünkü iki ordu arasındaki rekabeti tamamen soyutlıyorlar.

YZ araştırmaları için oyunu cazip bir alan haline getiren bu soyutlamadır.

Bu yazıda, algoritmanın işleyişi ile birlikte Minimax algoritmasının temellerini inceleyeceğiz.

Ayrıca minimax algoritmasının optimizasyonuna, alfa-beta budamalarına da göz atacağız.

Minimax algoritması nedir?

Minimax, diğer oyuncunun da en iyi şekilde oynadığını varsayarak bir oyuncu için en uygun hareketi seçmek için kullanılan özyinelemeli bir algoritmadır.

Tic Tac Toe, go, satranç, Isola, dama ve diğer birçok iki oyunculu oyunlar gibi oyunlarda kullanılır.

Bu oyunlara mükemmel bilgi oyunları denir çünkü belirli bir oyunun tüm olası hareketlerini görmek mümkündür.

Scrabble gibi mükemmel olmayan iki oyunculu oyunlar olabilir, çünkü rakibin hareketi tahmin edilemez.

Bir oyun oynadığımızda nasıl düşündüğümüze benzer: “Bu hamleyi yaparsam, o zaman rakibim sadece bu hamleleri yapabilir” vb.

Minimax buna denir çünkü diğer oyuncu maksimum zarara sahip olan stratejiyi seçtiğinde kaybın en aza indirilmesine yardımcı olur.

terminoloji

• Oyun Ağacı : Oyunun durumundan bir sonraki aşamaya geçmenizi sağlayan tüm olası hareketlerden oluşan bir ağaç şeklinde bir yapıdır.

Bir oyun, aşağıdaki bileşenlerle bir arama problemi olarak tanımlanabilir:

• İlk durum : Tahtanın pozisyonunu ve hareketinin kim olduğunu gösterir.
• Halef işlevi : Bir oyuncunun yapabileceği yasal hamlelerin ne olduğunu tanımlar.
• Terminal durumu : Oyun bittiğinde tahta pozisyonudur.
• Fayda fonksiyonu : Bir oyunun sonucuna sayısal bir değer atayan bir fonksiyondur. Örneğin, satrançta veya tic-tac-toe’da, sonuç ya bir kazanç, bir kayıp ya da beraberliktir ve bunlar sırasıyla +1, -1 ya da 0 değerleri ile gösterilebilir. Çok daha geniş bir sonuç yelpazesine sahip oyunlar var; örneğin, tavladaki yardımcı programlar +192 ile -192 arasında değişmektedir. Bir yardımcı fonksiyon aynı zamanda bir geri ödeme fonksiyonu olarak da adlandırılabilir.

Algoritma nasıl çalışır?

Bir oyuna MIN ve MAX denilen iki oyuncu var. MAX oyuncusu mümkün olan en yüksek puanı almaya çalışır ve MIN mümkün olan en düşük puanı almaya çalışır, yani, MIN ve MAX birbirleriyle zıt davranmaya çalışırlar.

Minimax algoritmasının genel süreci aşağıdaki gibidir:

Adım 1 : Öncelikle, oyunun mevcut durumundan başlayarak terminal durumlarına kadar oyun ağacının tamamını oluşturun. Oyun ağacı oyun tic-tac-toe için böyle görünüyor.

Tanımlanan terminolojiyi yukarıdaki şemaya göre anlayalım.

1. İlk durum, tahtanın boş olduğunu tanımlayan ilk katmandır ve MAX’ın oynama sırasıdır.
2. Halefi işlevi, olası tüm halefi hareketlerini listeler. Ağaçtaki tüm katmanlar için tanımlanmıştır.
3. Terminal Durumu ağacın son halini gösteren son katmandır, yani MAX oyuncunun kazanması, kaybetmesi veya rakibe bağlanması gibi.
4. Terminal durumlar için bu durumda yardımcı programlar, daha önce tartışıldığı gibi 1, 0 ve -1’dir ve diğer düğümlerin yardımcı programlarını da belirlemek için kullanılabilirler.

Adım 2 : Tüm terminal durumları için yardımcı değer elde etmek için yardımcı program işlevini uygulayın.
Adım 3 : Terminal düğümlerin yardımcı programlarının yardımıyla daha yüksek düğümlerin yardımcı programlarını belirleyin. Örneğin, aşağıdaki şemada, meydanlarda yazılan terminal durumları için yardımcı programlara sahibiz.

Terminalin üstündeki katmanın sol düğümü (kırmızı) için yardımcı programı hesaplayalım. MIN oyuncunun hamlesi olduğu için tüm hizmetlerin minimumunu seçeceğiz. Bu durumda, kesinlikle 3 olduğunu bildiğimiz MIN {3, 5, 10} değerini değerlendirmek zorundayız. Bu nedenle, kırmızı düğümün faydası 3’tür.

Adım 4 : Ağacın köküne kadar her seferinde bir katman göz önüne alınarak yaprakların yardımıyla fayda değerlerini hesaplayın.
Adım 5 : Sonunda, tüm yedeklenen değerler ağacın köküne, yani en üst noktaya ulaşır. Bu noktada, MAX en yüksek değeri seçmek zorundadır.

Örneğimizde, sadece 3 katmana sahibiz, bu yüzden hemen kökündeyiz, ancak gerçek oyunlarda, çok daha fazla katman ve düğüm olacaktır. Bu yüzden 3 olan MAX {3,2} ‘yi değerlendirmek zorundayız.

Bu nedenle, MAX için en iyi açılış hareketi sol düğümdür (veya kırmızı olan). Bu hamleye minimax kararı denir ve rakibin de en aza indirmek için en iyi şekilde oynadığı varsayımı sonrasında aracı en üst seviyeye çıkarır.

Özetlemek,

Minimax Kararı = MAX {MIN {3,5,10}, MIN {2,2}}
= MAX {3,2}
= 3

function minimax(node, depth, maximizingPlayer)
            if depth = 0 or node is a terminal node
                   return the utility of the node

            if maximizingPlayer
                   bestValue := ??
            for each child of node
                   v := minimax(child, depth ? 1, FALSE)
                   bestValue := max(bestValue, v)
            return bestValue  

            else (* minimizing player *)
                   bestValue := +?
                   for each child of node
                          v := minimax(child, depth ? 1, TRUE)
                          bestValue := min(bestValue, v)
                   return bestValue

Optimizasyon

Oyun ağaçları, genel olarak, inşa etmek çok zaman alır ve sadece kısa sürede üretilebilecek basit oyunlar içindir.

Eğer varsa b yasal hamleler, yani b Her noktadaki düğümler ve ağacın maksimum derinliği mminimax algoritmasının zaman karmaşıklığı düzendedir bm( O ( b)m) ).

Bu durumu ortadan kaldırmak için, algoritmaya eklenebilecek birkaç optimizasyon vardır.

Neyse ki, oyun ağacının her düğümüne bakmadan gerçek minimax kararını bulmak mümkün. Dolayısıyla, düğümleri analiz etmeden ağaçtan kaldırıyoruz ve bu işleme budama denir.

Alfa-beta budama

Bu makalede inceleyeceğimiz yönteme alfa-beta budaması deniyor.

Alfa-beta budamasını standart bir minimax algoritmasına uygularsak, standart olanla aynı hareketi döndürür, ancak nihai kararı etkilemeyen tüm düğümleri kaldırır (erik).

Önce bunun arkasındaki sezgiyi anlayalım, sonra algoritmayı resmileştirelim. Diyelim ki şu oyun ağacına sahibiz:

Bu durumda,
Minimax Kararı = MAX {MIN {3,5,10}, MIN {2, a, b}, MIN {2,7,3}}
= MAX {3, c, 2}
= 3

Şaşırdın!

Maksimum değeri eksik bir değerle nasıl hesaplayabiliriz? İşte hile. MIN {2, a, b} kesinlikle 2’den küçük veya ona eşit olacaktır, yani c <= 2 ve bu nedenle MAX {3, c, 2}, 3 olmalıdır.

Şimdi soru şu ki c’yi gerçekten hesaplamamız gerekiyor mu? Tabii ki değil.

Bu düğümlere bakmadan sonuca varabilirdik. Ve burası alfa-beta budamasının resmin içine girdiği yer.

Birkaç tanım:

Alfa: MAX oyuncu için şimdiye kadarki en iyi seçimdir. Burada mümkün olan en yüksek değeri elde etmek istiyoruz.
Beta: MIN için şu ana kadarki en iyi seçim ve mümkün olan en düşük değer olması gerekiyor.

Not: Her düğümün alfa ve beta değerlerini izlemesi gerekir. Alpha yalnızca MAX’ın sırası geldiğinde ve benzer şekilde beta yalnızca MIN’in şansı olduğunda güncellenebilir.

Alfa-beta budama nasıl çalışır?

1. Mümkün olan en kötü durum olarak alfa = -finity ve beta = sonsuzluğu başlat. Bir düğümü budama koşulu, alfa beta değerinden büyük veya ona eşit olduğunda meydana gelir.

1. Alfa ve beta’nın başlangıç ​​değerlerini kök dizinine atama ile başlayın ve alfa betadan daha küçük olduğu için bunu budamıyoruz.
2. Bu alfa ve beta değerlerini soldaki alt düğüme taşıyın. Ve şimdi terminal durumunun fayda değerinden, alpha ve be’nin değerlerini güncelleyeceğiz, bu yüzden beta değerini güncellememiz gerekmiyor. Yine, budama yapmayız çünkü durum aynı kalır. Benzer şekilde, üçüncü çocuk düğümü de. Daha sonra kök dizinine geri dönüyoruz, alpha = 3 olarak ayarlıyoruz, çünkü bu, alfa değerinin sahip olabileceği minimum değerdir.

1. Şimdi, alfa = 3 ve beta = kökündeki sonsuzluk. Yani biz budamıyoruz. Bunu merkez düğüme taşıyan ve MIN {2, sonsuz} değerini hesaplayarak alfa = 3 ve beta = 2 elde ederiz.
2. İkinci ve üçüncü alt düğümleri budama çünkü alfa şimdi betadan büyüktür.
3. Kökteki alfa 3 olarak kalır çünkü 2’den büyüktür. Bunu en sağ alt düğüme taşıyan MIN (sonsuz, 2} = 2) değerini değerlendirin. Beta’yı 2’ye güncelleyin ve alfa 3 kalır.
4. İkinci ve üçüncü alt düğümleri budama çünkü alfa şimdi betadan büyüktür.
5. Dolayısıyla sırasıyla sol, orta ve sağ MIN düğümlerinde 3, 2, 2 alıyoruz. Ve MAX {3,2,2} ‘yi hesaplarsak, 3 elde ederiz. Bu nedenle, dört yaprağı izlemeden minimax kararını doğru bir şekilde bulabiliriz.

evaluate (node, alpha, beta)
     if node is a leaf
        return the utility value of node
     if node is a minimizing node
        for each child of node
            beta = min (beta, evaluate (child, alpha, beta))
            if beta <= alpha
                return beta
            return beta
     if node is a maximizing node
        for each child of node
            alpha = max (alpha, evaluate (child, alpha, beta))
            if beta <= alpha
                return alpha
            return alpha

Sonuç

Oyunlar çok çekici ve oyun oynama programları yazmak belki de daha heyecan verici. Grand Prix yarışlarının otomobil endüstrisi için ne olduğu, oyun oynamak AI’dir.

Bir yarış arabasının engebeli bir yolda mükemmel şekilde çalışmasını beklemeyeceğimiz gibi, oyun oynama algoritmalarının her durum için mükemmel olmasını beklememeliyiz.

Minimax algoritması da öyle. AI olması gereken her türlü bilgisayar oyunu için en iyi çözüm olmayabilir.

Ancak iyi bir uygulama verildiğinde, zorlu bir rakip oluşturabilir.