Wat is de winnende strategie voor de eerste speler in Connect Four-spellen?

Beste antwoord

De eigenlijke “strategie” is eigenlijk vrij complex en vereist een uitgebreide zoektocht naar te behandelen punten met tactieken, dus het is niet praktisch om met de hand te gebruiken.

Aan de andere kant zijn de strategische inzichten en enkele regels voor algemene doeleinden gemakkelijk te gebruiken voor mensen, en zullen je waarschijnlijk een relatief goede speler.

Achtergrond

Laten we beginnen met snel connect-4 te bekijken. Het spel wordt gespeeld op een 6 × 7 bord; we kunnen elke rij voorzien van een nummer en elke kolom met een letter:

Elke speler kiest om de beurt een kolom; hun steen wordt in de onderste open cel in de kolom geplaatst. We kunnen een spel schrijven met alleen de kolommen; Als beide spelers bijvoorbeeld de middelste kolom spelen, kunnen we dd schrijven. Dit zou leiden tot het volgende bord:

(Volgens afspraak is speler 1 blauw en speler 2 rood.)

Een spel kan gewonnen worden door vier stukken van je kleur horizontaal, verticaal of diagonaal met elkaar te verbinden:

Een laatste bruikbare gedachte is een -dreiging , die slechts drie stukken op een rij is met het vierde vierkant open (maar niet noodzakelijkerwijs toegankelijk). Hier heeft blauw een diagonale bedreiging:

Strategie

Het spel is opgelost: de eerste speler (blauw) kan altijd een overwinning afdwingen. De kernideeën achter de winnende strategie zijn vrij eenvoudig: zugzwang beheersen en oneven / even besturen rijen.

Zugzwang

“Zugzwang” betekent verlies omdat je moeten een zet doen. Een eenvoudige illustratie zou zijn dat twee bedreigingen op elkaar zijn geplaatst. Hier is een voorbeeld van blauw dat een overwinning afdwingt op kolom c met rood om te verplaatsen:

Echter, dubbele bedreigingen zoals deze zijn redelijk gemakkelijk te herkennen van tevoren en tegen te gaan. In de praktijk is een veel nuttiger vorm van Zugzwang gewoon wachten tot het hele bord gevuld is en er nog maar één mogelijke zet over is. Beschouw het eenvoudige voorbeeld waarin rood aan de linkerkant wint, waarbij de daadwerkelijke kracht pas plaatsvindt na een aantal zetten:

Even / oneven bedreigingen

Wie een bedreiging heeft die onverbiddelijk zal worden opgevuld, zal uiteindelijk winnen. Zoals we in het vorige voorbeeld zagen, kan rood winnen met een bedreiging in een even rij. Blauw heeft daarentegen een vreemde dreiging nodig om te winnen: dit is waar de asymmetrie in het spel komt tevoorschijn.

Een vreemde dreiging sluit af een kolom en draait in wezen om wie welke rij kan krijgen bij het opvullen van de hele boa rd. Dit betekent in het bijzonder dat een geldige oneven dreiging “sterker” is dan een geldige even dreiging: als blauw een vreemde dreiging heeft in de ene kolom en rood een even dreiging in een andere, zal blauw nog steeds winnen. Hier is een voorbeeld (blauw om af te spelen):

Vanuit deze positie kunnen we herhaaldelijk vullen totdat we bij een positie waar rood c moet spelen omdat g (met een oneven aantal stukken erin) zou resulteren in het winnen van blauw. de c kolom wordt gevuld totdat rood gedwongen wordt te verliezen:

De vreemde dreiging werkt omdat het een enkele kolom afschermt om een ​​ oneven aantal posities te hebben – waardoor het bord effectief wordt verdraaid van een even aantal vierkanten (42) naar een oneven getal, wat de dynamiek van het spel omdraait. Dit betekent ook dat als zowel rood als blauw onafhankelijke oneven bedreigingen hebben, ze het volgende annuleren: met twee oneven kolommen brengen het totaal terug naar even.

Meer in het algemeen geeft het oneven / even onderscheid ons een idee van controle : rood bestuurt normaal gesproken het spel, maar blauw kan controle krijgen door een vreemde dreiging te creëren. In de praktijk betekent controle dat je alle even vierkanten kunt spelen of, als optie, een oneven vierkant kunt spelen, maar je tegenstander in ruil daarvoor een even vierkant laat spelen.

Tactics

Door het oneven / even onderscheid kunnen we “strategisch” spelen – in ieder geval een heleboel zetten vooruit. Om daadwerkelijk consequent te winnen, moeten we onze kennis over langetermijnstrategie combineren met gedegen tactische kortetermijnbewegingen. We moeten dit soort kleine valstrikken in gedachten houden:

Regels

De daadwerkelijke winnende strategie voor het spel komt neer op een reeks van negen regels die gebaseerd zijn op de eerder behandelde strategische principes en tactieken.De regels zijn ontwikkeld door Victor Allis in 1988 — ik denk dat hij de eerste was die het spel oploste.

De regels kunnen “t altijd vind de optimale oplossing: soms moest je echt door de mogelijkheden zoeken, grotendeels om tactische problemen op te lossen.

Dit zijn wat volgens mij de belangrijkste regels zijn, met de namen die Allis ze gaf . Er zijn nog een paar regels, maar deze zijn voor speciale gevallen of alleen voor combinaties van eerdere regels; je kunt over alle regels lezen in het eigenlijke proefschrift: Een op kennis gebaseerde benadering van Connect Four .

• baseinverse : je kunt altijd een van de twee beschikbare velden claimen als je tegenstander de andere claimt, dus je kunt altijd een vier-op-een-rij blokkeren die zo twee velden nodig heeft. Rood kan bijvoorbeeld altijd een van de groene vierkantjes nadat blauw de o speelt ther:

• verticaal : je kunt altijd een verticaal vier-op-een-rij blokkeren door een van de twee vierkanten direct boven elkaar te spelen. Rood kan altijd het verticale vier-op-een-rij op d blokkeren door een van de gemarkeerde vierkanten te spelen:

• claimeven : degene die controle heeft over het spel (dwz rood tenzij blauw een vreemde dreiging heeft ) kan een vierkant in een even rij spelen (zolang dat vierkant niet “onmiddellijk speelbaar is). Deze regel belichaamt de basisstrategie voor even / even.
• aftereven : als je controle hebt en een dreiging in een even rij hebt, kun je die rij spelen via claimeven. Dit betekent dat alle dreigingen in dezelfde kolom erboven worden geblokkeerd. Bijvoorbeeld hier blauw kan b3 niet afspelen omdat rood een bedreiging vormt op b2:

• lowinverse : als er twee kolommen zijn met een oneven aantal open vierkanten, het resultaat is even. Als er twee oneven kwadraten zijn In dergelijke kolommen die niet direct speelbaar zijn, kan degene die het spel bestuurt er minstens één spelen. Dit kan ook gelden voor vierkanten die verre van speelbaar zijn en niet naast elkaar. In deze twee eenvoudige voorbeelden kan rood ten minste een van de twee gemarkeerde vierkanten krijgen:

Winnen

Het spel is eigenlijk opgelost door een combinatie van deze regels en wat uitgebreid zoeken – de regels op zich zijn helaas niet voldoende.

Veel van de regels zijn afhankelijk van controle over het spel. Omdat rood aanvankelijk de controle heeft, kan blauw veel van de regels pas gebruiken als ze erin slagen een vreemde dreiging te vestigen. Blauw kan een vreemde dreiging vestigen door enkele van de regels te gebruiken die niet afhankelijk zijn van controle of gewoon tactisch denken, zoals het combineren van groepen van twee stukken om een ​​vreemde dreiging in de toekomst te garanderen.

Het blijkt de eerste De speler kan dit tegen optimaal spel doen zolang de eerste zet d1 is. Dit betekent dat de eerste speler altijd kan winnen. De zoektocht die dit feitelijk heeft vastgesteld, wordt ook gedetailleerd in het proefschrift.

Voor menselijke spelers is dit soort logica moeilijk om mee te werken. Gelukkig heeft iemand anders een aantal goede openingen gevonden die u over het algemeen kunt gebruiken: Expert spelen in Connect-Four .

Even terzijde, ik heb alle illustraties gemaakt met Haskell “s prachtige diagrammen pakket. In feite, dit hele antwoord was eigenlijk een oefening om de bibliotheek te leren gebruiken, wat ik al een tijdje van plan was te doen! Je kunt de code bekijken op deze kern. De code is rommelig, maar het is een geweldige demonstratie dat, in tegenstelling tot wat vaak wordt gedacht, Haskell eigenlijk geweldig is om interactief prototypen te maken en wegwerpcode te schrijven.

Ik vind het ook gaaf om te zien hoe Emacs SVGs en PNGs in een buffer kan voorvertonen, wat me in wezen een op maat gemaakte omgeving geeft voor het ontwikkelen van afbeeldingen zoals deze: