Vinnande strategi
Wikipedia
Begrepp inom spelteori. Nedan beskrivs detta plus några besläktade begrepp.
En strategi är en beskrivning för hur man ska spela ett visst spel. I varje drag som man står inför ska man alltså kunna konsultera denna beskrivning och få reda på vilket drag man ska göra. Beskrivningen måste täcka alla möjliga ställningar som kan uppkomma, och den måste vara entydig så att den bara ger en möjlighet i varje ställning och aldrig flera alternativ. En sådan här beskrivning är en algoritm, som kan utföras mekaniskt av till exempel ett datorprogram.
En vinnande strategi är en strategi som (från utgångsställningen) garanterat ger vinst för den spelare som följer den, oavsett vilka svarsdrag den andra spelaren gör. Naturligtvis kan det i ett spel uppstå en ställning efter ett antal drag som innebär att den ena spelaren från och med denna ställning har en vinnande strategi, men om detta inte samtidigt gäller från utgångsställningen säger man inte att spelet som helhet har en vinnande strategi. En optimal strategi är en strategi som ger bästa möjliga resultat (oftast oavgjort) av alla strategier för ett visst spel.
Ett finit tvåpersonsspel (ändligt tvåpersonsspel) är ett spel för två deltagare som efter ett ändligt antal drag utifrån en utgångsställning utser exakt en vinnare (får inte bli oavgjort). Ett sådant spel kan representeras med ett träd där varje nod i trädet representerar en ställning (till exempel pjäsernas placering om det är ett brädspel) inklusive information om vem som är vid draget. En av noderna ("roten") representerar utgångsställningen. En gren mellan två noder innebär att det är möjligt att ta sig från den ena ställningen till den andra med ett giltigt drag. De ändnoder som sitter ytterst på varje "gren" (bortsett från utgångsställningens nod) är samtliga slutställningar och kan klassificeras i två grupper efter vilken av spelarna som ges vinst i denna ställning. Man förutsätter också att dessa finita tvåpersonsspel har fullständig information, dvs båda spelarna vet exakt vilka drag som är möjliga i varje tänkbar ställning. Varje finit tvåpersonsspel har en vinnande strategi. Att spela ett sådant spel är att tillsammans "vandra" i trädet från nod till nod samtidigt som båda försöker få vandringen att sluta i "rätt" typ av ändnod. En vinnande strategi för en spelare är en algoritm som alltid leder till att vandringen slutar i en slutnod som är en vinstnod för denna spelare.
Schack uppfyller definitionen i föregående stycke så när som på att det finns även oavgjorda ställningar i schack. Detta innebär att det finns ett träd för schack som innehåller ändligt antal noder: En nod för varje tänkbar ställning som kan uppkomma, varav en nod är för utgångsställningen samt en nod för varje tänkbar slutställning. Grenarna mellan noderna representerar giltiga schackdrag. Antalet noder är ändligt eftersom man bara kan arrangera schackpjäser på ett schackbräde på ett ändligt antal sätt (dessutom kan ju inte ens alla dessa kombinationer uppkomma i ett parti). Antalet möjliga schackpartier som går att spela är därför också ändligt. Ändnoderna är av tre slag: vinstställning för svart, vinstställning för vit och oavgjort. Detta betyder att i schack finns det en optimal strategi för någon av spelarna (antagligen vit) som garanterat ger minst oavgjort (eller annorlunda uttryckt: strategin garanterar att man inte förlorar).
Samma sak gäller för flera andra spel som kan sluta oavgjort, till exempel Othello, Fyra i rad och Dam. För go gäller att om man spelar med heltals-komi (eller ingen komi), så kan det sluta oavgjort, och alltså finns det då en optimal strategi för någon av spelarna som ger minst oavgjort på samma sätt som för de andra spelen ovan. Om man däremot spelar med icke-heltals-komi (till exempel 6,5 som är vanligt i tävlingar) så finns det inga noder för oavgjort, och alltså finns det en vinnande strategi för någon av spelarna. (Eftersom man inte kan/får erbjuda den andre oavgjort kommer alltid någon att vinna.)
Att det finns en vinnande strategi i ett spel innebär naturligtvis inte att denna måste vara känd. I så fall skulle spelet helt tappa sin poäng. I spelet tic-tac-toe (tre i rad på ett 3*3-rutnät) så finns det en enkel optimal strategi som garanterar minst oavgjort för den som börjar. Det tar inte lång tid för ett barn att hitta denna, och därför är spelet egentligen ointressant att spela (utom för små barn möjligtvis).
Bevis för att varje finit tvåpersonsspel har en vinnande strategi:
