Hva er den vinnende strategien for den første spilleren i Connect Four-spill?

Beste svaret

Den faktiske «strategien» er faktisk ganske kompleks og innebærer uttømmende søk på punkter å håndtere med taktikk, så det er ikke praktisk å bruke for hånd.

På den annen side er den strategiske innsikten og noen generelle regler enkle å bruke for et menneske, og vil sannsynligvis gjøre deg til en relativt god spiller.

Bakgrunn

La oss starte med å gå raskt gjennom connect-4. Spillet spilles på et 6 × 7 brett; vi kan merke hver rad med et tall og hver kolonne med en bokstav:

Hver spiller bytter på å velge en kolonne; steinen deres er plassert i den nederste, mest åpne cellen i kolonnen. Vi kan skrive et spill ved hjelp av bare kolonnene; for eksempel, hvis begge spillerne spiller den sentrale kolonnen, kan vi skrive dd. Dette vil føre til følgende brett:

(Etter konvensjon vil spiller 1 være blå og spiller 2 rød.)

Et spill kan vinnes ved å koble fire stykker av fargen din horisontalt, vertikalt eller diagonalt:

En siste nyttig forestilling er en trussel , som bare er tre stykker på rad med den fjerde firkanten åpen (men ikke nødvendigvis tilgjengelig). Her har blå en trussel i en diagonal:

Strategi

Spillet er løst: den første spilleren (blå) kan alltid tvinge en seier. Kjerneideene bak vinnerstrategien er ganske enkle: å kontrollere zugzwang og kontrollere odd / even rader.

Zugzwang

«Zugzwang» som begrep betyr å tape fordi du har til å gjøre et trekk. En enkel illustrasjon ville være å ha to trusler oppå hverandre. Her er et eksempel på blått som tvinger en seier på kolonne c med rødt for å flytte:

Dobbelt trusler som dette er rimelig enkle å gjenkjenne på forhånd og mot. I praksis innebærer en mye mer nyttig form for Zugzwang bare å vente til hele brettet er fylt og det er bare ett mulig trekk igjen. Tenk på det enkle eksemplet der rød vinner til venstre, med den faktiske kraften som bare skjer etter en mengde trekk:

Jevn / merkelig trussel

Den som har en trussel som ubønnhørlig blir fylt, vil vinne til slutt. Som vi så i forrige eksempel, kan rød vinne med en trussel i en jevn rad. Derimot trenger blått en odd trussel for å vinne: det er her asymmetrien i spillet dukker opp.

En merkelig trussel «tapper» en kolonne og snur i hovedsak hvem som kan få hvilken rad når de fyller hele boaen rd. Spesielt betyr dette at en gyldig odd trussel er «sterkere» enn en gyldig jevn trussel: hvis blå har en merkelig trussel i en kolonne og rød en jevn trussel i en annen, vil blå fortsatt vinne. Her er et eksempel (blått å spille):

Fra denne posisjonen kan vi fylle gjentatte ganger til vi kommer til en posisjon der rødt må spille c fordi g (som har et ulikt antall brikker i seg) vil resultere i blå vinn. Dette lar c -kolonnen fylles opp til rødt blir tvunget til å miste:

The merkelig trussel «fungerer» fordi den lukker av en enkelt kolonne for å ha et odd antall posisjoner – effektivt vender tavlen fra å ha et jevnt antall firkanter (42) til et oddetall, som snur dynamikken i spillet. Dette betyr også at hvis både rød og blå har uavhengige oddetrusler, avbryter de: å ha to odde kolonner bringer totalen tilbake til å være jevn.

Mer generelt gir den ulige / jevne skillet oss en forestilling om kontroll : rødt kontrollerer normalt spillet, men blått kan få kontroll ved å etablere en merkelig trussel. I praksis betyr kontroll å være i stand til å spille noen jevne firkanter eller, som et alternativ, spille en merkelig firkant, men la motstanderen spille en jevn firkant i retur.

Taktikk

Den merkelige / jevne skillet lar oss spille «strategisk» – en haug med bevegelser fremover, i alle fall. For å faktisk vinne konsekvent, må vi kombinere kunnskapen vår om langsiktig strategi med sunne taktiske kortsiktige trekk. Vi må ha små feller som dette i tankene:

