Minimax algoritması

Minimaks algoritma (aynı zamanda olarak anılacaktır minmaks algoritması ) için geçerli olan bir algoritmadır oyun teorisi iki oyuncu için sıfır toplamlı (yani en kötü durumda demek) (ve tam bilgi) maksimum kaybını minimize oyunları. Geniş bir oyun ailesi için, von Neumann'ın minimax teoremi , pratikte onu bulmak çoğu zaman kolay olmasa bile, böyle bir algoritmanın varlığını garanti eder. Hex oyunu böyle bir algoritmanın varlığının kurulduğu bir örnektir ve bu strateji bilinmeden ilk oyuncunun her zaman kazanabileceğini gösterir.

Bilgisayarın sınırlı sayıda hamle için tüm olasılıkları gözden geçirmesini ve onlara oyuncu ve rakibi için faydalarını dikkate alan bir değer atamasını sağlar. Bu durumda en iyi seçim, rakibin tam tersine onları maksimize etmek istediğini varsayarak oyuncunun kayıplarını en aza indiren seçimdir (oyun sıfır toplamlıdır).

Oyun ağacında ziyaret edilen düğüm sayısını sınırlayarak en iyi hamleyi aramayı optimize etmek için MinMax tabanlı farklı algoritmalar vardır oyun ağacı, en bilineni alfa-beta budamasıdır . Uygulamada, ağaç genellikle tam olarak keşfedilemeyecek kadar büyüktür ( satranç veya go oyununda olduğu gibi ). Ağacın sadece bir kısmı daha sonra keşfedilir.

Çok büyük ağaçlar söz konusu olduğunda, bir AI (uzman sistemi, örneklerden öğrenerek değerlendirme, vb.) belirli dalları budamak için kullanılabilirliklerine ilişkin bir tahmine dayalı olarak kullanılabilir. Bu, örneğin go bağlamında kullanılan şeydir.

Prensip

Minimax algoritması, aşağıdaki gibi özyinelemeli olarak hesaplanan bir değeri ("oyun değeri" olarak adlandırılır) köke getirmek için oyun ağacını ziyaret eder:

$minimax ( p ) = f ( p )$ eğer $p$ ağacın bir yaprağıysa, burada $f$ oyunun konumunun bir değerlendirme fonksiyonudur;
$minimaks ( p ) = maks (minimaks ( O 1 ),\dots, minimaks ( O n ))$ eğer $p$ , çocukları $O 1 ,\dots, O n$ ;
$minimaks ( p ) = min (minimaks ( O 1 ),\dots, minimaks ( O n ))$ eğer $p$ , çocukları $O 1 ,\dots, O n$ olan bir Karşıt düğüm ise .

Misal

Yukarıdaki şemada, gri düğümler oyuncu düğümlerini ve mavi düğümler karşıt düğümleri temsil eder. A düğümünün değerini belirlemek için B düğümlerinin maksimum değerini seçiyoruz (A bir oyuncu düğümüdür). Bu nedenle, her biri çocuklarında depolanan minimum değeri alan B düğümlerinin değerlerini belirlemek gerekir (B düğümleri karşıttır). C düğümleri yapraklardır, dolayısıyla değerleri değerlendirme fonksiyonu tarafından hesaplanabilir.

Dolayısıyla A düğümü 5 değerini alır. Oyuncu bu nedenle hamleyi B2'ye getiren hamleyi oynamalıdır. Ağacı gözlemleyerek, algoritmanın rakibin en iyi performansı göstereceğini düşündüğünü anlıyoruz: minimumu alıyor. Bu yüklem olmadan, düğüm C seçsin 1 büyük kazanç ve B1 yol açacak seçilen sonraki hamlesini sunmaktadır. Ama sonra rakibin sadece 3 kazanç sağlayan C3 oynaması riskini alıyoruz.

Pratikte, P pozisyonunun teorik değeri genellikle hesaplanamaz. Sonuç olarak, değerleme işlevi terminal dışı pozisyonlara uygulanacaktır. Değerlendirme fonksiyonu kökten ne kadar uzağa uygulanırsa, hesaplama sonucunun o kadar iyi olduğu kabul edilecektir. Başka bir deyişle, daha fazla ardışık vuruş inceleyerek, teorik değere daha iyi bir yaklaşım elde ettiğimizi ve dolayısıyla daha iyi bir hareket seçimi elde ettiğimizi varsayıyoruz.

Negamax sadeleştirme

$f ( p )$ tarafından alınan değerler kümesi 0'a göre simetrik ise, $g ( p )$ fonksiyonu şu şekilde tanımlanabilir:

$g ( p ) = f ( p )$ bir oyuncu düğümündeysek
$g ( p ) = - f ( p )$ eğer karşıt bir düğümdeysek

Böylece negamax'ı bu yeni fonksiyondan tanımlıyoruz:

$negamax ( p ) = g ( p )$ eğer P terminal ise
$negamax ( p ) = maks (-NegaMax ( p i ))$ aksi halde

Minmax algoritmasıyla aynı örnekten elde edilen ağaç:

sözde kod

Sınırlı derinlikli minimax algoritmasının sözde kodu aşağıda gösterilmiştir:

function minimax(node, depth, maximizingPlayer) is if depth = 0 or node is a terminal node then return the heuristic value of node if maximizingPlayer then value := −∞ for each child of node do value := max(value, minimax(child, depth − 1, FALSE)) return value else (* minimizing player *) value := +∞ for each child of node do value := min(value, minimax(child, depth − 1, TRUE)) return value (* Initial call *) minimax(origin, depth, TRUE)

Uygulamalar

Minimax ve istatistiksel seçim teorisi

Seçim istatistiksel Teoride, biz bir tahmincisi var $Í$ amaçları bir bulmak için parametre $İçeride ISTV melerin RWMAIWi'nin \in İçeride ISTV melerin RWMAIWi'nin$ . Bu bağlamda, eğer $θ$ 'minimax':

{\ displaystyle \ sup _ {\ teta} R (\ teta, {\ tilde {\ delta}}) = \ inf _ {\ delta} \ sup _ {\ teta} R (\ teta, \ delta).}

Alfa-beta budama

Bu algoritma, alfa-beta budama olarak bilinen tekniğin uygulanmasıyla optimize edilebilir . Alfa beta algoritması, kullanılmayacak durumları ortadan kaldırarak minimax arama rutinini hızlandırır. Bu yöntem, ağaçtaki diğer tüm seviyelerin maksimize edileceği ve diğer tüm seviyelerin minimize edileceği gerçeğini kullanır.

Ekler

Notlar

Jean-Marc Alliot ve Thomas Schiex , “Oyunların programlanması” , Yapay Zeka ve Teorik Hesaplama , Cepadues,1994( ISBN 2-85428-324-4 )
Ancak oyuncular taş-kağıt-makas oyununda olduğu gibi rakibinin oynadığı hamleleri bilmiyorlarsa , bu algoritma sadece şans kullanımını gerektiren stratejilere yol açar; bkz teoremi makalesine fazla ayrıntı için

bibliyografya

A. Aho , J. Hopcroft, J. Ullman , Veri yapıları ve algoritmalar , Paris, InterEditions,1987, 450 s. ( ISBN 978-2-7296-0194-2 , ihbar BNF n o FRBNF34973701 ) , "Algoritmik kavramları ve stratejileri"

İlgili Makaleler

Dış bağlantı

(tr) google yapay zeka mücadelesinin bir parçası olarak tron oyunu için minimax algoritmasının açıklaması