Masa Oyunu Yapay Zekası: Minimax Algoritması: 8 Adım

2024 Yazar: John Day | [email protected]. Son düzenleme: 2024-01-30 13:18

Satrançta veya damada oynadığınız bilgisayarların nasıl yapıldığını hiç merak ettiniz mi? Minimax Algoritmasını kullanarak nasıl basit ama etkili bir yapay zeka (AI) yapacağınızı göstereceğinden, bu Eğitilebilir Tablodan başka bir yere bakmayın! AI, Minimax Algoritmasını kullanarak iyi planlanmış ve düşünülmüş hamleler yapar (veya en azından bir düşünce sürecini taklit eder). Şimdi, sana yaptığım yapay zekanın kodunu verebilirdim ama bu eğlenceli olmazdı. Bilgisayarın seçimlerinin arkasındaki mantığı açıklayacağım.

Bu Eğitilebilir Kitapta, python'da Othello (AKA Reversi) için nasıl AI yapılacağına ilişkin adımlarda size yol göstereceğim. Bu projeyle uğraşmadan önce python'da nasıl kod yazılacağını orta düzeyde anlamalısınız. Sizi bu Eğitilebilir Yazıya hazırlamak için bakmanız gereken birkaç iyi web sitesi: w3schools veya Learnpython. Bu Eğitilebilirliğin sonunda, hesaplanmış hareketler yapacak ve çoğu insanı yenebilecek bir yapay zekaya sahip olmalısınız.

Bu Eğitilebilir Kitap, öncelikle bir AI'nın nasıl yapılacağı ile ilgileneceğinden, python'da bir oyunun nasıl tasarlanacağını açıklamayacağım. Bunun yerine, bir insanın başka bir insana karşı oynayabileceği ve onu değiştirebileceği oyunun kodunu vereceğim, böylece bir insanın AI'ya karşı oynadığı bir oyun oynayabilirsiniz.

Columbia SHAPE'deki bir yaz programı aracılığıyla bu yapay zekayı nasıl oluşturacağımı öğrendim. Orada iyi vakit geçirdim, bu yüzden ilgilenip ilgilenmeyeceğini görmek için web sitelerine bir göz atın.

Artık lojistiği aradan çıkardığımıza göre, kodlamaya başlayalım!

(Resimlere bir kaç not koydum, bakmayı unutmayın)

Gereçler

Bu kolay:

1) Spyder veya IDLE gibi bir python ortamına sahip bilgisayar

2) Othello oyununun dosyalarını GitHub'dan indirin

3) Sabır yüklü beyniniz

Adım 1: Gerekli Dosyaları İndirin

GitHub'uma girdiğinizde 5 dosya görmelisiniz. 5'ini de indirin ve hepsini aynı klasöre yerleştirin. Oyunu çalıştırmadan önce spyder ortamındaki tüm dosyaları açın.

İşte dosyaların yaptığı şey:

1) othello_gui.py bu dosya, oyuncuların (ister insan ister bilgisayar olsun) oynayabileceği oyun tahtasını oluşturur.

2) othello_game.py bu dosya gameboard olmadan iki bilgisayarı birbirine karşı oynar ve sadece skor ve hareket pozisyonlarını gösterir.

3) ai_template.py, AI'nızı yapmak için tüm kodunuzu koyacağınız yer burasıdır.

4) randy_ai.py bu, hareketlerini rastgele seçen önceden hazırlanmış bir yapay zekadır.

5) othello_shared.py, mevcut hamleleri, skoru veya tahta durumunu kontrol etmek gibi AI'nızı yapmak için kullanabileceğiniz bir dizi önceden yapılmış işlev

6) Diğer üç dosya: Puma.py, erika_5.py ve nathan.py, SHAPE programından sırasıyla ben, Erika ve Nathan tarafından yapılmıştır, bunlar benzersiz kodlara sahip üç farklı AI'dır.

Adım 2: Python Othello Nasıl Açılır ve Oynanır

Tüm dosyaları açtıktan sonra, ekranın sağ alt köşesinde "run othello_gui.py" yazın ve IPython Konsolunda enter tuşuna basın. Veya Mac terminalinde "python othello_gui.py" yazın (elbette doğru klasöre girdikten sonra). Ardından ekranınızda bir tahta açılmalıdır. Bu mod, insan ve insan modudur. Işık ikinci, karanlık önce gider. Kafanız karıştıysa videoma bakın. iEn üstte, her bir renk döşemesinin puanı bulunur. Oynamak için, oraya bir karo yerleştirmek için geçerli bir hareket boşluğuna tıklayın ve ardından bilgisayarı, aynısını yapacak ve tekrar edecek rakibinize verin.

Othello'yu nasıl oynayacağınızı bilmiyorsanız, ultra boards web sitesinden şu kuralları okuyun:

Siyah her zaman önce hareket eder. Oyuncunun renginde bir diski, rakibin disklerinden bir veya daha fazlasını "yan dışına" gelecek şekilde tahtaya yerleştirerek bir hamle yapılır. Bir disk veya disk sırası, uçlarında zıt renkte disklerle çevrili olduğunda, dış çevrilir. Bir disk, herhangi bir yönde (yatay, dikey, diyagonal) bir veya daha fazla sıradaki herhangi bir sayıda diski geçebilir…. (kendi web sitesinde okumayı bitirin)

Orijinal oyun ile bu python oyunu arasındaki fark, bir oyuncu için geçerli hamle kalmadığında oyunun sona ermesidir

Artık oyunu bir arkadaşınızla oynayabileceğinize göre, birlikte oynayabileceğiniz bir yapay zeka yapalım.

Adım 3: Minimax Algoritması: Senaryolar Oluşturma

Bunu kodda nasıl yazacağımızdan bahsetmeden önce, arkasındaki mantığı gözden geçirelim. Minimax algoritması bir karar verme, geri izleme algoritmasıdır ve tipik olarak iki oyunculu, sıra tabanlı oyunlarda kullanılır. Bu yapay zekanın amacı, oyunu kazanana kadar bir sonraki en iyi hamleyi ve sonraki en iyi hamleleri bulmaktır.

Şimdi algoritma hangi hareketin en iyi hamle olduğunu nasıl belirleyecek? Durun ve bir sonraki hamleyi nasıl seçeceğinizi düşünün. Çoğu insan onlara en çok puanı verecek hamleyi seçer, değil mi? Ya da ileriyi düşünüyorlarsa, daha da fazla puan kazanabilecekleri bir durum oluşturacak hamleyi seçerlerdi. İkinci düşünme biçimi, Minimax Algoritmasının düşünme biçimidir. Gelecekteki tüm kurul kurulumlarına bakar ve en çok puana yol açacak hamleyi yapar.

Bunu bir geri izleme algoritması olarak adlandırdım, çünkü ilk önce gelecekteki tüm yönetim kurulu durumlarını ilişkili değerleriyle oluşturup değerlendirerek başlar. Bu, oyunun her senaryosu oynanana kadar algoritmanın oyunu gerektiği kadar oynayacağı (hamleleri kendisi ve rakibi için yaparak) anlamına gelir. Tüm pano durumlarını (senaryoları) takip etmek için bir ağaç çizebiliriz (resimlere bakın). Yukarıdaki resimdeki ağaç, Connect 4 oyununun basit bir örneğidir. Her tahta konfigürasyonuna tahta durumu ve ağaç üzerindeki yerine düğüm denir. Ağacın altındaki tüm düğümler, tüm hamleleri yaptıktan sonraki son tahta durumlarıdır. Açıkçası bazı yönetim kurulu durumları bir oyuncu için diğerinden daha iyidir. Şimdi, AI'nın hangi yönetim kurulu durumuna ulaşmak istediğini seçmesini sağlamalıyız.

Adım 4: Minimax: Kart Konfigürasyonlarının Değerlendirilmesi

Kurul durumlarına değer vermek için oynadığımız oyunun stratejilerini öğrenmeliyiz: bu durumda Othello'nun stratejilerini. Bu oyun rakibin ve sizin disklerinizi çevirme savaşı olduğundan, en iyi disk konumları sabit olan ve ters çevrilemeyen konumlardır. Örneğin köşe, bir disk yerleştirildiğinde diğer renge değiştirilemediği yerdir. Böylece, o nokta son derece değerli olacaktır. Diğer iyi pozisyonlar, çok fazla taş almanıza izin verecek olan tahtanın kenarlarını içerir. Bu web sitesinde daha fazla strateji var.