Regler

Den faktiske vinnestrategien for spillet kommer ned på et sett med ni regler basert på de strategiske prinsippene som ble dekket tidligere og taktikk.Reglene ble utviklet av Victor Allis i 1988 – jeg tror han var den første personen som løste spillet.

Reglene kan «t alltid finn den optimale løsningen: noen ganger må du gjøre et faktisk søk ​​gjennom muligheter, i stor grad for å håndtere taktiske bekymringer.

Her er hva jeg synes er de viktigste reglene, med navnene Allis ga dem Det er noen flere regler, men de er enten for spesielle tilfeller eller bare for kombinasjoner av tidligere regler, du kan lese om alle reglene i selve avhandlingen: En kunnskapsbasert tilnærming av Connect Four .

• baseinverse : du kan alltid gjøre krav på en av to tilgjengelige firkanter når motstanderen din hevder den andre, slik at du alltid kan blokkere en fire-på-en-rad som trenger to ruter slik. For eksempel kan rød alltid spille en av de grønne rutene etter blå spiller på o ther:

• loddrett : du kan alltid blokkere en vertikal fire-på-en-rad ved å spille en av de to rutene rett over hverandre. Rødt kan alltid blokkere den vertikale fire-på-en-rad på d ved å spille en av de uthevede rutene:

• claimeven : den som har kontroll over spillet (dvs. rødt med mindre blå har en merkelig trussel ) kan spille en firkant i en jevn rad (så lenge den firkanten ikke kan spilles umiddelbart). Denne regelen inneholder den grunnleggende oddetall / jevn-strategien.
• etterpå : Hvis du har kontroll og har en trussel i en jevn rad, vil du kunne spille den raden via claimeven. Dette betyr at alle trusler i samme kolonne over den ene er blokkert. For eksempel her blå vil ikke kunne spille b3 siden rød har en trussel mot b2:

• lowvers : hvis det er to kolonner med et oddetall åpent kvadrater, er resultatet jevnt. Hvis det er to odde kvadrater i slike kolonner som ikke er direkte spillbare, vil den som styrer spillet kunne spille minst en av dem. Dette kan også gjelde firkanter som er langt fra å være spillbare og ikke ved siden av hverandre. I disse to enkle eksemplene kan rødt få minst ett av de to uthevede rutene:

Vinne

Spillet ble faktisk løst gjennom en kombinasjon av disse reglene og litt uttømmende søk – reglene i seg selv er dessverre ikke nok.

Mange av reglene er avhengig av å ha kontroll over spillet. Siden rød først har kontroll, kan blå ikke bruke mange av reglene før de klarer å etablere en merkelig trussel. Blå kan etablere en merkelig trussel ved å bruke noen av reglene som ikke er avhengig av å ha kontroll eller bare taktisk tenkning som å kombinere grupper på to stykker for å garantere en merkelig trussel i fremtiden.

Det viser seg at den første spilleren kan gjøre dette mot optimalt spill så lenge første trekk er d1. Dette betyr at den første spilleren alltid kan vinne. Søket som faktisk etablerte dette er også detaljert i oppgaven.

For menneskelige spillere er denne typen logikk vanskelig å jobbe med. Heldigvis fant noen andre et sett med gode åpninger som du generelt kan bruke: Ekspertspill i Connect-Four .

Også, som en side, lagde jeg alle illustrasjonene ved hjelp av Haskells «fantastiske diagrammer -pakken. Faktisk hele dette svaret var faktisk en øvelse bare for å lære å bruke biblioteket, som jeg har ment å gjøre en stund! Du kan ta en titt på koden på denne kjernen. Koden er rotete, men den er en flott demonstrasjon av at, i motsetning til populær tro, er Haskell faktisk flott for interaktiv prototyping og skriving av kaste-kode.

Også, jeg synes det er kult å se hvordan Emacs kan forhåndsvise SVG-er og PNG-er i en buffer, og gir meg et skreddersydd miljø for å utvikle bilder som dette: