Original English version: http://wilson.engr.wisc.edu/boxes/method/
Ser på hver mulig sekvens av bevegelser produserer en n! tid for analyse. Mitt program ser på hver mulig posisjon i stedet, noe som gir en 2n tid for analyse. Selv om 2n blir stor raskt, er det ikke nær så stort som n!
Arbeider bakover
For hver posisjon lagrer programmet beste poeng for spilleren på farten for fremtidige bokser. Bokser som allerede er omgitt, ignoreres. Dermed er hver posisjon unikt identifisert av de tilstedeværende linjene. Ingen data om scoring opp til det trekket holdes.
Analysen fungerer bakover fra posisjonen med alle linjene fylt. Denne posisjonen tilordnes verdien gitt i den første linjen i datafilen (normalt null). Deretter behandler programmet posisjonene med en mindre linje fylt inn. Når de er ferdige, behandler det posisjonene med en annen linje mindre. Til slutt kommer det tilbake til den opprinnelige posisjonen.
For hver slik stilling vurderer programmet alle mulige trekk og holder poengsummen det beste resultatet for spilleren på farten.
For hvert mulig trekk sjekker programmet først for å se om null, en eller to nye bokser ble dannet. Hvis ingen nye bokser ble dannet, er poengsummen for flyttingen negativ for poengsummen for den resulterende posisjonen, siden stillingen har den beste poengsummen for den andre spilleren som er innspilt. Hvis en eller to nye bokser ble dannet, er poengsummen for flyttingen poengsummen for den resulterende posisjonen, pluss antall nye bokser siden spilleren er på farten.
Finne posisjoner med et gitt antall linjer
En posisjon er representert av et binært tall med en bit (binært siffer) sted tilordnet hver linje. Biten er 0 hvis linjen er til stede og 1 hvis linjen er fraværende. (Jeg reverserte den vanlige konvensjonen for å gjøre det lettere å se etter nye bokser.)
Jeg deler linjene i grupper. Hver gruppe av linjer er representert av sammenhengende biter i posisjonens binære nummer. Disse bitene kan kopieres og plasseres i et eget tall som representerer tilstanden til linjene i gruppen. For eksempel er det 24 linjer totalt for 3×3-spillet. Programmet bruker to grupper med linjer med 12 linjer hver. For hver mulig linjeantall for en gruppe (0 til 12), konstruerer programmet en liste over tall som representerer en gruppe med det antallet linjer som er til stede. For å finne posisjonene med n-linjersett, kombinerer jeg all den første gruppetilstanden med i linjer satt med den andre gruppetilstanden med ni linjersett hvor jeg varierer over alle mulige verdier som ikke resulterer i et umulig antall linjer for enten gruppe. For eksempel, for å finne alle stillinger med 15 linjer i 3×3-spillet, kombinerer programmet alle første gruppestatistikk med 3 linjer med alle andre gruppestater med 12 linjer (det er bare en av dem), så alle første gruppestater med 4 linjer med alle andre gruppe stater med 11 linjer… og til slutt alle første gruppe stater med 12 linjer (igjen, bare en mulig) med alle andre gruppe stater med 3 linjer.
Sjekker etter nye bokser
Hver linje er gitt et indeksnummer som tilsvarer sin bit i posisjonens binære nummer. Programmet har to sett med bokstavsverdier som refereres ved hjelp av indeksnummeret til en ny linje. Ett sett sjekker om en ny boks over eller til venstre for en ny linje. Den andre kontrollerer en boks under eller til høyre for en ny linje. Disse verdiene brukes til å kontrollere om de andre 3 linjene allerede er til stede. Bittene som svarer til disse 3 linjene er satt til 1; alle andre biter er satt til 0. Testen er utført ved hjelp av en logisk “og” -operasjon mellom posisjonens binære nummer og testverdien. “Og” -operasjonen, for hver bitposisjon, produserer 1 dersom de tilsvarende biter i begge verdier er satt; 0 ellers. Siden posisjonens binære nummer har biter satt til 0 hvis en linje er til stede, gir “og” av denne og testverdien et nullresultat hvis og bare hvis de tre linjene allerede er til stede.
Hvis en boks ikke eksisterer fordi en linje er på kanten, har testverdien alle biter satt, og dermed testes for alle linjer er tilstede. Siden testen er utført før den nye linjen er plassert i posisjonens binære nummer, er det minst en linje ikke satt og testen med denne verdien vil si at det ikke er noen ny boks.
Bruke mange linjegrupper
Etter at den islandske analysen kjørte på bare en halv time, innså jeg at datatiden ikke ville være et problem for 3×5-spillanalysen. Det islandske spillet har 30 åpne linjer mens 3×5-spillet har 38 åpne linjer som gjør det 256 (28) ganger vanskeligere. 256 ganger en halv time er 128 timer eller ca 5 dager. Siden jeg kunne sette opp programmet for å starte hvor det gikk av etter en abort eller omstart, kunne de 5 dagene enkelt gjøres over netter og helger. Så problemet ble å finne ut hvordan man får det til å passe på min maskin med 256 MB RAM og 16 GB ledig diskplass.
Først så det ikke ut som mulig. Lagring av analysen vil ta 238 byte eller 256 GB diskplass. Plassen som trengs i RAM mens du beregner verdien for stillinger med 19 linjer satt mens du refererer til resultatene for stillinger med 20 linjer satt, vil være 56 GB, ganske mye mer enn min kvart i GB RAM.
Forutsatt at linjene var delt inn i to grupper på 19 linjer hver, kunne jeg ha i RAM bare verdiene som svarer til et gitt antall linjer for hver av de to gruppene. For eksempel, mens du gjør posisjoner med 19 linjer, kunne jeg evaluere posisjonene med 9 linjer i den første gruppen og 10 linjer i den andre gruppen. Jeg ringer disse 9/19 10/19 stillingene. For å beregne disse verdiene må jeg referere til to sett med stillinger med 20 linjer: 10/19 10/19 og 9/19 11/19. Jeg trengte ikke begge de 20 linjene i minnet på en gang; de kunne bli brukt en om gangen ved å lagre de beste poengene med tanke på bare nye linjer i den første gruppen for alle 9/19 10/19 stillingene og deretter se om det kunne gjøres noen forbedringer i resultatene med en ny linje i den andre gruppe. De to bufferne ville bare ta 16 GB.
Da innså jeg at jeg kunne bryte opp linjene i mer enn to grupper. Ved å bruke 6 grupper, kunne jeg kutte RAM som trengs for bare 426 MB. En ytterligere kutt ved hjelp av symmetri (se nedenfor) gjorde den tilpasning. Selvfølgelig, for eksempel å finne resultatene for 4/8 3/6 3/6 3/6 3/6 3/6 stillingene, måtte programmet lese i seks forskjellige sett med score med 20 linjer – hver å ha en linje i en av de seks gruppene.
Symmetri
De 3 x 5 spillet er symmetrisk vertikalt og horisontalt, slik at ved å dra fordel av den symmetri, kan jeg dele plassbehov ved 4 (faktisk, ved 3 i min endelige implementering). Paul Stevens rapportert en feil i testen for symmetri over en diagonal på et kvadratisk brett.
For å beregne poengsummen for en stilling, ser programmet på de tidligere beregnede poengene for stillingene som kommer fra å legge til en linje. Men å legge til en linje kan resultere i en posisjon som må symmetrisk omformes før poengsummen kan bli funnet. For å sikre at poengsummen for stillingen som kommer fra den symmetriske transformasjonen er umiddelbart tilgjengelig, er det nødvendig at transformasjonskartet noen linjer inn i samme gruppe. På den måten forblir antallet linjer i hver gruppe det samme etter transformasjon.
Før programmet tilordner linjer til grupper, ser det først etter linjer som er forbundet med hverandre ved symmetrisk transformasjon. I 3×5-spillet er det sju sett med 4 linjer og fives sett med 2 linjer som er tilknyttet. Programmet tildeler deretter settene med linjer til gruppene. For 3×5-spillet som bruker 256 MB RAM, resulterer seks grupper (hver med to sett med linjer) med størrelser 8 6 6 6 6 6.
For å finne ut om en posisjon skal symmetrisk omformes, ser programmet bare på linjene i den første gruppen. Under oppsettfasen skanner programmet gjennom alle mulige linjekonfigurasjoner i den første gruppen av linjer. Til hver konfigurasjon gjelder den vertikal refleksjon, horisontal refleksjon og refleksjon gjennom opprinnelsestransformasjonene. Hvis en av disse transformasjonene resulterer i et tall for tilstanden av linjene i gruppen som er numerisk mindre enn tallet for tilstanden til de opprinnelige linjene, så er (1) konfigurasjonen IKKE inkludert i den koblede listen over konfigurasjoner med en gitt antall linjer satt og (2) informasjon lagres som hvilken symmetrisk transformasjon som skal brukes til å få en posisjon hvis score er beregnet – det vil si hvordan man kommer til den tilsvarende konfigurasjonen med den laveste numeriske verdien for tilstand av sine linjer.
Selv om bare den første gruppen brukes til å se om en transformasjon skal gjøres, når transformasjonen er gjort, påvirker det linjene i alle gruppene.
Beskytter diskplass
Resultatene for posisjoner med et gitt antall linjer i hver gruppe lagres i en enkelt diskfil. For eksempel lagres resultatene for 4/8 3/6 4/6 2/6 3/6 3/6 posisjonene i filen:
\Boxes\3×5\19\4\3\4\2\3.bin
Bakslaget skiller separate nestede mappenavn. 3×5 er navnet på spillet som analyseres. 19 er det totale antall linjer i posisjonen. Resten av mappenavnene og filnavnet kommer fra antall linjer i gruppene. Antall linjer i den siste gruppen er ikke brukt siden det er fikset av de andre tallene. .Bin betyr at dette er en binær fil – innholdet kan ikke vises direkte. Nestede mapper brukes fordi Windows behandler mapper med et stort antall filer veldig sakte.
Symmetriske transformasjoner reduserer diskplassen som kreves fra 256 GB til 85 GB. Det er imidlertid ikke nødvendig å beholde alle analyseresultatene. Så snart programmet ble ferdig med stillinger med 19 linjer, kunne resultatene for stillinger med 20 linjer slettes. Med bare 16 GB ledig diskplass tilgjengelig, holder programmet resultatet for posisjoner med 15 eller færre linjer. Dette resulterer i en “åpningsbok” for 3×5-spillet.
Imidlertid lagrer bare resultatene for 20 linjeposisjoner og 19 linjeposisjoner tar fortsatt 22 GB. Dette løses ved å slette deler av de 20 linjepostfilene som de ikke lenger er nødvendige for ytterligere beregning av score for 19 linjeposisjoner. Når programmet går gjennom alle mulige kombinasjoner av linjer teller for gruppene som legger til 19 linjer, blir tellingen for den første gruppen av linjer aldri redusert. Således, når tellingen for den første gruppen av linjer beveger seg fra 0 til 1, kan alle filene som starter med \Boxes\3×5\20\0\ bli slettet. Med denne endringen passer analysen i 16 GB tilgjengelig.
Kjeder
På dette punktet, programmet var fortsatt utilstrekkelig for å løse de 5×5 problemer i kapittel 12 i Prikker-og-bokser spill av Elwyn Berlekamp (AK Peters, 2000). Hvis datamaskiner fortsetter å doble sin kapasitet hver 18. måned, bør vi være i stand til å analysere hele 5×5 spillet i 2034, siden den har 22 flere linjer enn 3×5 spill, som ble analysert i 2001. Programmet kan nå håndtere stillinger med opptil 36 åpne linjer hvor posisjonen har ingen symmetri og 14 GB diskplass er tilgjengelig. Det menes at kun de 5×5 posisjoner med 24 eller flere linjer (av 60) kan takles. Ingen av kapittel 12 problemene hadde som mange linjer.
En kjede er en streng av en eller flere bokser med to sider fylt inn. Jeg antok at når en av spillerne tok en linje i en kjede, involverer minst en av de beste spillelinjene resten av linjene i kjeden fylles inn, av en spiller eller den andre, før noen linjer andre steder er fylt ut. Hvert sett med kjedelinjer er representert av en enkelt “pseudolinje”. Posisjonsrepresentasjonen i programmet har bare en bit å si om kjeden har blitt fullstendig fylt eller fortsatt tom. For eksempel er her posisjonen for problem 12.18 (før strekket i strekket linje):
+ + + . + + +
| . |
| . |
| . |
+ + . + . + + +
| . | .
| . | ....
| . |
+ + . +-----+-----+-----+
| . |
| . | ..........
| . | .
+ + . + . +-----+ . +
| | .
| .... | ....
| . |
+ + + . + . +-----+
| .
| ....
|
+ + +-----+ + +
Punkter markerer kjedene som hver representeres av en enkelt pseudolinje. Av de 60 linjene er 15 fylt inn, 30 er tomme og 15 er involvert i 6 kjeder. Posisjonene som kan oppstå fra denne startposisjonen er representert ved 36 biter – 30 for de tomme linjene og 6 for de 6 kjedene. Dermed er denne posisjonen bare knapt innenfor dagens evner av programmet.
I mange av stillingene som kommer fra en gitt startposisjon, vil innledende kjeder bli en del av lengre kjeder. Programmet endrer ikke stillingsrepresentasjonsskjemaet i denne situasjonen. Pseudoliniene fortsetter å representere bare de innledende kjedene. Dette skyldes at stillingsrepresentasjonen er brukt som en “adresse” for å få tilgang til de tidligere beregnede resultatene.
Mens du vurderer om du går inn i en innledende kjede, er en god ide for spilleren på farten, har programmet tilgjengelig nettotscore med beste spill for fremtidige bokser for spilleren på farten etter at hele startkjeden er fylt. Programmet må da sjekke boksene rundt kjeden for å se hvilken spiller som har den første sjansen til å ta boksene i kjeden, for å se om den spilleren ville tjene på å gjøre et offer for å unngå å komme på farten etter at kjeden er fylt, og for å sjekke om kjeden har blitt utvidet eller til og med gjort en del av en løkke.
Hvis den innledende kjeden har en 3-sidig boks på begge sider like utenfor kjeden, kan spilleren på farten bevege seg inn i kjeden med en fangst og har mulighet til å ta boksene i kjeden. Ellers er det den andre spilleren som har muligheten i kjeden. Jeg ringer personen med muligheten til å ta boksene i kjeden, “kjedespilleren”.
Hvis den første kjeden har blitt utvidet nok til at kjedespilleren kan gjøre ofre senere, er resultatet etter at kjeden er fullstendig gjengitt, gjenspeiler dette alternativet og kjedespilleren tar alle boksene i den innledende kjeden. Ellers sjekker programmet for å se om det er nok plass til et offer, forutsatt at den beste flyttingen går inn i kjeden av spilleren som er opprinnelig på farten, og ser på den innledende kjeden og eventuelle utvidelser. Hvis det fortsatt ikke er nok plass til et offer, tar kjedespilleren alle boksene. Ellers sjekker programmet om et offer er lønnsomt, og vurderer i så fall å gå inn i kjeden for spilleren som er opprinnelig på farten, forutsatt at kjedespilleren gjør ofringen.
Siste flytt straffen
Programmet gjør det mulig for en straff for å bli brukt til stillingen av spilleren som gjør siste trekk. Hvis denne straffen er stor nok, vil trekkene valgt som beste være de samme som er valgt av nimstring analyse. For eksempel har jeg analysert problem 11.16 med straffer med økende omfang. Programmet tillater ikke brøk straffer fordi de ville levere ingen tilleggsinformasjon:
- Hvis du kjører analyse på to forskjellige straffer poengsummen for et trekk ikke kan endre med mer enn pluss eller minus forskjellen i straffer.
- For påfølgende heltall straffer, en analyseresultater i alle like heltallsmultipler resultatene og andre resultater i alle odde heltall score.
- Således for påfølgende heltall straffer, resultatet alltid endrer seg, resultatene endres alltid med +1 eller -1 …maksimalt mulig.
- Derfor kan man få utlignet for en brøk straff ved å interpolere mellom poengsummene for de tilstøtende heltallige straffer.
Gal trekk
Den endelige versjonen av programmet inkluderer gal trekk analyse. I utgangen blir en poeng suffiks av v dersom spiller A må gjøre neste gal trekk eller ved ^ hvis spiller B må. Hvis ingen av spillerne må foreta et lunetrykk, brukes ikke noe suffiks. Under analysen brukes to biter av byten som brukes til å holde poengsummen, for å holde den lunefulle tilstanden av bevegelsen. Dette etterlater bare 6 biter for resultatene. Dermed kan bare score fra -32 til +31 lagres. Dette gjør den gal flytteanalyseversjonen av programmet upålitelig på brett større enn 5 av 6. Derfor beholder jeg en versjon tilgjengelig som ikke gjør gal flytteanalyse for bruk med større brett.
For å finne gal flytter i en rimelig mengde datatid, gjør programmet en gal bonus sjekk når det er mulig å fange en boks. Hvis boksen på den andre siden av linjen som vurderes, har nøyaktig to andre sider allerede fylt ut, konkluderer programmet at motstanders forrige trekk var gal.
Hjørner
William Fraser skrev: “Tar du hensyn til det faktum at [ab] og [ba] refererer til ekvivalente koblinger? Dermed (hvis du legger de åtte hjørnelinkene i den endelige 8 linjegruppen) kan du bare lagre 3^4=81 oppføringer i stedet for 2^8=256. Dette ville være helt uavhengig av rotasjon/refleksjon. Det reduserer diskforbruket med 75% og minnebruk med gjennomsnittlig 75%.”
Jeg implementerte dette forslaget, som gjorde det mulig å analysere 4×4-spillet.