Care este strategia câștigătoare pentru primul jucător din jocurile Connect Four?

Cel mai bun răspuns

„Strategia” reală este de fapt destul de complexă și implică o căutare exhaustivă în punctele de rezolvat cu tactici, deci nu este practic de folosit manual.

Pe de altă parte, ideile strategice și unele reguli de uz general sunt ușor de utilizat pentru un om și probabil vă vor face un jucător bun.

Fundal

Să începem examinând rapid connect-4. Jocul se joacă pe o tablă 6 × 7; putem eticheta fiecare rând cu un număr și fiecare coloană cu o literă:

Fiecare jucător se alternează pentru a alege o coloană; piatra lor este plasată în celula cea mai deschisă din coloană. Putem scrie un joc folosind doar coloanele; de exemplu, dacă ambii jucători joacă coloana centrală putem scrie dd. Acest lucru ar duce la următoarea placă:

(Prin convenție, jucătorul 1 va fi albastru și jucătorul 2 roșu.)

Un joc poate fi câștigat conectând patru bucăți de culoare pe orizontală, verticală sau diagonală:

O ultimă noțiune utilă este o amenințare , care este doar trei piese la rând cu al patrulea pătrat deschis (dar nu neapărat accesibil). Aici, albastrul are o amenințare într-o diagonală:

Strategie

Jocul este rezolvat: primul jucător (albastru) poate întotdeauna forța să câștige. Ideile de bază din spatele strategiei câștigătoare sunt destul de simple: controlul zugzwang și controlul impar / par rânduri.

Zugzwang

„Zugzwang” ca termen înseamnă a pierde deoarece trebuie să facă o mișcare. O ilustrare simplă ar avea două amenințări una peste alta. Iată un exemplu de albastru care forțează o victorie pe coloana c cu roșu să se miște:

Cu toate acestea, amenințări duble ca aceasta sunt rezonabil de ușor de recunoscut înainte și în timp. În practică, o formă mult mai utilă de Zugzwang presupune doar așteptarea până când este completată întreaga placă și rămâne o singură mișcare posibilă. Luați în considerare exemplul simplu în care roșul câștigă pe stânga, cu forța reală care se întâmplă numai după o grămadă de mișcări:

Amenințări pare / ciudate

Oricine are o amenințare care va fi completată inexorabil va câștiga în cele din urmă. După cum am văzut în exemplul anterior, roșul poate câștiga cu o amenințare într-un rând egal. În schimb, albastrul are nevoie de o ciudată pentru a câștiga: aici este asimetria din joc apare.

O ciudată amenințare „acoperă” o coloană și, în esență, răstoarnă cine poate obține care rând atunci când umple întregul boa rd. În special, acest lucru înseamnă că o amenințare impară validă este „mai puternică” decât o amenințare pare valabilă: dacă albastrul are o amenințare impară într-o coloană și roșu o amenințare pare în alta, albastrul va câștiga în continuare. Iată un exemplu (albastru pentru a juca):

Din această poziție, putem completa în mod repetat până când ajungem la un poziția în care roșul trebuie să joace c deoarece g (care are un număr impar de piese) ar avea ca rezultat câștigarea albastră. coloana c se completează până când roșul este obligat să piardă:

amenințarea ciudată „funcționează” deoarece limitează o singură coloană pentru a avea un număr impar de poziții – transformând efectiv placa de la un număr par de pătrate (42) la un număr impar, care întoarce dinamica jocului. Aceasta înseamnă, de asemenea, că dacă ambele roșu și albastru au amenințări impare independente, se anulează: având două coloane impare readuc totalul la egalitate.

Mai general, distincția pare / impar ne oferă o noțiune de control : roșu controlează în mod normal jocul, dar albastrul poate câștiga controlul stabilind o amenințare ciudată. În practică, controlul înseamnă a putea juca orice pătrate pare sau, ca opțiune, a juca un pătrat impar, dar lăsați-vă adversarul să joace un pătrat egal în schimb. div> Tactics

Distincția impar / pare ne permite să jucăm „strategic” – o grămadă de mișcări înainte, în orice caz. Pentru a câștiga în mod consecvent, trebuie să combinăm cunoștințele noastre despre strategia pe termen lung cu mișcări tactice solide pe termen scurt. Trebuie să avem în vedere mici capcane ca acestea:

