Yapay Zekada Min Maks Algoritma: Bileşenler, Özellikler, Avantajlar ve Sınırlamalar

Halk arasında minimax olarak bilinen AI'daki min max algoritması, karar verme, oyun teorisi ve yapay zekada (AI) kullanılan bir geri izleme algoritmasıdır. Rakibin de en iyi şekilde oynadığını varsayarak, bir oyuncu için en uygun hareketi bulmak için kullanılır. Popüler iki oyunculu bilgisayar veya Chess, Tic-Tac-Toe, Checkers, Go gibi çevrimiçi oyunlar bu algoritmayı kullanır.

Bir adayın adım adım bir çözüme doğru kademeli olarak oluşturulacağı şekilde hesaplama sorunlarına bir çözüm bulmak için bir geri izleme algoritması kullanılır. Ve bir çözümü tamamlayamayan aday hemen terk edilir.

O nasıl çalışır?

AI'daki min max algoritmasında, Maximiser ve Minimiser olmak üzere iki oyuncu vardır. Her iki oyuncu da oyunu, mümkün olan en yüksek puanı veya maksimum faydayı elde etmeye çalışırken, rakip en düşük puanı veya minimum faydayı elde etmeye çalışırken oynar.

Her oyun tahtasının kendisine atanan bir değerlendirme puanı vardır, bu nedenle Maksimize edici maksimum değeri seçecek ve Minimizer karşı hamlelerle minimize edilmiş değeri seçecektir. Maximizer'ın üstünlüğü varsa, tahta puanı pozitif bir değer olacaktır ve Minimizer'ın üstünlüğü varsa, tahta puanı negatif bir değer olacaktır.

Bu, toplam fayda puanının iki oyuncu arasında bölündüğü sıfır toplamlı oyun konseptine dayanmaktadır. Böylece, bir oyuncunun puanındaki artış, rakip oyuncunun puanında bir azalmaya yol açarak toplam puanı her zaman sıfır yapar. Yani bir oyuncunun kazanması için diğerinin kaybetmesi gerekiyor.

Dünyanın en iyi Üniversitelerinden çevrimiçi Makine Öğrenimi Sertifikasyonu ve AI kurslarına katılın . Kariyerinizi hızlandırmak için Master, Executive PGP veya ACP kazanın.

AI'da min max algoritmasını yıkmak

Tüm oyun ağacı, yapay zekadaki min max algoritmasında derinlik öncelikli arama algoritması ile araştırılır . Tamamen ağacın terminal düğümüne kadar ilerler ve ardından ağaç boyunca geriye doğru ilerler.

Amaç, bir oyuncu için mümkün olan en iyi hamleyi bulmaktır. Bu, en iyi değerlendirme puanına sahip düğümü seçerek yapılabilir. Rakibin tüm potansiyel hamleleri değerlendirildikten sonra en iyi seçim yapılacaktır. Algoritma, olası tüm değerlere sonuna kadar bakar ve oyuncu için bir karar verir.

Kaynak

Yukarıdaki oyun ağacı, hareketleri değerlendirmek için kullanılan iç içe geçmiş bir veri yapısıdır. Burada kök düğüm, Düzey 1'e veya ana düğümlere ayrılan Düzey 0'dır, bu da Düzey 2'ye veya alt düğümlere daha da dallanır. Dallanma, sonsuz seviyelerin potansiyeline sahip olarak birçok seviyeye devam edebilir. Seviye 0, tahtanın mevcut durumu gibidir, Seviye 1 ise bir sonraki hamleye bağlı olarak tahtaların tüm olası durumlarıdır.

Böylece, Oyuncu 2 bir hamle yaptıysa, kök düğümün, Oyuncu 1'in hamlesini bekleyen tahtanın mevcut durumu olduğunu varsayabiliriz. Seviye 1 düğümleri, Oyuncu 1 için tüm olası hamleleri içerir ve Seviye 2 düğümleri, Oyuncu 1'in her olası hareketine dayalı olarak Oyuncu 2 için tüm olası hareketleri içerir.

