Sök efter bevisnummer

Bevisnummersökning (kort: PN-sökning) är en sökalgoritm för spelträd som uppfanns av Victor Allis , med tillämpningar mestadels i slutspelslösare, men även för delmål under spel.

Med hjälp av ett binärt mål (t.ex. den första spelaren vinner spelet), kan spelträd för två-personers spel med perfekt information mappas till ett och–eller träd . Maximiserande noder blir ELLER-noder, minimeringsnoder mappas till OCH-noder. För alla noder lagras bevis- och avvisningsnummer och uppdateras under sökningen.

Till varje nod i det delvis expanderade spelträdet är bevisnumret och disproofnumret associerade. Ett bevisnummer representerar det minsta antalet lövnoder som måste bevisas för att kunna bevisa noden. Analogt representerar ett disproofnummer det minsta antal blad som måste motbevisas för att motbevisa noden. Eftersom målet med trädet är att bevisa en påtvingad vinst, anses vinnande noder som bevisade. Därför har de bevisnummer 0 och disproofnummer ∞. Förlorade eller ritade noder betraktas som motbevisade. De har bevisnummer ∞ och motbevisnummer 0. Okända lövnoder har ett bevis- och motbevisnummer på enhet. Bevisnumret för en intern OCH-nod är lika med summan av dess barns bevisnummer, eftersom för att bevisa en OCH-nod måste alla barn bevisas. Disproof-numret för en AND-nod är lika med minimivärdet av dess barns disproof-nummer. Disproof-talet för en intern ELLER-nod är lika med summan av dess barns disproof-tal, eftersom för att motbevisa en ELLER-nod måste alla barn motbevisas. Dess bevisnummer är lika med minimum av dess barns bevisnummer.

Proceduren för att välja den mest beprövade noden att expandera är följande. Vi börjar vid roten. Sedan, vid varje ELLER-nod väljs barnet med det lägsta bevisnumret som efterträdare, och vid varje OCH-nod väljs barnet med det lägsta avvisningsnumret som efterträdare. Slutligen, när en lövnod nås, expanderas den och dess barn utvärderas.

Bevis- och motbevissiffrorna representerar lägre gränser för antalet noder som ska utvärderas för att bevisa (eller motbevisa) vissa noder. Genom att alltid välja den mest bevisande (motbevisande) noden att expandera, genereras en effektiv sökning.

Vissa varianter av bevisnummersökning som dfPN, PN ² , PDS-PN har utvecklats för att möta de ganska stora minneskraven för algoritmen.

Vidare läsning

A. Kishimoto, MHM Winands, M. Müller och JT. Saito (2012) Spelträdsökning med hjälp av bevisnummer: De första tjugo åren , ICGA, 35(3):131–156, pdf