Reguli

Strategia de câștig efectivă a jocului se reduce la un set de nouă reguli bazate pe principiile strategice abordate anterior și pe tactici.Regulile au fost elaborate de Victor Allis în 1988 – cred că a fost prima persoană care a rezolvat jocul.

Regulile pot fi „t întotdeauna găsiți soluția optimă: uneori, ar trebui să faceți o căutare efectivă prin posibilități, în mare parte pentru a face față preocupărilor tactice.

Iată care cred că sunt cele mai importante reguli, cu numele pe care Allis le-a dat Există încă câteva reguli, dar sunt fie pentru cazuri speciale, fie doar pentru combinații de reguli anterioare; puteți citi despre toate regulile din teza actuală: O abordare bazată pe cunoștințe a Connect Four .

• baseinverse : poți revendica oricând unul din cele două pătrate accesibile atunci când adversarul tău îl revendică pe celălalt, deci poți oricând să blochezi un patru la rând care are nevoie de două pătrate așa. De exemplu, roșu poate juca întotdeauna unul dintre pătratele verzi după ce albastrul joacă o acolo:

• vertical : puteți oricând să blocați un patru-la-rând vertical jucând unul dintre cele două pătrate direct unul deasupra celuilalt. Roșul poate bloca întotdeauna verticalul patru la rând pe d jucând unul dintre pătratele evidențiate:

• claimeven : oricine are controlul jocului (adică roșu, cu excepția cazului în care albastrul are o amenințare ciudată) ) poate juca un pătrat într-un rând par (atâta timp cât acel pătrat nu poate fi redat imediat). Această regulă întruchipează strategia de bază impar / pare.
• aftereven : dacă dețineți controlul și aveți o amenințare într-un rând egal, veți putea juca acel rând prin claimeven. Aceasta înseamnă că orice amenințări din aceeași coloană de deasupra celei sunt blocate. De exemplu, aici albastru nu va putea reda b3 deoarece roșu are o amenințare pe b2:

• lowinverse : dacă există două coloane cu un număr impar de deschise pătrate, rezultatul este par. Dacă există două pătrate impare se află în astfel de coloane care nu pot fi redate direct, oricine controlează jocul va putea juca cel puțin una dintre ele. Acest lucru se poate aplica și pătratelor care sunt departe de a fi redate și nu una lângă alta. În aceste două exemple simple, roșu poate obține cel puțin unul dintre cele două pătrate evidențiate:

Câștigător

Jocul a fost de fapt rezolvat printr-o combinație a acestor reguli și unele căutări exhaustive – regulile de la sine nu sunt, din păcate, suficiente.

Multe dintre reguli depind de controlul jocului. Deoarece roșul are controlul inițial, albastrul nu poate folosi multe dintre reguli până când nu reușesc să stabilească o amenințare ciudată. Albastru poate crea o amenințare ciudată folosind unele dintre regulile care nu depind de controlul sau doar de gândirea tactică, cum ar fi combinarea grupurilor de două piese pentru a garanta o amenințare ciudată în viitor.

Se pare că prima jucătorul poate face acest lucru împotriva jocului optim atâta timp cât prima mișcare este d1. Aceasta înseamnă că primul jucător poate câștiga întotdeauna. Căutarea care a stabilit efectiv acest lucru este, de asemenea, detaliată în teză.

Pentru jucătorii umani, acest tip de logică este greu de lucrat. Din fericire, altcineva a găsit un set de deschideri bune pe care le puteți folosi în general: Expert Play in Connect-Four .

De asemenea, ca o parte, am făcut toate ilustrațiile folosind minunatele pachete diagramelor Haskell. De fapt, tot acest răspuns a fost de fapt un exercițiu doar pentru a învăța cum să folosesc biblioteca, ceea ce am vrut să fac de ceva vreme! Puteți arunca o privire asupra codului de pe acest esențial. Codul este dezordonat, dar este „o demonstrație extraordinară că, contrar credinței populare, Haskell este de fapt grozav pentru prototiparea interactivă și scrierea codului de eliminare.

De asemenea, cred că este bine să văd cum Emacs poate previzualiza SVG-urile și PNG-urile într-un buffer, oferindu-mi în esență un mediu personalizat pentru dezvoltarea de imagini de acest gen: