Bästa svaret
Den faktiska ”strategin” är faktiskt ganska komplex och involverar uttömmande sökning efter poäng att hantera med taktik, så det är inte praktiskt att använda för hand.
Å andra sidan är de strategiska insikterna och vissa allmänna regler enkla att använda för en människa och kommer förmodligen att göra dig till en relativt bra spelare.
Bakgrund
Låt oss börja med att snabbt granska connect-4. Spelet spelas på ett 6 × 7-bräde; vi kan märka varje rad med ett nummer och varje kolumn med en bokstav:
Varje spelare turas om att välja en kolumn; deras sten är placerad längst ner i cellen i kolumnen. Vi kan skriva ett spel med bara kolumnerna; Till exempel, om båda spelarna spelar den centrala kolumnen kan vi skriva dd. Detta skulle leda till följande tavla:
(Enligt konvention är spelare 1 blå och spelare 2 röd.)
Ett spel kan vinnas genom att ansluta fyra delar av din färg horisontellt, vertikalt eller diagonalt:
En sista användbar uppfattning är ett -hot , som bara är tre delar i rad med det fjärde torget öppet (men inte nödvändigtvis tillgängligt). Här har blått ett hot i en diagonal:
Strategi
Spelet är löst: den första spelaren (blå) kan alltid tvinga en vinst. Kärnidéerna bakom den vinnande strategin är ganska enkla: att styra zugzwang och kontrollera udda / jämnt rader.
Zugzwang
”Zugzwang” som term betyder att förlora eftersom du måste göra ett drag. En enkel illustration skulle vara att ha två hot ovanpå varandra. Här är ett exempel på blått som tvingar en vinst i kolumn c med rött för att flytta:
Men dubbla hot som detta är rimligt lätta att känna igen i förväg och mot. I praktiken innebär en mycket mer användbar form av Zugzwang att bara vänta tills hela brädet är fyllt och det bara finns ett möjligt drag kvar. Tänk på det enkla exemplet där röd vinner till vänster med den faktiska kraften som bara händer efter en massa drag:
Jämna / udda hot
Den som har ett hot som obevekligt kommer att fyllas vinner till slut. Som vi såg i föregående exempel kan rött vinna med ett hot i en jämn rad. Däremot behöver blått ett udda hot för att vinna: det är här asymmetrin i spelet framträder.
Ett udda hot ”täcker” en kolumn och vänder i huvudsak vem som kan få vilken rad när man fyller hela boa rd. I synnerhet betyder detta att ett giltigt udda hot är ”starkare” än ett giltigt jämnt hot: om blått har ett udda hot i en kolumn och rött ett jämnt hot i en annan, kommer blå fortfarande att vinna. Här är ett exempel (blått att spela):
Från denna position kan vi fylla upprepade gånger tills vi kommer till en position där rött måste spela c eftersom g (som har ett udda antal bitar i sig) skulle resultera i blått vinnande. Detta låter c -kolumnen fylls upp tills rött tvingas förlora:
udda hot ”fungerar” eftersom det täcker en enda kolumn för att ha ett udda antal positioner – vilket effektivt gör att styrelsen får ett jämnt antal rutor (42) till ett udda tal som vänder på dynamiken i spelet. Detta betyder också att om både rött och blått har oberoende udda hot, avbryter de: att ha två udda kolumner gör att summan återgår till jämn.
Mer allmänt ger den udda / jämna skillnaden oss en uppfattning om kontroll : rött kontrollerar normalt spelet, men blått kan få kontroll genom att skapa ett udda hot. I praktiken betyder kontroll att kunna spela alla jämna rutor eller, som ett alternativ, spela en udda kvadrat men låta din motståndare spela en jämn kvadrat i gengäld.
Taktik
Den udda / jämna skillnaden låter oss spela ”strategiskt” – en massa drag framåt, i alla fall. För att faktiskt vinna konsekvent måste vi kombinera vår kunskap om långsiktig strategi med sunda taktiska kortsiktiga drag. Vi måste ha sådana små fällor i åtanke:
Regler
Den faktiska vinnarstrategin för spelet kommer ner till en uppsättning av nio regler baserade på tidigare strategiska principer och taktik.Reglerna utvecklades av Victor Allis 1988 – jag tror att han var den första personen som löste spelet.
Reglerna kan ”t alltid hitta den optimala lösningen: ibland måste du göra en faktisk sökning genom möjligheter, till stor del för att hantera taktiska problem.
Här är vad jag tycker är de viktigaste reglerna, med namnen Allis gav dem Det finns några fler regler, men de är antingen för speciella fall eller bara för kombinationer av tidigare regler, du kan läsa om alla regler i själva avhandlingen: En kunskapsbaserad metod för Connect Four .
- baseinverse : du kan alltid göra anspråk på en av två tillgängliga rutor när din motståndare gör anspråk på den andra, så du kan alltid blockera en fyr i rad som behöver två rutor så. Till exempel kan rött alltid spela en av de gröna rutorna efter blå spelar o ther:
- vertikalt : du kan alltid blockera en vertikal fyra i rad genom att spela en av de två rutorna direkt ovanför varandra. Rött kan alltid blockera den vertikala fyra i rad på
dgenom att spela en av de markerade rutorna:
- claimeven : den som har kontroll över spelet (dvs. rött såvida inte blått har ett udda hot ) kan spela en kvadrat i en jämn rad (så länge den kvadraten inte kan spelas omedelbart). Denna regel innehåller den grundläggande udda / jämna strategin.
- efterpå : om du har kontroll och har ett hot i en jämn rad kommer du att kunna spela den raden via claimeven. Detta innebär att alla hot i samma kolumn ovanför den är blockerade. Till exempel här blå kommer inte att kunna spela
b3eftersom rött har ett hot motb2:
- lågomvänd : om det finns två kolumner med ett udda antal öppna rutor är resultatet jämnt. Om det finns två udda rutor es i sådana kolumner som inte är direkt spelbara, vem som styr spelet kan spela minst en av dem. Detta kan också gälla rutor som är långt ifrån spelbara och inte bredvid varandra. I dessa två enkla exempel kan röd få åtminstone en av de två markerade rutorna:
Vinnande
Spelet löstes faktiskt genom en kombination av dessa regler och lite uttömmande sökning – reglerna i sig är tyvärr inte tillräckliga.
Många av reglerna beror på att ha kontroll över spelet. Eftersom rött har kontroll från början kan blå inte använda många av reglerna förrän de lyckas skapa ett udda hot. Blå kan skapa ett udda hot genom att använda några av de regler som inte beror på att ha kontroll eller bara taktiskt tänkande som att kombinera grupper om två delar för att garantera ett udda hot i framtiden.
Det visar sig att den första spelaren kan göra detta mot optimalt spel så länge det första steget är d1. Det betyder att den första spelaren alltid kan vinna. Sökningen som faktiskt etablerade detta beskrivs också i avhandlingen.
För mänskliga spelare är denna typ av logik svår att arbeta med. Lyckligtvis hittade någon annan en uppsättning bra öppningar som du vanligtvis kan använda: Expertspel i Connect-Four .
Dessutom gjorde jag alla illustrationer med hjälp av Haskells ”underbara diagram -paket. Faktum är att hela svaret var faktiskt en övning bara för att lära mig hur man använder biblioteket, vilket jag har tänkt göra ett tag! Du kan ta en titt på koden på den här kärnan. Koden är rörig, men det är en fantastisk demonstration att, i motsats till vad många tror, är Haskell faktiskt bra för interaktiv prototypning och skrivning av bortkastningskod.
Jag tycker också att det är coolt att se hur Emacs kan förhandsgranska SVG: er och PNG: er i en buffert, vilket i huvudsak ger mig en skräddarsydd miljö för att utveckla bilder så här: