Çekişmeli arama, dünyanın ilerisini planlamaya çalıştığımızda ve diğer ajanların bize karşı plan yaptığında ortaya çıkan sorunu incelediğimiz bir aramadır.
- Önceki konularda, genellikle bir dizi eylem şeklinde ifade edilen, çözümü bulmayı amaçlayan, yalnızca tek bir etmenle ilişkilendirilen arama stratejilerini incelemiştik.
- Ancak birden fazla temsilcinin aynı arama alanında çözüm aradığı durumlar da olabilir ve bu durum genellikle oyun oynarken ortaya çıkar.
- Birden fazla aracının bulunduğu ortama ne ad verilir? çok aracılı ortam Her temsilcinin diğer temsilcinin rakibi olduğu ve birbirlerine karşı oynadığı. Her temsilcinin diğer temsilcinin eylemini ve bu eylemin performansı üzerindeki etkisini dikkate alması gerekir.
- Bu yüzden, Çatışan hedeflere sahip iki veya daha fazla oyuncunun çözüm için aynı arama alanını keşfetmeye çalıştığı aramalara, genellikle Oyunlar olarak bilinen, çekişmeli aramalar denir. .
- Oyunlar bir Arama problemi ve buluşsal değerlendirme işlevi olarak modellenmiştir ve bunlar yapay zekada oyunların modellenmesine ve çözülmesine yardımcı olan iki ana faktördür.
Yapay Zekadaki Oyun Türleri:
Deterministik | Şans Hareketleri | |
---|---|---|
Mükemmel bilgi | Satranç, Dama, git, Othello | Tavla, tekel |
Kusurlu bilgi | Savaş gemileri, kör, tic-tac-toe | Köprü, poker, scrabble, nükleer savaş |
Örnek: Tavla, Tekel, Poker vb.
Not: Bu başlıkta deterministik oyunları, tamamen gözlemlenebilir ortamı, sıfır toplamlıyı ve her aracının alternatif olarak hareket ettiği yerleri tartışacağız.
Sıfır Toplamlı Oyun
- Sıfır toplamlı oyunlar, saf rekabeti içeren çekişmeli aramalardır.
- Sıfır toplamlı oyunda her bir aracının fayda kazancı veya kaybı, başka bir aracının fayda kayıpları veya kazançları ile tam olarak dengelenir.
- Oyunun bir oyuncusu tek bir değeri maksimuma çıkarmaya çalışırken diğer oyuncu onu en aza indirmeye çalışır.
- Oyunda bir oyuncunun yaptığı her hamleye kat adı verilir.
- Satranç ve tic-tac-toe, Sıfır toplamlı oyunun örnekleridir.
Sıfır toplamlı oyun: Gömülü düşünme
Sıfır toplamlı oyun, bir temsilcinin veya oyuncunun aşağıdakileri anlamaya çalıştığı gömülü düşünmeyi içeriyordu:
yazılım testi
- Ne yapalım.
- Harekete nasıl karar verilir?
- Rakibini de düşünmesi gerekiyor
- Rakip de ne yapacağını düşünüyor
Oyuncuların her biri, rakibinin eylemlerine verdiği tepkiyi bulmaya çalışıyor. Bu, yapay zekadaki oyun sorunlarını çözmek için yerleşik düşünmeyi veya geriye dönük akıl yürütmeyi gerektirir.
Sorunun resmileştirilmesi:
Bir oyun, yapay zekada aşağıdaki unsurlarla resmileştirilebilen bir arama türü olarak tanımlanabilir:
Oyun ağacı:
Oyun ağacı, ağacın düğümlerinin oyun durumları ve ağacın kenarlarının oyuncuların hareketleri olduğu bir ağaçtır. Oyun ağacı başlangıç durumunu, eylem fonksiyonunu ve sonuç Fonksiyonunu içerir.
Örnek: Tic-Tac-Toe oyun ağacı:
kurt tilkiye karşı
Aşağıdaki şekil tic-tac-toe oyunu için oyun ağacının bir kısmını göstermektedir. Aşağıda oyunun bazı önemli noktaları verilmiştir:
- MAX ve MIN olmak üzere iki oyuncu vardır.
- Oyuncuların alternatif bir sırası vardır ve MAX ile başlarlar.
- MAX oyun ağacının sonucunu maksimuma çıkarır
- MIN sonucu en aza indirir.
Örnek Açıklama:
- Başlangıç durumundan itibaren MAX'ın ilk başladığı için 9 olası hamlesi vardır. MAX yer x ve MIN yer o ve her iki oyuncu da, bir oyuncunun arka arkaya üç taneye sahip olduğu veya tüm karelerin dolduğu bir yaprak düğümüne ulaşana kadar dönüşümlü olarak oynar.
- Her iki oyuncu da her düğümü, minimax'ı, optimum rakibe karşı elde edilebilecek en iyi fayda olan minimax değerini hesaplayacaktır.
- Her iki oyuncunun da tic-tac-toe oyununun farkında olduğunu ve en iyi oyunu oynadığını varsayalım. Her oyuncu bir diğerinin kazanmasını engellemek için elinden geleni yapıyor. MIN oyunda Max'e karşı hareket ediyor.
- Yani oyun ağacında bir Max katmanımız, bir MIN katmanımız var ve her katmana şu ad veriliyor: Kat . Maksimum yere x, ardından MIN, Max'in kazanmasını önlemek için o koyar ve bu oyun terminal düğümüne kadar devam eder.
- Bunda ya MIN kazanır, MAX kazanır ya da beraberlik olur. Bu oyun ağacı, MIN ve MAX'ın tic-tac-toe oynaması ve dönüşümlü olarak oynaması olasılıklarının tüm arama alanıdır.
Dolayısıyla minimaks prosedürü için çekişmeli Arama şu şekilde çalışır:
numpy sıfırlar
- MAX'ın oyunu kazanması için en uygun stratejiyi bulmayı amaçlamaktadır.
- Derinlik öncelikli arama yaklaşımını takip eder.
- Oyun ağacında, ağacın herhangi bir derinliğinde en uygun yaprak düğümü görünebilir.
- Minimax değerlerini terminal düğümü keşfedilene kadar ağaca kadar yayın.
Belirli bir oyun ağacında, her düğümün MINIMAX(n) olarak yazılabilen minimax değerinden optimal strateji belirlenebilir. MAX maksimum değer durumuna geçmeyi tercih eder ve MIN minimum değer durumuna geçmeyi tercih eder, o zaman: