logo

Çelişkili Arama

Ç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ş
    Mükemmel bilgi:Mükemmel bilgiye sahip bir oyun, temsilcilerin tahtanın tamamına bakabildiği oyundur. Temsilciler oyunla ilgili tüm bilgilere sahiptir ve birbirlerinin hareketlerini de görebilirler. Örnekler Satranç, Dama, Go vb.'dir.Eksik bilgi:Bir oyundaki temsilciler oyun hakkında tüm bilgilere sahip değilse ve olup bitenden haberdar değilse, bu tür oyunlara tic-tac-toe, Battleship, kör, Köprü vb. gibi kusurlu bilgi içeren oyun adı verilir.Deterministik oyunlar:Deterministik oyunlar, oyunlar için katı bir model ve kurallar dizisi izleyen oyunlardır ve bunlarla ilişkili hiçbir rastgelelik yoktur. Örnekler satranç, Dama, Go, tic-tac-toe vb.'dir.Deterministik olmayan oyunlar:Belirleyici olmayan, çeşitli öngörülemeyen olaylara sahip olan ve şans veya şans faktörüne sahip olan oyunlardır. Bu şans veya şans faktörü, zar veya kartlarla ortaya çıkar. Bunlar rastgeledir ve her eylem yanıtı sabit değildir. Bu tür oyunlara stokastik oyunlar da denir.
    Ö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:

    Başlangıç ​​hali:Oyunun başlangıçta nasıl kurulacağını belirtir.Oyuncu(lar):Durum uzayında hangi oyuncunun hareket ettiğini belirtir.Hareketler):Durum uzayındaki yasal hamlelerin kümesini döndürür.Sonuç(lar, a):Durum uzayındaki hareketlerin sonucunu belirleyen geçiş modelidir.Terminal Testi/Testleri:Terminal testi oyun bittiyse doğrudur, aksi halde her durumda yanlıştır. Oyunun bittiği duruma terminal durumları denir.Fayda(lar, p):Bir yardımcı işlev işlevi, p oyuncusu için terminal durumları s ile biten bir oyunun son sayısal değerini verir. Buna ödeme fonksiyonu da denir. Satranç için sonuçlar galibiyet, mağlubiyet veya beraberliktir ve getiri değerleri +1, 0, ½'dir. Ve tic-tac-toe için fayda değerleri +1, -1 ve 0'dır.

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.
Çelişkili Arama

Ö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:

Çelişkili Arama