Rakip Tabanlı Arama ve Oyun Oynama
Rakip tabanlı arama, bir ajanın, zıt sonucu elde etmeye çalışan bir rakibe karşı bir oyun ağacında hamle seçmesi gereken rekabetçi ortamlardaki karar verme süreçlerinin incelenmesidir.
Tanım
Rakip tabanlı arama, oyuncuların sırayla hamle yaptığı bir oyun ağacını keşfederek, minimax prensibini (her oyuncu rakibin en iyi şekilde oynadığını varsayarak optimize eder) budama ve sezgisel değerlendirme ile birlikte kullanarak büyük ağaçlarla başa çıkmak için bir oyuncu için bir hamle hesaplamaktadır.
Kapsam
Bu konu, iki oyunculu, sıfır toplamlı, tam bilgiye sahip oyunlardaki aramayı kapsamaktadır: minimax karar kuralı, minimax'ın kanıtlanabilir şekilde alakasız dalları atlamasına olanak tanıyan alfa-beta budaması, tam olarak çözülemeyecek kadar büyük oyunlar için değerlendirme fonksiyonları ve derinlik sınırlı arama ile çok büyük dallanma faktörlerine sahip oyunlar için Monte Carlo ağaç araması. Oyun ağaçlarının nasıl modellendiği ve hesaplama sınırlamalarının sezgisel kesintileri nasıl zorunlu kıldığı ele alınmaktadır. Çoklu ajan teşviklerinin genel oyun teorik denge analizi bu konunun kapsamında değildir; bu konu çoklu ajan sistemleri altında ele alınmaktadır.
Temel sorular
- Minimax kuralı, optimal bir rakibe karşı optimal bir hamleyi nasıl belirler?
- Alfa-beta budaması, minimax değerini etkilemeden dalları nasıl ortadan kaldırır?
- Büyük oyunlarda aramayı sabit bir derinlikte kesmek için değerlendirme fonksiyonları nasıl kullanılır?
- Monte Carlo ağaç araması, derinlik sınırlı minimax'a ne zaman tercih edilir?
Anahtar kavramlar
- oyun ağacı
- minimax değeri
- alfa-beta budaması
- değerlendirme (sezgisel) fonksiyonu
- derinlik sınırlı arama ve ufuk etkisi
- sıfır toplamlı tam bilgi oyunları
- Monte Carlo ağaç araması
- hamle sıralaması
Temel kuramlar
- Minimax karar kuralı
- İki oyunculu sıfır toplamlı bir oyunda, her oyuncu kendi minimum garantili sonucunu maksimize eden hamleyi seçer; bu maksimum/minimum değerlerin oyun ağacında yukarı doğru yayılması, kökteki optimal hamleyi verir.
- Alfa-beta budaması
- Maksimize eden ve minimize eden oyunculara zaten garanti edilmiş en iyi değerleri takip ederek, alfa-beta araması belirli alt ağaçların nihai kararı etkileyemeyeceğini kanıtlar ve bunları atlar, böylece tam minimax değerini döndürürken, en iyi durumda belirli bir sürede yaklaşık olarak iki kat daha derin arama yapılmasına olanak tanır.
- Monte Carlo ağaç araması
- Dallanma faktörleri kapsamlı ileriye dönük arama için çok büyük olduğunda, Monte Carlo ağaç araması, rastgele denemeler (rollouts) ve keşif ile sömürüyü dengeleyen bir seçim kuralı tarafından yönlendirilen asimetrik bir ağaç inşa eder; bu yöntem Go gibi oyunlarda bilgisayarın oynayışını dönüştürmüştür.
Klinik önem
Rakip tabanlı arama, alfa-beta araması kullanan satranç motorlarından Monte Carlo ağaç aramasına dayalı Go programlarına kadar dönüm noktası niteliğinde yapay zeka sistemleri üretmiştir ve aynı teknikler otomatik müzakerelere, güvenlik oyunlarına ve optimize eden taraflar arasındaki bir yarışma olarak modellenen herhangi bir ortama temel oluşturmaktadır.
Tarihçe
Shannon'ın 1950 tarihli makalesi, bilgisayar satrancını bir değerlendirme fonksiyonu ile minimax araması olarak çerçevelemiş ve von Neumann'ın minimax teoremi oyun teorik temeli sağlamıştır. Alfa-beta budaması 1950'ler ve 1960'lar boyunca geliştirilmiş ve Knuth ile Moore (1975) tarafından titizlikle analiz edilmiştir. 2000'li yıllarda resmileştirilen Monte Carlo ağaç araması, oyun oynama gücünde, özellikle Go'da bir sonraki sıçramayı sağlamıştır.
Öne çıkan isimler
- Claude E. Shannon
- John von Neumann
- Arthur Samuel
- Donald E. Knuth
- Ronald W. Moore
İlgili konular
Temel eserler
- shannon1950
- knuth1975
- browne2012
Sıkça sorulan sorular
- Alfa-beta budaması, minimax'ın seçeceği hamleyi değiştirir mi?
- Hayır. Alfa-beta budaması, tam minimax ile tamamen aynı değeri ve hamleyi döndürür; yalnızca sonucu kanıtlanabilir şekilde etkileyemeyecek dalları keşfetmekten kaçınır. Faydası hızdır ve iyi bir hamle sıralaması ile aynı sürede yaklaşık olarak iki kat daha derine arama yapabilir.
- Go gibi oyunlarda neden minimax yerine Monte Carlo ağaç araması kullanılır?
- Go, çok büyük bir dallanma faktörüne sahiptir ve basit, doğru bir değerlendirme fonksiyonundan yoksundur, bu nedenle sabit derinlikli minimax etkisizdir. Monte Carlo ağaç araması bunun yerine birçok rastgele oyun (playout) aracılığıyla hamle kalitesini tahmin eder ve ağacı umut vadeden hatlara doğru seçici olarak büyütür, bu da bu tür oyunlarda çok daha iyi ölçeklenir.