Artık her bir board state board için pozisyonlara değerler atayabiliriz. Bir pozisyon AI'nın taşı tarafından işgal edildiğinde, pozisyona bağlı olarak belirli sayıda puan verirsiniz. Örneğin, AI'nın taşının köşede olduğu bir tahta durumu, 50 puanlık bir bonus verebilirsiniz, ancak elverişsiz bir noktada olsaydı, taş 0 değerine sahip olabilir. pozisyonlar, yönetim kurulu durumuna bir değer atarsınız. Örneğin, AI'nın köşede bir taşı varsa, tahta durumu 50 puan alabilirken, AI'nın taşı ortada olan başka bir tahta durumu 10 puan alabilir.

Bunu yapmanın birçok yolu var ve tahta parçalarını değerlendirmek için üç farklı buluşsal yöntemim var. Sizi kendi buluşsal türünüzü yapmaya teşvik ediyorum. Github'uma üç farklı yaratıcı tarafından üç farklı buluşsal yöntem ile üç farklı yapay zeka yükledim: Puma.py, erika5.py, nathanh.py.

Adım 5: Minimax Algoritması: En İyi Hareketi Seçme

Şimdi AI en yüksek puanla tahta durumuna geçmek için tüm hamleleri seçebilseydi iyi olurdu. Ancak, AI'nın tüm tahta durumlarını oluştururken rakibin hamlelerini de seçtiğini ve rakip akıllıysa, AI'nın en yüksek tahta puanına ulaşmasına izin vermeyeceğini unutmayın. Bunun yerine, akıllı bir rakip, AI'yı en düşük tahta durumuna getirmek için hamle yapacaktı. Algoritmada iki oyuncuya maksimize eden oyuncu ve minimize eden oyuncu diyoruz. AI, kendisi için en fazla puanı almak istediğinden, en üst düzeye çıkaran oyuncu olacaktır. Rakip, AI'nın en az puanı aldığı hareketi yapmaya çalıştığından, rakip en aza indiren oyuncu olacaktır.

Tüm pano durumları oluşturulduktan ve panolara değerler atandıktan sonra, algoritma pano durumlarını karşılaştırmaya başlar. Resimlerde, algoritmanın hareketlerini nasıl seçeceğini gösteren bir ağaç oluşturdum. Dallardaki her bölünme, yapay zekanın veya rakibin oynayabileceği farklı bir harekettir. Düğüm sıralarının soluna, maksimize eden oyuncunun mu yoksa minimize eden oyuncunun mu gittiğini yazdım. Alt sıra, değerleriyle birlikte tüm pano durumlarıdır. Bu düğümlerin her birinin içinde bir sayı vardır ve bunlar her bir panoya atadığımız puanlardır: bunlar ne kadar yüksekse, AI için o kadar iyi olur.

Tanımlar: üst düğüm - altında düğüm oluşturan veya oluşturan bir düğüm; alt düğümlerin kökeni - aynı ana düğümden gelen düğümler

Boş düğümler, AI'nın en iyi tahta durumuna ulaşmak için hangi hareketi yapacağını temsil eder. En soldaki düğümün çocuklarını karşılaştırmakla başlar: 10, -3, 5. Maksimize eden oyuncu hamleyi yapacağından, kendisine en fazla puanı verecek hamleyi seçecektir: 10. Böylece, bunu seçip kaydediyoruz. tahta puanı ile hareket edin ve ana düğüme yazın. Şimdi 10 ana düğümde olduğuna göre, sıra en aza indirgeyen oyunculardadır. Ancak, 10 ile karşılaştıracağımız düğüm boştur, bu yüzden küçültme yapan oyuncunun seçim yapabilmesi için önce o düğümü değerlendirmeliyiz. Böylece, maksimize eden oyuncunun sırasına geri dönüyoruz ve bitişik düğümün çocuklarını karşılaştırıyoruz: 8, -2. Maksimize etmek 8'i seçecek ve bunu boş ana düğüme yazacağız. Algoritma, üstündeki bir düğümün çocukları için boş alanları doldurmayı bitirdiğine göre, simge durumuna küçültme yapan oyuncu bu çocukları 10 ve 8'i karşılaştırabilir ve 8'i seçebilir. Algoritma daha sonra bu işlemi tüm ağaç dolana kadar tekrarlar. Bu örneğin sonunda, 8 puanımız var. Bu, AI'nın rakibin en iyi şekilde oynadığını varsayarak oynayabileceği en yüksek tahta durumudur. Böylece AI, 8 board durumuna giden ilk hamleyi seçecek ve eğer rakip en iyi şekilde oynarsa, AI 8 board durumuna geçmek için tüm hamleleri oynamalıdır. (Resimlerimdeki notları takip edin)

Biliyorum bu çoktu. Bir şeyi anlamak için birinin sizinle konuşması gereken tiplerdenseniz, bunun arkasındaki fikri kavramama yardımcı olması için izlediğim birkaç video: 1, 2, 3.

Adım 6: Minimax Algoritması: Sözde kod

Minimax algoritmasının arkasındaki mantığı anladıktan sonra, wikipedia'dan bu sözde koda (tüm kodlar için evrensel olan işlevler) bir göz atın:

işlev minimax(düğüm, derinlik, maksimizasyonPlayer)

derinlik = 0 veya düğüm bir terminal düğüm ise

düğümün buluşsal değerini döndür

Eğer Player'ı maksimize ediyorsa

değer:= −∞

düğümün her çocuğu için

değer:= maks(değer, minimaks(alt, derinlik − 1, YANLIŞ))

geri dönüş değeri

else (* oyuncu küçültme *)

değer:= +∞

düğümün her çocuğu için

değer:= min(değer, minimaks(alt, derinlik − 1, DOĞRU))

geri dönüş değeri

Bu özyinelemeli bir işlevdir, yani bir durma noktasına ulaşana kadar kendini tekrar tekrar çağırır. İlk olarak fonksiyon, düğüm, derinlik ve sıranın kimde olduğu olmak üzere üç değer alır. Düğüm değeri, programın aramaya başlamasını istediğiniz yerdir. Derinlik, programın ne kadar arama yapmasını istediğinizdir. Örneğin benim ağaç örneğimde 3 hareketten sonra tüm tahta durumlarını aradığı için derinliği 3'tür. Elbette, AI'nın her tahta durumunu kontrol etmesini ve kazanan bir galibiyet seçmesini isteriz, ancak milyonlarca olmasa da binlerce tahta yapılandırmasının olduğu çoğu oyunda, evdeki dizüstü bilgisayarınız tüm bu yapılandırmaları işleyemez. Bu nedenle, AI'nın arama derinliğini sınırlandırıyoruz ve en iyi tahta durumuna gitmesini sağlıyoruz.

Bu sözde kod, önceki iki adımda açıkladığım işlemi yeniden üretiyor. Şimdi bunu bir adım daha ileri götürelim ve bunu python kodunda düzeltelim.

7. Adım: AI'nızı Ai_template.py ile Oluşturun

Minimax AI koduma bir göz atmadan önce, ai_template.py dosyası ve son adımda bahsettiğimiz sözde kod ile kendi AI'nızı yapmaya çalışın. AI şablonunda iki işlev vardır: def minimax_min_node(board, color) ve def minimax_max_node(board, color). Minimax fonksiyonunun kendini yinelemeli olarak çağırması yerine, birbirini çağıran iki farklı fonksiyonumuz var. Kurul durumlarını değerlendirmek için buluşsal yöntemi oluşturmak için kendi işlevinizi oluşturmanız gerekecektir. othello_shared.py dosyasında yapay zekanızı oluşturmak için kullanabileceğiniz önceden hazırlanmış işlevler vardır.

AI'nızı aldıktan sonra, onu randy_ai.py'ye karşı çalıştırmayı deneyin. İki ais'i birbirine karşı çalıştırmak için, mac terminaline "python othello_gui.py (ai dosya adını girin).py (dosya adını girin).py" yazın veya "run othello_gui.py (ai dosya adını girin).py" yazın. (dosya adını girin).py" ve doğru dizinde olduğunuzdan emin olun. Ayrıca, tam adımlar için videoma bakın.

Adım 8: AI Dövüşü Yapma Zamanı

Şimdi bir grup bilgisayar arkadaşınızı edinin ve kendi yapay zekalarını tasarlamalarını sağlayın! Sonra bir yarışma yapabilir ve yapay zekanızın bunu yapmasını sağlayabilirsiniz. Umarım kendi yapay zekanızı oluşturamasanız bile minimax algoritmasının nasıl çalıştığını anlayabilmişsinizdir. Herhangi bir sorunuz varsa, aşağıdaki yorumlarda herhangi bir soru göndermekten çekinmeyin.