Dört son durumun olduğu bir örnek düşünün ve bunlara ulaşmanın yolu bir ağacın kökünden dört yaprağına kadardır. Dört yaprağın değerleri solda 3, 6 ve sağda 4, 7'dir. Bir hamle yapma sırası Maximizer/Oyuncu 1'dedir. Algoritmayı yürütmek için her hareket için varsayımlar yapılmalıdır.

Oyuncu 1 sola gitmeyi seçerse, Küçültücü/Oyuncu 2, 3 ile 6 arasında en küçüğünü seçmek zorundadır ve bu nedenle 3'ü seçerler. Oysa Oyuncu 1 sağı seçerse, Oyuncu 2 minimum olan 4'ü seçer. iki değerden 4 ve 7. Böylece, Düzey 1 şimdi 3 ve 4 değerlerine sahiptir.

Oyuncu 1/Maximizer'ın sırası olduğundan, maksimum Seviye 1 düğümlerini seçmeleri gerekir. Böylece 3'ü seçecekler. O zaman en uygun seçenek sola gitmek.

AI'daki min max algoritmasının adımları aşağıdaki gibi ifade edilebilir:

1. Tüm oyun ağacını oluşturun.
2. Değerlendirme işlevine dayalı olarak yaprak düğümleri için puanları değerlendirin.
3. Yapraktan kök düğümlere geri dönüş:

Maximizer için maksimum puana sahip düğümü seçin.

Minimizer için minimum puana sahip düğümü seçin.

4. Kök düğümde, maksimum değere sahip düğümü seçin ve ilgili hareketi seçin.

Ayrıca Okuyun: Makine Öğrenimi Proje Fikirleri

AI'da min max algoritmasının özellikleri

• Algoritma tamamlandı, yani sonlu bir arama ağacında kesinlikle bir çözüm bulunacak.
• Her iki oyuncunun da en iyi şekilde oynaması optimaldir.
• Oyun ağacı için Derinlik-İlk Arama (DFS) nedeniyle, algoritmanın zaman karmaşıklığı O(b m )'dir, burada b dallanma faktörüdür ve m ağacın maksimum derinliğidir.
• DFS gibi, bu algoritmanın uzay karmaşıklığı O(bm)'dir.

Avantajlar

• Arama uzayının kapsamlı bir değerlendirmesi yapılır.
• AI'da karar vermek kolayca mümkündür.
• Bu algoritma ile yeni ve akıllı makineler geliştirilmektedir.

sınırlamalar

• Büyük dallanma faktörü nedeniyle, hedefe ulaşma süreci daha yavaştır.
• Tüm olası düğümlerin ve dalların değerlendirilmesi ve aranması, motorun performansını ve verimliliğini düşürür.
• Her iki oyuncunun da karar vermek için çok fazla seçeneği var.
• Zaman ve mekan kısıtlaması varsa, ağacın tamamını keşfetmek mümkün değildir.

Ancak Alfa-Beta Budama ile algoritma geliştirilebilir.

Çözüm

Bu makale, AI'daki min-max algoritmasının tüm yönlerini açıklamaktadır . İlk olarak, nerede kullanıldığına dair örneklerle teoriye bir giriş yapılır, ardından algoritmanın bir oyunda nasıl çalıştığına dair bir açıklama yapılır.

Algoritma, oyuncuların hamlelerine ve karşı hamlelerine dayanarak optimal bir hamle yapma kararının nasıl alındığını açıklamak için parçalanmıştır. Algoritmanın özellikleri daha sonra listelenir. Son olarak algoritmanın avantaj ve dezavantajlarına yer verilmiştir.

Makine öğrenimi hakkında daha fazla bilgi edinmek istiyorsanız, çalışan profesyoneller için tasarlanmış ve 450+ saat zorlu eğitim, 30'dan fazla vaka çalışması ve ödev, IIIT sunan IIIT-B & upGrad'ın Makine Öğrenimi ve Yapay Zeka alanında Yönetici PG Programına göz atın. -B Mezunu statüsü, 5'ten fazla pratik uygulamalı bitirme projesi ve en iyi firmalarla iş yardımı.