Qual è la strategia vincente per il primo giocatore nei giochi Connect Four?

Migliore risposta

La “strategia” effettiva è in realtà piuttosto complessa e implica una ricerca esaustiva nei punti da trattare tattiche, quindi non è pratico da usare a mano.

Daltra parte, le intuizioni strategiche e alcune regole generali sono facili da usare per un essere umano e probabilmente ti renderanno relativamente buon giocatore.

Background

Iniziamo esaminando rapidamente connect-4. Il gioco si gioca su una scacchiera 6 × 7; possiamo etichettare ogni riga con un numero e ogni colonna con una lettera:

Ogni giocatore, a turno, sceglie una colonna; la loro pietra è posta nella cella aperta più in basso della colonna. Possiamo scrivere un gioco usando solo le colonne; per esempio, se entrambi i giocatori giocano la colonna centrale possiamo scrivere dd. Questo porterebbe al seguente tabellone: ​​

(Per convenzione, il giocatore 1 sarà blu e il giocatore 2 rosso.)

Una partita può essere vinta collegando quattro pezzi del tuo colore orizzontalmente, verticalmente o diagonalmente:

Unultima nozione utile è una minaccia , che è solo tre pezzi di fila con il quarto quadrato aperto (ma non necessariamente accessibile). Qui, il blu ha una minaccia in diagonale:

Strategia

Il gioco è risolto: il primo giocatore (blu) può sempre forzare una vittoria. Le idee fondamentali alla base della strategia vincente sono piuttosto semplici: controllare zugzwang e controllare dispari / pari righe.

Zugzwang

“Zugzwang” come termine significa perdere perché avere per fare una mossa. Una semplice illustrazione sarebbe avere due minacce una sopra laltra. Ecco un esempio in cui il blu costringe una vittoria sulla colonna c con il rosso a spostarsi:

Tuttavia, minacce doppie come questa sono ragionevolmente facili da riconoscere in anticipo e counter. In pratica, una forma molto più utile di Zugzwang consiste nellattendere che lintero tabellone sia riempito e che rimanga una sola mossa possibile. Considera il semplice esempio in cui il rosso vince a sinistra, con la forza effettiva che si verifica solo dopo un gruppo di mosse:

Minacce pari / dispari

Chi ha una minaccia che verrà inesorabilmente colmata alla fine vincerà. Come abbiamo visto nellesempio precedente, il rosso può vincere con una minaccia in un pari . Al contrario, il blu ha bisogno di una minaccia dispari per vincere: qui è dove lasimmetria nel gioco emerge.

Una strana minaccia “chiude” una colonna e essenzialmente capovolge chi può ottenere quale riga riempiendo lintero boa rd. In particolare, ciò significa che una minaccia dispari valida è “più forte” di una minaccia pari valida: se il blu ha una minaccia dispari in una colonna e il rosso una minaccia pari in unaltra, il blu vincerà comunque. Ecco un esempio (blu per giocare):

Da questa posizione, possiamo riempire ripetutamente fino ad arrivare a posizione in cui il rosso deve giocare c perché g (che contiene un numero dispari di pezzi) comporterebbe la vittoria del blu. Ciò consente la colonna c si riempie finché il rosso non è costretto a perdere:

Il la minaccia dispari “funziona” perché chiude una singola colonna per avere un numero dispari di posizioni, trasformando effettivamente la scacchiera in un numero pari di quadrati (42) a un numero dispari, che capovolge le dinamiche del gioco. Ciò significa anche che se sia rosso e blu hanno minacce dispari indipendenti, si annullano: avendo due colonne dispari riporta il totale a pari.

Più in generale, la distinzione dispari / pari ci dà unidea di controllo : il rosso normalmente controlla il gioco, ma il blu può ottenere il controllo stabilendo una strana minaccia. In pratica, controllo significa essere in grado di giocare qualsiasi quadrato pari o, come opzione, giocare un quadrato dispari ma lasciare che il tuo avversario giochi un quadrato pari in cambio.

Tattiche

La distinzione pari / dispari ci permette di giocare “strategicamente”, un mucchio di mosse avanti, in ogni caso. Per vincere effettivamente in modo coerente, dobbiamo combinare le nostre conoscenze sulla strategia a lungo termine con solide mosse tattiche a breve termine. Dobbiamo tenere a mente piccole trappole come questa:

Regole

La vera strategia vincente per il gioco si riduce a una serie di nove regole basate sui principi strategici trattati in precedenza e sulle tattiche.Le regole sono state sviluppate da Victor Allis nel 1988, credo sia stato il primo a risolvere il gioco.

Le regole possono “t sempre trova la soluzione ottimale: a volte, dovresti fare una vera ricerca attraverso le possibilità, soprattutto per affrontare questioni tattiche.

Ecco quelle che penso siano le regole più importanti, con i nomi che Allis ha dato loro Ci sono alcune regole in più, ma sono per casi speciali o solo combinazioni di regole precedenti; puoi leggere tutte le regole nella tesi vera e propria: Un approccio basato sulla conoscenza di Connect Four .

• baseinverse : puoi sempre rivendicare una delle due caselle accessibili quando il tuo avversario reclama laltra, quindi puoi sempre bloccare un quattro di fila che necessita di due caselle come quella. Ad esempio, il rosso può sempre giocare uno dei quadrati verdi dopo che il blu ha suonato la o ther:

• verticale : puoi sempre bloccare un quadretto di fila verticale giocando uno dei due quadrati direttamente uno sopra laltro. Il rosso può sempre bloccare il quadretto di fila verticale su d giocando uno dei quadrati evidenziati:

• claimeven : chiunque abbia il controllo del gioco (cioè rosso a meno che il blu non abbia una strana ) può giocare una casella in una riga pari (a condizione che quella casella non sia immediatamente giocabile). Questa regola incarna la strategia di base pari / dispari.
• aftereven : se hai il controllo e hai una minaccia in una riga pari, sarai in grado di giocare quella riga tramite claimeven. Ciò significa che qualsiasi minaccia nella stessa colonna sopra quella viene bloccata. Ad esempio, qui il blu non sarà in grado di giocare b3 poiché il rosso ha una minaccia su b2:

• lowinverse : se sono presenti due colonne con un numero dispari di aperte quadrati, il risultato è pari Se ci sono due quadrati dispari In tali colonne che non sono direttamente giocabili, chi controlla il gioco potrà giocarne almeno una. Questo può essere applicato anche alle caselle che sono lontane dallessere giocabili e non una accanto allaltra. In questi due semplici esempi, il rosso può ottenere almeno uno dei due quadrati evidenziati:

Vincere

Il gioco è stato effettivamente risolto attraverso una combinazione di queste regole e una ricerca approfondita: le regole da sole purtroppo non sono sufficienti.

Molte delle regole dipendono dal controllo del gioco. Poiché il rosso ha inizialmente il controllo, il blu non può utilizzare molte delle regole finché non riesce a stabilire una strana minaccia. Il blu può stabilire una strana minaccia utilizzando alcune delle regole che non dipendono dallavere il controllo o solo un pensiero tattico come combinare gruppi di due pezzi per garantire una strana minaccia in futuro.

Si scopre il primo il giocatore può farlo contro il gioco ottimale purché la prima mossa sia d1. Ciò significa che il primo giocatore può sempre vincere. La ricerca che ha effettivamente stabilito questo è anche dettagliata nella tesi.

Per i giocatori umani, questo tipo di logica è difficile da lavorare. Fortunatamente, qualcun altro ha trovato una serie di buone opportunità che puoi generalmente utilizzare: Expert Play in Connect-Four .

Inoltre, per inciso, ho realizzato tutte le illustrazioni utilizzando il meraviglioso pacchetto diagrams di Haskell. Infatti, tutta questa risposta era in realtà un esercizio solo per imparare a usare la libreria, cosa che avevo intenzione di fare per un po ! Puoi dare unocchiata al codice in questa sintesi. Il codice è disordinato, ma “è una grande dimostrazione che, contrariamente a quanto si crede, Haskell è davvero fantastico per la prototipazione interattiva e la scrittura di codice usa e getta.

Inoltre, penso che sia bello vedere come Emacs può visualizzare in anteprima SVG e PNG in un buffer, essenzialmente offrendomi un ambiente su misura per lo sviluppo di immagini come questa: