Minimax Algoritmasını Kullanarak XOX Oyunu Yapalım - 1. Bölüm

Merhaba arkadaşlar,

Öncelikle bu yazı benim ilk paylaşımım olacak. Blogumda elimden geldiğimce bildiklerimi ve öğrendiklerimi paylaşmaya çalışacağım. Bu yazımda ise size Minimax algoritmasından bahsedeceğim.

Geçen sene satranca ve satranç motorlarının kullandığı yapay zekaya ilgimden dolayı, bir satranç motoru programlamaya heveslenmiştim. Bu hevesim beni doğal olarak yapay zeka algoritmalarını araştırmaya götürdü. Planımda bu işin kolayından başlayıp zora gitmek vardı, ilk olarak XOX oyunu yapacaktım, sonrasında bir dama oyunu ve en son olarak da satranç motoru. Fakat çok zahmetli bir iş olmasından dolayı bir yerden sonra bu hevesimden vazgeçtim.

Minimax Nedir?

Zeka oyunlarında kullanılan bir yapay zeka tekniğidir. Bu algoritmayı kullanacağımız oyunlar şu koşulları sağlamalıdır:

• Oyunun iki kişilik olması gerekir.
• Oyunun karşılıklı sırayla oynanması gerekir.
• İki oyuncu da rakibinin yapabileceği bütün olası hamleleri bilmelidir. (Oyun şans oyunu olmamalı)
• Oyunun sonlu olması gerekir.

Bu koşulları sağlayan oyunlara Satranç, Dama, XOX, Go gibi örnekler verilebilir. Minimax yönteminin temel mantığı oyundaki tarafların yapabileceği en iyi hamleleri bulup, ona göre bir arama yapmasıdır.


XOX oyunu (veya Tic Tac Toe) mantığını sanırım biliyorsunuz. Bilmeyenler için: iki oyuncudan biri X, diğeri ise O harfini kullanır. 3x3'lük bir tahtada her oyuncu hamlesinde tahtadaki istediği bir kareye kendi harfini koyar. 3 tane harfi yan yana veya çapraz olarak getiren (XXX veya OOO) kazanır. Bu durum sağlanamazsa oyun berabere biter.

Algoritmanın mantığını bu oyun üzerinden anlatmayı uygun gördüm. Bir XOX oyununda gelinen konum aşağıdaki gibidir (Şekil 1.1).

Şekil 1.1

Sıra X oyuncusundadır. Oyuncunun yapması gereken görüldüğü üzere iki tane O harfinin arasındaki kareye X koyup rakibinin kazanmasını engellemektir. Peki bu hamleyi bulmak için nasıl bir mantık üretmeliyiz?

Öncelikle konumda oluşabilecek olası hamleleri yazarak bir ağaç oluşturalım (Şekil 1.2).

Şekil 1.2

Bu işlemi oyunun sonuna ulaşana kadar tekrarlayıp ağacımızı oluşturmayı sonlandıralım (Şekil 1.3).

Şekil 1.3

Böylece bütün ihtimalleri oluşturmuş olduk. Öncelikle bahsetmek istediğim bir kaç nokta var. Oluşturduğumuz ağaç 3 seviyeli bir ağaçtır, yani 3 seviye derinliğe inmiş olduk. Bu seviyeye biz ply diyoruz. Satranç, Go gibi oyunlarda olasılık sayısı çok fazla olduğu için bilgisayar hepsini hesaplayamaz. Bu yüzden bu tür oyunlarda ineceğimiz derinlik belirli bir seviyenin altında tutulur. Fakat XOX oyunu (berabere olduğu) çözülmüş bir oyundur ve son derinliğe kadar hesaplayabiliriz.

Bizim bu noktada ihtiyacımız olan ulaştığımız konumlar hakkında bir değerlendirme (evaluation) yapmaktır. Biz basit bir şekilde X'in kazanma durumunu "1", beraberlik durumu "0", O'nun kazanma durumunu ise "-1" ile değerlendirelim. Bu değerlendirme fonksiyonunu en son ulaştığımız konumlara, yani ağacın yapraklarına (leaf) uygulayalım (Şekil 1.4).

Şekil 1.4

Bilgisayarımız X oyuncusu olduğu için maksimum olan skoru seçmek ister. Yani skoru 1 olan konuma girmek ister. Fakat X oyuncusunun bu seviyede oynayacak 1 hamlesi olduğu için skorları direkt olarak üst seviyeye taşımak mecburiyetindeyiz. (Şekil 1.5).

Şekil 1.5

Bu seviyede hamle O oyuncusundadır. O oyuncusu da minimum olan skoru seçmek ister. Çünkü O oyuncusunun kazanma skorunu -1 olarak tanımlamıştık. Bu yüzden skorları bir üste taşırken minimum olanını seçmeliyiz (Şekil 1.6).

Şekil 1.6

Bu seviyede hamle X oyuncusundadır. X oyuncusu maksimum olan skoru seçtiğine göre ihtimallerdeki skorların maksimum olanını bir üste taşıyoruz (Şekil 1.7)

Şekil 1.7

Sonuç olarak ağacımızın köküne (root) 0 taşımış olduk. Bu da demek oluyor ki, bilgisayar 0 skorunun olduğu hamleyi (ağacın ortasındaki dal) oynayacak, ve hesabına göre doğru hamleler oynandığında oyun 0 skorunun temsil ettiği "beraberlik" ile sonuçlanacaktır.

Dikkat ettiyseniz ağacın her seviyesinde bir maximum, bir minumum değerleri alarak işlemimize devam ettik. Minimax ismi de zaten buradan gelmektedir. Bu işlem yapılarak iki tarafın da en doğru hamleleri oynaması amaçlanır (Şekil 1.8).

Şekil 1.8

Bu yazımda elimden geldiğince minimax algoritmasının mantığını anlatmaya çalıştım. 2. Bölümde işin programlama kısmına değineceğim. Bir sonraki yazıda görüşmek dileğiyle... :)