Opgelost spel

Van Wikipedia, de gratis encyclopedie
Spring naar navigatie Spring om te zoeken

Een opgelost spel is een spel waarvan de uitkomst (winst, verlies of gelijkspel ) correct kan worden voorspeld vanuit elke positie, ervan uitgaande dat beide spelers perfect spelen. Dit concept wordt meestal toegepast op abstracte strategiespellen , en vooral op spellen met volledige informatie en zonder kanselement; het oplossen van een dergelijk spel kan gebruik maken van combinatorische speltheorie en / of computerondersteuning.

Overzicht [ bewerken ]

Een spel voor twee spelers kan op verschillende niveaus worden opgelost: [1] [2]

Ultra zwak
Bewijs of de eerste speler wint, verliest of remise vanaf de beginpositie, mits perfect spel aan beide kanten. Dit kan een niet-constructief bewijs zijn (mogelijk met een strategie-steel-argument ) dat eigenlijk geen zetten van het perfecte spel hoeft te bepalen.
Zwak
Zorg voor een algoritme dat vanaf het begin van het spel een overwinning voor één speler of een gelijkspel voor een van beide veiligstelt tegen mogelijke zetten van de tegenstander. Dat wil zeggen, produceer ten minste één compleet ideaal spel (alle zetten beginnen en eindigen) met het bewijs dat elke zet optimaal is voor de speler die het doet. Het betekent niet noodzakelijk dat een computerprogramma dat de oplossing gebruikt, optimaal zal spelen tegen een onvolmaakte tegenstander.
Sterk
Zorg voor een algoritme dat vanaf elke positie perfecte zetten kan produceren, zelfs als er al aan één of beide kanten fouten zijn gemaakt.

Ondanks hun naam zijn veel speltheoretici van mening dat ‘ultrazwakke’ bewijzen de diepste, interessantste en meest waardevolle zijn. Voor "ultrazwakke" bewijzen moet een wetenschapper redeneren over de abstracte eigenschappen van het spel, en laten zien hoe deze eigenschappen tot bepaalde resultaten leiden als perfect spel wordt gerealiseerd.

Daarentegen worden ‘sterke’ bewijzen vaak met brute kracht uitgevoerd - met behulp van een computer om grondig in een gameboom te zoeken om erachter te komen wat er zou gebeuren als perfect spel werd gerealiseerd. Het resulterende bewijs geeft een optimale strategie voor elke mogelijke positie op het bord. Deze bewijzen zijn echter niet zo nuttig om de diepere redenen te begrijpen waarom sommige games oplosbaar zijn als gelijkspel, en andere, schijnbaar zeer vergelijkbare games, kunnen worden opgelost als een overwinning.

Gezien de regels van twee-person game met een eindig aantal posities, kan men altijd triviaal bouw van een minimax algoritme dat uitputtend het zou doorkruisen spel boom . Aangezien een dergelijk algoritme voor veel niet-triviale spellen echter een onhaalbare hoeveelheid tijd zou vergen om een ​​zet in een bepaalde positie te genereren, wordt een spel niet als zwak of sterk beschouwd, tenzij het algoritme kan worden uitgevoerd door bestaande hardware in een bepaalde positie. goede tijd. Veel algoritmen vertrouwen op een enorme vooraf gegenereerde database en zijn in feite niets meer.

Als voorbeeld van een sterke oplossing: het spel boter-kaas-en-eieren is oplosbaar als gelijkspel voor beide spelers met perfect spel (een resultaat dat zelfs handmatig kan worden bepaald door schoolkinderen). Games zoals nim laten ook een rigoureuze analyse toe met behulp van combinatorische speltheorie .

Of een game wordt opgelost, is niet per se hetzelfde als of het voor mensen interessant blijft om te spelen. Zelfs een sterk opgelost spel kan nog steeds interessant zijn als de oplossing te complex is om te onthouden; omgekeerd kan een zwak opgelost spel zijn aantrekkingskracht verliezen als de winnende strategie eenvoudig genoeg is om te onthouden (bijv. Maharadja en de Sepoys ). Een ultrazwakke oplossing (bijv. Chomp of Hex op een voldoende groot bord) heeft doorgaans geen invloed op de speelbaarheid.

Bovendien, zelfs als het spel niet wordt opgelost, is het mogelijk dat een algoritme een goede geschatte oplossing oplevert: een artikel in Science uit januari 2015 beweert bijvoorbeeld dat hun heads-up limit Texas hold'em pokerbot Cepheus garandeert dat een mensenleven van spel is niet voldoende om met statistische significantie vast te stellen dat zijn strategie geen exacte oplossing is. [3] [4] [5]

Perfect spel [ bewerken ]

In de speltheorie is perfect spel het gedrag of de strategie van een speler die tot de best mogelijke uitkomst voor die speler leidt, ongeacht de reactie van de tegenstander. Perfect spel voor een spel is bekend wanneer het spel is opgelost. [1] Op basis van de spelregels kan elke mogelijke eindpositie worden geëvalueerd (als winst, verlies of gelijkspel). Door achterwaarts te redeneren, kan men recursief een niet-eindpositie beoordelen als identiek aan de positie die één zet verwijderd is en het best gewaardeerd wordt voor de speler wiens zet het is. Een overgang tussen posities kan dus nooit resulteren in een betere evaluatie van de bewegende speler, en een perfecte zet in een positie zou een overgang zijn tussen posities die gelijkelijk worden geëvalueerd. Een perfecte speler in een gelijkspel krijgt bijvoorbeeld altijd gelijkspel of wint, nooit een verlies. Als er meerdere opties zijn met hetzelfde resultaat, wordt perfect spelen soms beschouwd als de snelste methode die tot een goed resultaat leidt, of de langzaamste methode die tot een slecht resultaat leidt.

Perfect spel kan worden gegeneraliseerd naar niet- perfecte informatiespellen , als de strategie die de hoogst verwachte minimale uitkomst garandeert, ongeacht de strategie van de tegenstander. De perfecte strategie voor een steenpapieren schaar zou bijvoorbeeld zijn om willekeurig elk van de opties te kiezen met een gelijke (1/3) kans. Het nadeel in dit voorbeeld is dat deze strategie nooit niet-optimale strategieën van de tegenstander zal exploiteren, dus de verwachte uitkomst van deze strategie versus welke strategie dan ook zal altijd gelijk zijn aan de minimaal verwachte uitkomst.

Hoewel de optimale strategie van een spel (nog) niet bekend is, kan een spelcomputer toch profiteren van oplossingen van het spel vanuit bepaalde eindspelposities (in de vorm van eindspel-tafelbasissen ), waardoor het na enige tijd perfect kan spelen. punt in het spel. Computerschaakprogramma 's staan ​​erom bekend dit te doen.

Opgeloste spellen [ bewerken ]

Awari (een spel van de familie Mancala )
De variant van Oware die game-ending "grand slams" toestaat, werd sterk opgelost door Henri Bal en John Romein van de Vrije Universiteit in Amsterdam , Nederland (2002). Beide spelers kunnen het spel tot een gelijkspel dwingen.
Eetstokjes
De tweede speler kan altijd een overwinning afdwingen.
Verbind vier
Eerst opgelost door James D. Allen op 1 oktober 1988 en onafhankelijk door Victor Allis op 16 oktober 1988. [6] De eerste speler kan een overwinning afdwingen. Sterk opgelost door de 8-laags database van John Tromp [7] (4 februari 1995). Zwak opgelost voor alle plankformaten waar de breedte + hoogte maximaal 15 is (evenals 8 × 8 eind 2015) [6] (18 februari 2006).
Engelse dammen (dammen)
Deze 8 × 8 variant van tocht werd op 29 april 2007 zwak opgelost door het team van Jonathan Schaeffer . Vanuit de standaard startpositie kunnen beide spelers een gelijkspel met perfect spel garanderen. [8] Dammen is het grootste spel dat tot nu toe is opgelost, met een zoekruimte van 5 × 10 20 . [9] Het aantal betrokken berekeningen was 10 14 , die over een periode van 18 jaar werden uitgevoerd. Het proces omvatte van 200 desktopcomputers op zijn hoogtepunt tot ongeveer 50. [10]
Fanorona
Zwak opgelost door Maarten Schadd. Het spel is een gelijkspel.
Gratis gomoku
Opgelost door Victor Allis (1993). De eerste speler kan een overwinning afdwingen zonder regels te openen.
Geest
Opgelost door Alan Frank met behulp van de Official Scrabble Players Dictionary in 1987. [ nodig citaat ]
Raad eens wie?
Sterk opgelost door Mihai Nica in 2016. [11] De eerste speler heeft 63% kans om te winnen bij optimaal spel door beide partijen.
Hex
  • Een argument dat de strategie steelt (zoals gebruikt door John Nash ) laat zien dat alle vierkante bordformaten niet verloren kunnen gaan door de eerste speler. Gecombineerd met een bewijs van de onmogelijkheid van een gelijkspel, toont dit aan dat het spel ultrazwak is opgelost als een eerste speler wint.
  • Sterk opgelost door meerdere computers voor bordformaten tot 6 × 6.
  • Jing Yang heeft een winnende strategie (zwakke oplossing) gedemonstreerd voor bordformaten 7 × 7, 8 × 8 en 9 × 9.
  • Een winnende strategie voor Hex met ruilen staat bekend om het 7 × 7 bord.
  • Het is onwaarschijnlijk dat Hex sterk wordt opgelost op een N × N- bord, aangezien is aangetoond dat het probleem PSPACE-compleet is .
  • Als Hex wordt gespeeld op een N × ( N +1) bord, kan de speler met de kortere afstand om verbinding te maken altijd winnen door een eenvoudige paarstrategie, zelfs met het nadeel dat hij als tweede speelt.
  • Er is een zwakke oplossing bekend voor alle openingszetten op het 8 × 8 bord. [12]
Hexapawn
3 × 3 variant opgelost als overwinning voor zwart, diverse andere grotere varianten ook opgelost. [13]
Kalah
De meeste varianten zijn opgelost door Geoffrey Irving, Jeroen Donkers en Jos Uiterwijk (2000) behalve Kalah (6/6). De (6/6) variant is opgelost door Anders Carstensen (2011). In de meeste gevallen werd een sterk first-player voordeel bewezen. [14] [15] Mark Rawlings, uit Gaithersburg, MD, heeft de omvang van de eerste winst van een speler in de (6/6) variant (2015) gekwantificeerd. Na het aanmaken van 39 GB aan eindspel-databases, zoekopdrachten van in totaal 106 dagen CPU-tijd en meer dan 55 biljoen nodes, werd bewezen dat, met perfect spel, de eerste speler wint met 2. Merk op dat al deze resultaten verwijzen naar de Empty-pit Capture variant en zijn daarom van zeer beperkt belang voor het standaardspel. Analyse van het spel met standaardregels is nu gepost voor Kalah (6,4), wat een winst met 8 is voor de eerste speler, en Kalah (6,5), wat een winst met 10 is voor de eerste speler. Analyse van Kalah (6,6) met de standaardregels is aan de gang, maar het is bewezen dat het een overwinning met minstens 4 is voor de eerste speler.
L spel
Gemakkelijk oplosbaar. Beide spelers kunnen het spel tot een gelijkspel dwingen.
Schaken verliezen
Zwak opgelost als overwinning voor wit beginnend met 1. e3. [16]
Maharadja en de Sepoys
Dit asymmetrische spel is een overwinning voor de sepoys-speler met correct spel.
Nim
Sterk opgelost.
Morris van negen mannen
Opgelost door Ralph Gasser (1993). Beide spelers kunnen het spel tot een gelijkspel dwingen. [17]
Orde en chaos
Order (eerste speler) wint. [18]
Ohvalhu
Zwak opgelost door mensen, maar bewezen door computers. (Dakon is echter niet identiek aan Ohvalhu, het spel dat daadwerkelijk door de Voogt was waargenomen)
Pangki
Sterk opgelost door Jason Doucette (2001). [19] Het spel is gelijkspel. Er zijn slechts twee unieke eerste zetten als u gespiegelde posities aflegt. De ene forceert de remise en de andere geeft de tegenstander een gedwongen overwinning in 15.
Pentago
Sterk opgelost. [20] De eerste speler wint.
Pentomino's
Zwak opgelost door HK Orman. [21] Het is een overwinning voor de eerste speler.
Poddavki ("Russian Give-away Checkers")
Opgelost door Osipov en Morozev in 2011. Een witte overwinning.
Quarto
Opgelost door Luc Goossens (1998). Twee perfecte spelers zullen altijd tekenen.
Qubic
Zwak opgelost door Oren Patashnik (1980) en Victor Allis . De eerste speler wint.
Renju- achtig spel zonder betrokken openingsregels
Opgelost door János Wagner en István Virág (2001). Een overwinning voor de eerste speler.
Sim
Zwak opgelost: win voor de tweede speler.
Teeko
Opgelost door Guy Steele (1998). Afhankelijk van de variant wint de eerste speler of een gelijkspel. [22]
Morris voor drie mannen
In feite oplosbaar. Beide spelers kunnen het spel tot een gelijkspel dwingen.
Drie Musketiers
Sterk opgelost door Johannes Laire in 2009, en zwak opgelost door Ali Elabridi in 2017. [23] Het is een overwinning voor de blauwe stukken (de mannen van kardinaal Richelieu, of de vijand). [24]
Boter kaas en eieren
Triviaal sterk oplosbaar vanwege de kleine wildboom. [25] De game is remise als er geen fouten worden gemaakt, zonder dat er een fout mogelijk is bij de openingszet.
Tijgers en geiten
Zwak opgelost door Yew Jin Lim (2007). Het spel is een gelijkspel. [26]
Wythoff's spel
Sterk opgelost.

Gedeeltelijk opgeloste spellen [ bewerken ]

Schaak
Het volledig oplossen van schaken blijft ongrijpbaar, en er wordt gespeculeerd dat de complexiteit van het spel kan beletten dat het ooit wordt opgelost. Door middel van retrograde computer analyse , endgame tablebases hebben (sterke oplossingen) is gevonden voor alle drie- tot zeven-stuk eindspelen , het tellen van de twee koningen als stukjes.
Enkele varianten van schaken op een kleiner bord met een kleiner aantal stukken zijn opgelost. Enkele andere populaire varianten zijn ook opgelost; een zwakke oplossing voor Maharajah en de Sepoys is bijvoorbeeld een gemakkelijk te onthouden reeks zetten die de overwinning voor de "sepoys" -speler garandeert.
Gaan
Het 5 × 5-bord was zwak opgelost voor alle openingszetten in 2002. [27] Het 7 × 7-bord werd zwak opgelost in 2015. [28] Mensen spelen meestal op een 19 × 19-bord dat meer dan 145 orden van grootte complexer is dan 7 × 7. [29]
Internationale tocht
Alle eindspelposities met twee tot en met zeven stukken werden opgelost, evenals posities met 4 × 4 en 5 × 3 stukken waarbij elke partij één koning of minder had, posities met vijf mannen versus vier mannen, posities met vijf mannen versus drie mannen en één koning, en posities met vier mannen en één koning tegen vier mannen. De eindspelposities werden in 2007 opgelost door Ed Gilbert uit de Verenigde Staten. Computeranalyse toonde aan dat het hoogstwaarschijnlijk in een gelijkspel zou eindigen als beide spelers perfect speelden. [30] [ betere bron nodig ]
m, n, k-game
Het is triviaal om te laten zien dat de tweede speler nooit kan winnen; zie strategie-stelen argument . Bijna alle gevallen zijn zwak opgelost voor k ≤ 4. Sommige resultaten zijn bekend voor k = 5. De partijen zijn geloot voor k ≥ 8.
Reversi (Othello)
Zwak opgelost op een 4 × 4 en 6 × 6 bord toen een tweede speler in juli 1993 won door Joel Feinstein. [31] Op een 8 × 8-bord (het standaardbord) is het wiskundig onopgelost, hoewel computeranalyse een waarschijnlijke gelijkspel laat zien. Er bestaan ​​geen andere sterk veronderstelde schattingen dan verhoogde kansen voor de startspeler (zwart) op 10 × 10 en grotere borden.

Zie ook [ bewerken ]

  • Computer schaken
  • Computer gaan
  • Computer Othello
  • Complexiteit van het spel
  • Gods algoritme
  • Stelling van Zermelo (speltheorie)

Referenties [ bewerken ]

  1. "Proefschrift: zoeken naar oplossingen in games en kunstmatige intelligentie" (pdf) . Afdeling Computerwetenschappen . Universiteit Limburg . Ontvangen 2012-07-14 .
  2. Burch, N .; Johanson, M .; Tammelin, O. (januari 2015). "Heads-up limit hold'em poker is opgelost" (pdf) . Wetenschap . 347 (6218): 145-9. CiteSeerX 10.1.1.697.72 . doi : 10.1126 / science.1259433 . PMID 25574016 . S2CID 3796371 .    
  3. "Speltheoretici Crack Poker" . Natuur . Natuur. doi : 10.1038 / natuur.2015.16683 . S2CID 155710390 . Ontvangen 2015/01/13 . 
  4. "Computer verovert Texas Hold 'Em, zeggen onderzoekers" . Wall Street Journal .
  5. tromp.github.io .
  6. archive.ics.uci.edu .
  7. "Dammen is opgelost" . Wetenschap . 317 (5844): 1518-1522. doi : 10.1126 / science.1144079 . PMID 17641166 . S2CID 10274228 . Ontvangen 2007-07-20 .  
  8. Ontvangen 2007-07-19 .
  9. "Dammen 'opgelost' na jaren van rekenwerk" . NewScientist.com nieuwsservice . Ontvangen 2020/12/06 .
  10. IJCAI-09505-510 (2009) Ontvangen 29 juni 2010.
  11. "Hexapawn" . www.chessvariants.com .
  12. "Schaken verliezen: 1. e3 wint voor wit" (pdf) . Ontvangen 17 januari 2017 .
  13. Online: pdf .
  14. "Het spel van de drie musketiers zwak oplossen met behulp van kunstmatige intelligentie en speltheorie" (pdf) .
  15. Over vooruit snoeien in Game-Tree Search . Ph.D. Scriptie, National University of Singapore , 2007.
  16. blog.sina.com.cn . (wat zegt dat de 7x7-oplossing slechts zwak is opgelost en nog in onderzoek is, 1. de juiste komi is 9 (4,5 steen); 2. er zijn meerdere optimale bomen - de eerste 3 zetten zijn uniek - maar binnen de eerste 7 zetten zijn er zijn 5 optimale bomen; 3. Er zijn veel manieren om te spelen die het resultaat niet beïnvloeden)
  17. Gearchiveerd van het origineel op 01-11-2009.

Verder lezen [ bewerken ]

  • Allis, de wereldkampioen verslaan? De allernieuwste in het spelen van computerspellen. in nieuwe benaderingen van onderzoek naar bordspellen.

Externe links [ bewerken ]

  • Computationele complexiteit van games en puzzels door David Eppstein.
  • GamesCrafters lost tweepersoonsspellen op met perfecte informatie en zonder kans