Spelträd

För spelträd som det används i spelteori (inte kombinatorisk spelteori), se Omfattande spel .

Inom ramen för kombinatorisk spelteori , som vanligtvis studerar sekventiella spel med perfekt information , är ett spelträd en graf som representerar alla möjliga speltillstånd inom ett sådant spel. Sådana spel inkluderar välkända spel som schack , dam , Go och tic-tac-toe . Detta kan användas för att mäta komplexiteten i ett spel , eftersom det representerar alla möjliga sätt som ett spel kan slå ut på. På grund av de stora spelträden i komplexa spel som schack, kommer algoritmer som är designade för att spela denna klass av spel att använda partiella spelträd, vilket gör beräkning möjlig på moderna datorer. Det finns olika metoder för att lösa spelträd. Om ett komplett spelträd kan genereras, kan en deterministisk algoritm , såsom bakåtinduktion eller retrograd analys användas. Randomiserade algoritmer och minimaxalgoritmer som MCTS kan användas i de fall där ett komplett spelträd inte är genomförbart.

Förstå spelträdet

För att bättre förstå spelträdet kan det ses som en teknik för att analysera motståndsspel, som avgör vilka åtgärder spelaren vidtar för att vinna spelet. I spelteorin är ett spelträd en riktad graf vars noder är positioner i ett spel (t.ex. arrangemanget av pjäserna i ett brädspel) och vars kanter är drag (t.ex. för att flytta pjäser från en position på en bräda till en annan ).

Det kompletta spelträdet för ett spel är spelträdet som börjar vid den ursprungliga positionen och innehåller alla möjliga drag från varje position; det kompletta trädet är samma träd som det som erhålls från spelrepresentationen i extensiv form . För att vara mer specifik är det kompletta spelet en norm för spelet i spelteorin. Vilket tydligt kan uttrycka många viktiga aspekter. Till exempel sekvensen av åtgärder som intressenter kan vidta, deras val vid varje beslutspunkt, information om åtgärder som vidtagits av andra intressenter när varje intressent fattar ett beslut och fördelarna med alla möjliga spelresultat.

De två första lagren av spelträdet för tic-tac-toe.

Diagrammet visar de två första nivåerna, eller skikten , i spelträdet för tic-tac-toe . Rotationerna och reflektionerna av positioner är likvärdiga, så den första spelaren har tre val av drag: i mitten, vid kanten eller i hörnet. Den andra spelaren har två val för svaret om den första spelaren spelade i mitten, annars fem val. Och så vidare.

Antalet lövnoder i hela spelträdet är antalet möjliga olika sätt som spelet kan spelas på. Till exempel har spelträdet för tic-tac-toe 255 168 lövnoder.

Spelträd är viktiga för artificiell intelligens eftersom ett sätt att välja det bästa draget i ett spel är att söka i spelträdet med någon av de många trädsökningsalgoritmerna , kombinerat med minimax -liknande regler för att beskära trädet . Spelträdet för tic-tac-toe är lätt sökbart, men de kompletta spelträden för större spel som schack är alldeles för stora för att söka. Istället söker ett schackspelande program i ett partiellt spelträd : vanligtvis så många lag från den aktuella positionen som det kan söka inom den tillgängliga tiden. Förutom fallet med "patologiska" viltträd (som verkar vara ganska sällsynta i praktiken), ökar i allmänhet chansen att välja det bästa draget genom att öka sökdjupet (dvs. antalet sökta skikt).

Två-personers spel kan också representeras som och-eller träd . För att den första spelaren ska vinna ett spel måste det finnas ett vinnande drag för alla drag av den andra spelaren. Detta representeras i och-eller-trädet genom att använda disjunktion för att representera den första spelarens alternativa drag och använda konjunktion för att representera alla den andra spelarens drag.

Lösa spelträd

Deterministisk algoritm version

Med ett komplett spelträd är det möjligt att "lösa" spelet – det vill säga hitta en sekvens av drag som antingen den första eller andra spelaren kan följa som garanterar bästa möjliga resultat för den spelaren (vanligtvis en vinst eller en slips). Den deterministiska algoritmen (som allmänt kallas bakåtinduktion eller retrograd analys ) kan beskrivas rekursivt enligt följande.

  1. Färglägg det sista lagret av spelträdet så att alla vinster för spelare 1 färgas åt ena hållet (blått i diagrammet), alla vinster för spelare 2 färgas på ett annat sätt (röd i diagrammet) och alla oavgjorda färger på ett tredje sätt (Grå i diagrammet).
  2. Titta på nästa lager. Om det finns en nod som är färgad motsatt den nuvarande spelaren, färglägg denna nod också för den spelaren. Om alla omedelbart lägre noder är färgade för samma spelare, färga även denna nod för samma spelare. Annars, färga denna nod en slips.
  3. Upprepa för varje lager, rör dig uppåt tills alla noder är färgade. Färgen på rotnoden kommer att avgöra spelets karaktär.

Diagrammet visar ett spelträd för ett godtyckligt spel, färgat med ovanstående algoritm.

Det är vanligtvis möjligt att lösa ett spel (i denna tekniska betydelse av "lösa") med endast en delmängd av spelträdet, eftersom ett drag i många spel inte behöver analyseras om det finns ett annat drag som är bättre för samma spelare ( till exempel kan alfa-beta-beskärning användas i många deterministiska spel).

Alla underträd som kan användas för att lösa spelet kallas beslutsträd , och storlekarna på beslutsträd av olika former används som mått på spelets komplexitet .

Randomiserade algoritmer version

Randomiserade algoritmer kan användas för att lösa spelträd. Det finns två huvudsakliga fördelar med denna typ av implementering: snabbhet och praktisk. Medan en deterministisk version av att lösa spelträd kan göras i Ο ( n ) , har följande randomiserade algoritm en förväntad körtid på θ ( n 0,792 ) om varje nod i spelträdet har grad 2. Dessutom är det praktiskt eftersom randomiserat Algoritmer är kapabla att "förhindra en fiende", vilket betyder att en motståndare inte kan slå systemet av spelträd genom att känna till algoritmen som används för att lösa spelträdet eftersom ordningen för lösningen är slumpmässig.

Följande är en implementering av en randomiserad spelträdslösningsalgoritm:

   
    
     
         
    
              
           
             
           
              def  gt_eval_rand  (  u  )  ->  bool  :  """Returnerar True om denna nod utvärderas till en vinst, annars False"""  om  u  .  blad  :  returnera  u  .  win  else  :  random_children  =  (  gt_eval_rand  (  barn  )  för  barn  i  random_order  (  u  .  barn  ))  om  u  .  op  ==  "ELLER"  :  returnera  någon  (  random_children  )  om  u  .  op  ==  "OCH"  :  returnera  alla  (  random_children  )

Algoritmen använder sig av idén om " kortslutning ": om rotnoden anses vara en " ELLER "-operator, så klassificeras roten som Sann när en Sann har hittats ; omvänt, om rotnoden anses vara en " OCH "-operator så klassificeras roten som False när en False hittats .

Se även

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Game_tree&oldid=1081174077 "