Sökspelet är ett nollsummespel för två personer som utspelar sig på en uppsättning som kallas sökutrymmet. Sökaren kan välja vilken kontinuerlig bana som helst med en maxhastighetsgräns. Det antas alltid att varken sökaren eller gömman är medveten om den andra spelarens rörelser förrän avståndet mellan dem är mindre än (eller lika med) upptäcktsradien och just i det ögonblicket fångas. Som matematiska modeller kan sökspel användas i områden som kurragömma -spel som spelas av barn eller under vissa militära taktiska omständigheter. Sökspel introducerades i det sista kapitlet av Rufus Isaacs klassiska Differential Games [1] och utvecklades senare av Shmuel Gal [2] [3] och Steve Alpern [3] . Spelet "The Princess and the Beast " handlar om ett rörligt mål.
En naturlig sökstrategi för ett fast mål i en graf är att hitta den minsta slutna kurvan L som går genom grafens alla bågar. (L kallas den kinesiska brevbärarvägen ). Sedan går vi runt L med sannolikhet 1/2 för varje riktning. Denna strategi fungerar bra om Euler- grafen är . I allmänhet är den kinesiska brevbärarvägen en optimal strategi om och endast om grafen består av en uppsättning Euler-grafer sammankopplade med en trädliknande struktur [4] . Ett bedrägligt enkelt exempel på en graf som inte kommer från denna familj består av två noder förbundna med tre bågar. Att slumpmässigt korsa den kinesiska brevbäraren (motsvarande att passera tre bågar i slumpmässig ordning) är inte optimalt, och den optimala vägen för att hitta dessa tre bågar är komplicerad [2] .
I det allmänna fallet med ett obegränsat sökområde, som i fallet med onlinealgoritmen , skulle en acceptabel strategi vara att använda en normaliserad förlustfunktion (kallad konkurrenskvoten i litteraturen ).
Minimax- banan för problem av denna typ är alltid en geometrisk sekvens (eller en exponentiell funktion för kontinuerliga problem). Detta resultat ger en enkel metod för att hitta en minimaxbana genom att minimera en enda parameter (generatorn för denna sekvens) istället för att söka igenom hela utrymmet av banor. Detta verktyg används i det linjära sökproblemet , det vill säga problemet med att hitta ett mål på en oändlig linje, som har fått mycket uppmärksamhet nyligen och har analyserats som ett sökspel [5] . Den användes också för att hitta en minimaxbana för att hitta en uppsättning strålar som konvergerar vid en punkt. Optimal sökning på planet utförs med hjälp av exponentiella spiraler [2] [3] [6] .
Sökandet efter konvergerande strålar återupptäcktes senare i den vetenskapliga litteraturen som "kovägsproblemet" [7] .
| Spel teori | |
|---|---|
| Grundläggande koncept | |
| Typer av spel |
|
| Lösningskoncept | |
| Spelexempel | |