Arbetar bakåt
För varje position lagrar programmet den bästa poängen för spelaren i farten för framtida rutor. Lådor som redan är omgivna ignoreras. Således identifieras varje position unikt med de närvarande linjerna. Ingen data om poäng upp till det draget sparas.
Analysen fungerar bakåt från positionen med alla rader fyllda. Den positionen tilldelas det värde som ges i den första raden i datafilen (normalt noll). Sedan bearbetar programmet positionerna med en mindre rad fylld i. När de är färdiga bearbetas positionerna med en annan rad mindre. Så småningom kommer det tillbaka till sin ursprungliga position.
För varje sådan position tar programmet hänsyn till alla möjliga drag och håller poängen med det bästa resultatet för spelaren på resande fot.
För varje möjlig flytt kontrollerar programmet först om noll, en eller två nya rutor bildades. Om inga nya rutor bildades är poängen för flytten det negativa av poängen för den resulterande positionen eftersom positionen har den bästa poängen för den andra spelaren som spelats in. Om en eller två nya rutor bildades är poängen för flytten poängen för den resulterande positionen plus antalet nya rutor eftersom spelaren förblir på språng.
Hitta positioner med ett givet antal linjer
En position representeras av ett binärt tal med en bit (binär siffra) tilldelad varje rad. Biten är 0 om raden är närvarande och 1 om raden saknas. (Jag vände om den vanliga konventionen för att göra det lättare att söka efter nya rutor.)
Jag delar upp raderna i grupper. Varje grupp av linjer representeras av på varandra följande bitar i positionens binära nummer. Dessa bitar kan kopieras och placeras i ett separat nummer som representerar linjernas tillstånd i gruppen. Till exempel, för 3×3-spelet finns det totalt 24 rader. Programmet använder två grupper av rader med vardera 12 rader. För varje möjlig radräkning för en grupp (0 till 12) konstruerar programmet en lista med nummer som representerar en grupp med det antal rader som finns. Sedan för att hitta positionerna med n-raduppsättningar, kombinerar jag alla de första grupptillstånden med i-linjerna inställda med det andra grupptillståndet med ni-linjeruppsättningen där jag varierar över alla möjliga värden som inte resulterar i ett omöjligt antal rader grupp. Till exempel, för att hitta alla positioner med 15 rader i 3×3-spelet,programmet kombinerar alla första grupptillstånd med 3 rader med alla andra grupptillstånd med 12 rader (det finns bara en av dessa), sedan alla första grupptillstånd med 4 rader med alla andra grupptillstånd med 11 rader, … och slutligen alla första grupptillstånd med 12 rader (igen, endast en möjlig) med alla andra grupptillstånd med 3 rader.
Letar efter nya lådor
Varje rad ges ett indexnummer som motsvarar dess bit i positionens binära nummer. Programmet har två uppsättningar lådtestvärden som refereras med indexnumret för en ny rad. En uppsättning söker efter en ny ruta ovanför eller till vänster om en ny rad. Den andra söker efter en ruta nedan eller till höger om en ny rad. Dessa värden används för att kontrollera om de andra tre raderna redan finns. Bitarna som motsvarar dessa 3 rader är inställda på 1; alla andra bitar är inställda på 0. Testet görs med en logisk “och” operation mellan positionens binära tal och testvärdet. “Och” -operationen, för varje bitposition, producerar 1 om motsvarande bitar i båda värdena är inställda; 0 annars. Eftersom positionens binära antal har bitar inställda på 0 om en rad finns, kommer “och”av detta och testvärdet ger ett nollresultat om och bara om de tre raderna redan finns.
Om det inte finns en ruta på grund av att en rad är på kanten, har testvärdet alla bitar inställda och därmed testas för alla rader som finns. Eftersom testet utförs innan den nya raden placeras i positionens binära nummer finns det minst en rad som inte är inställd och testet med detta värde säger att det inte finns någon ny ruta.
Använda många linjegrupper
Efter att den isländska analysen gick på bara en halvtimme insåg jag att datatiden inte skulle vara ett problem för 3×5-spelanalysen. Det isländska spelet har 30 öppna linjer medan 3×5-spelet har 38 öppna linjer vilket gör det 256 (2 8 ) gånger svårare. 256 gånger en halvtimme är 128 timmar eller cirka 5 dagar. Eftersom jag kunde ställa in programmet för att börja där det slutade efter ett avbrott eller omstart, kunde de fem dagarna enkelt göras över nätter och helger. Så problemet blev att räkna ut hur jag skulle få den att passa på min maskin med 256 MB RAM och 16 GB ledigt diskutrymme.
Först såg det inte möjligt ut. Att lagra analysen tar 2 38 byte eller 256 GB diskutrymme. Det utrymme som behövs i RAM vid beräkning av värdet för positioner med 19 rader inställda medan man hänvisar till resultaten för positioner med 20 rader är 56 GB, snarare mer än mitt en kvarts GB RAM.
Förutsatt att raderna delades in i två grupper om 19 rader vardera, kunde jag ha i RAM bara de värden som motsvarar ett givet antal rader för var och en av de två grupperna. När jag till exempel gör positioner med 19 rader kan jag utvärdera positionerna med 9 rader i den första gruppen och 10 rader i den andra gruppen. Jag kallar dessa 9/19 10/19 positioner. För att beräkna dessa värden måste jag referera till två uppsättningar positioner med 20 rader: 10/19 10/19 och 9/19 11/19. Jag behövde inte båda de 20 raduppsättningarna i minnet på en gång; de kunde användas en i taget genom att spara de bästa poängen med tanke på bara nya rader i den första gruppen för alla 9/19 10/19 positioner och sedan se om någon förbättring kunde göras i poängen med en ny rad i den andra grupp. De två buffertarna tar bara 16 GB.
Då insåg jag att jag kunde dela upp raderna i mer än två grupper. Genom att använda 6 grupper kunde jag klippa det RAM som behövdes till bara 426 MB. En ytterligare skärning med symmetri (se nedan) gjorde att den passade. Naturligtvis, för att hitta till exempel poängen för 4/8 3/6 3/6 3/6 3/6 3/6 positionerna, måste programmet läsa i sex olika uppsättningar poäng med 20 rader – vardera med en rad till i en av de sex grupperna.
Symmetri
3×5-spelet är symmetriskt vertikalt och horisontellt, så genom att utnyttja symmetrin kunde jag dela ut rymdbehovet med 4 (faktiskt med 3 i min slutliga implementering). Paul Stevens rapporterade ett fel i testet för symmetri över en diagonal på en fyrkantig tavla.
För att beräkna poängen för en position tittar programmet på de tidigare beräknade poängen för positionerna som är resultatet av att lägga till en rad till. Att lägga till en rad kan dock resultera i en position som måste transformeras symmetriskt innan dess poäng kan hittas. För att säkerställa att poäng för positionen som är resultatet av den symmetriska omvandlingen är omedelbart tillgänglig, är det nödvändigt att transformationen kartlägger några linjer i samma grupp. På det sättet förblir antalet rader i varje grupp densamma efter transformation.
Innan programmet tilldelar rader till grupper letar det först efter rader som är associerade med varandra genom symmetrisk transformation. I spelet 3×5 finns det sju uppsättningar med 4 rader och fem uppsättningar med 2 rader som är associerade. Programmet tilldelar sedan raduppsättningarna till grupperna. För 3×5-spelet med 256 MB RAM-resultat resulterar sex grupper (vardera med två uppsättningar linjer) av storlekarna 8 6 6 6 6 6.
För att avgöra om en position ska transformeras symmetriskt, ser programmet endast på raderna i den första gruppen. Under installationsfasen skannar programmet igenom alla möjliga linjekonfigurationer i den första gruppen av rader. För varje konfiguration tillämpar den vertikal reflektion, horisontell reflektion och reflektion genom ursprungstransformationerna. Om en av dessa transformationer resulterar i ett tal för tillståndet för raderna i gruppen som är numeriskt mindre än antalet för de ursprungliga raderna, så ingår (1) konfigurationen INTE i den länkade konfigurationslistan med en givet antal rader och (2) information sparas om vilken symmetrisk transformation som behöver användas för att få en position vars poäng har beräknats – det vill sägaför att komma till motsvarande konfiguration med det lägsta numeriska värdet för dess linjer.
Även om endast den första gruppen används för att se om en transformation ska göras, när transformationen är klar påverkar den linjerna i alla grupper.
Spara diskutrymme
Poängen för positioner med ett visst antal rader i varje grupp lagras i en enda diskfil. Till exempel lagras poängen för 4/8 3/6 4/6 2/6 3/6 3/6 positionerna i fil:
\ Boxes \ 3×5 \ 19 \ 4 \ 3 \ 4 \ 2 \ 3.bin
The snedstreck separerade kapslade mappnamn. 3×5 är namnet på spelet som analyseras. 19 är det totala antalet rader i positionen. Resten av mappnamnen och filnamnet kommer från till antalet rader i grupperna. Antalet rader i den sista gruppen används inte eftersom det fixeras av de andra siffrorna. .Bin betyder att detta är en binär fil – dess innehåll kan inte visas direkt. Kapslade mappar används eftersom Windows behandlar mappar med ett stort antal filer mycket långsamt.
Symmetriska omvandlingar minskar det nödvändiga diskutrymmet från 256 GB till 85 GB. Det är dock inte nödvändigt att behålla hela analysresultaten. Så snart programmet gjordes med positioner med 19 rader kunde resultaten för positioner med 20 rader tas bort. Med bara 16 GB ledigt diskutrymme tillgängligt behåller programmet resultaten för positioner med 15 eller färre rader. Detta resulterar i en “öppningsbok” för spelet 3×5.
Att lagra bara resultaten för 20 radpositioner och 19 radpositioner tar dock fortfarande 22 GB. Detta löses genom att ta bort delar av de 20 raderna positionsfiler eftersom de inte längre behövs för ytterligare beräkning av poäng för 19 rader. När programmet går igenom alla möjliga kombinationer av rader för de grupper som lägger till upp till 19 rader, minskar räkningen för den första gruppen av rader aldrig. Således, när räkningen för den första gruppen av rader flyttas från 0 till 1, kan till exempel alla filer som börjar med \ Boxes \ 3×5 \ 20 \ 0 \ raderas. Med denna förändring passar analysen i de tillgängliga 16 GB.
Kedjor
Vid denna tidpunkt var programmet fortfarande otillräckligt för att lösa 5×5-problemen i kapitel 12 i The Dots-and-Boxes Game av Elwyn Berlekamp (AK Peters, 2000) . Om datorer fortsätter att fördubbla sin kapacitet var 18: e månad, borde vi kunna analysera hela 5×5-spelet 2034 eftersom det har 22 fler linjer än 3×5-spelet, som analyserades 2001. Programmet kan nu hantera positioner med upp till 36 öppna linjer där positionen inte har någon symmetri och 14 Gb diskutrymme är tillgängligt. Det innebar att bara 5×5-positionerna med 24 eller fler linjer (av de 60) kunde tacklas. Inget av kapitel 12-problemen hade så många rader.
En kedja är en sträng av en eller flera lådor med två sidor fyllda. Jag antar att när en av spelarna väl tagit en linje i en kedja, involverar åtminstone en av de bästa spellinjerna alla resten av raderna i kedjan fylls i, av en spelare eller den andra, innan några rader någon annanstans fylls i. Varje uppsättning kedjelinjer representeras av en enda “pseudolinje”. Positionsrepresentationen i programmet har bara en bit som säger om kedjan har fyllts helt eller inte eller fortfarande är tom. Här är till exempel positionen för problem 12.18 (före den streckade linjen):
+ + +. + + +
| . |
| . |
| . |
+ +. +. + + +
| . | .
| . | ....
| . |
+ +. + ----- + ----- + ----- +
| . |
| . | ..........
| . | .
+ +. +. + ----- +. +
| | .
| .... | ....
| . |
+ + +. +. + ----- +
| .
| ....
|
+ + + ----- + + +
Prickarna markerar kedjorna som var och en representeras av en enda pseudolinje. Av de 60 raderna är 15 fyllda, 30 är tomma och 15 är involverade i 6 kedjor. Positionerna som kan uppstå från denna startposition representeras av 36 bitar – 30 för de tomma linjerna och 6 för de 6 kedjorna. Således ligger denna position knappt inom programmets nuvarande kapacitet.
I många av de positioner som härrör från en given startposition har initiala kedjor blivit en del av längre kedjor. Programmet ändrar inte positionrepresentationsschemat i denna situation. Pseudolinjerna representerar bara de initiala kedjorna. Detta beror på att positionsrepresentationen används som en “adress” för att komma åt de tidigare beräknade poängen.
Samtidigt som man utvärderar om att flytta in i en initial kedja är en bra idé för spelaren på resande fot, har programmet tillgång till nettopoängen med bästa spel för framtida rutor för spelaren på språng efter att hela den ursprungliga kedjan har fyllts. Programmet måste sedan kontrollera rutorna runt kedjan för att se vilken spelare som får första chansen att ta lådorna i kedjan, för att se om den spelaren skulle tjäna på att offra för att undvika att ta med sig när kedjan är fylld , och för att kontrollera om kedjan har förlängts eller till och med gjort en del av en slinga.
Om den initiala kedjan har en 3-sidig låda på vardera sidan strax bortom kedjan, kan spelaren på resande fot flytta in i kedjan med en fångst och har möjlighet att ta lådorna i kedjan. Annars är det den andra spelaren som har alternativet i kedjan. Jag ringer personen med möjlighet att ta rutorna i kedjan, “kedjespelaren”.
Om den initiala kedjan har förlängts tillräckligt så att kedjespelaren kan göra ett offer senare, återspeglar poängen efter att kedjan är helt fylld redan detta alternativ och kedjespelaren tar alla rutorna i den ursprungliga kedjan. Annars kontrollerar programmet om det finns tillräckligt med utrymme för ett offer förutsatt att den bästa flytten in i kedjan av spelaren som ursprungligen var på språng och tittar på den initiala kedjan och eventuella tillägg. Om det fortfarande inte finns tillräckligt med utrymme för ett offer tar kedjespelaren alla lådor. I annat fall kontrollerar programmet om ett offer är lönsamt och i så fall utvärderar det att gå in i kedjan för spelaren som ursprungligen är på språng förutsatt att kedjespelaren gör offret.
Sista dragstraff
Programmet gör det möjligt att tillämpa en straff på poängen för spelaren som gör det sista draget. Om det här straffet är tillräckligt stort kommer de drag som väljs som bäst att vara desamma som de som valts av nimstring-analys. Till exempel har jag analyserat problem 11.16 med påföljder av ökande omfattning . Programmet tillåter inte brottmål eftersom de inte ger ytterligare information:
- Om du kör analysen med två olika straffar kan poängen för ett drag inte förändras med mer än minus minus skillnaden i straffarna.
- För på varandra följande heltalstraffar resulterar en analys i alla jämna heltal och den andra resulterar i alla udda heltal.
- Således för på varandra följande heltalsstraffar ändras poängen alltid med +1 eller -1 … det högsta möjliga.
- Därför kan du få poängen för varje bråkstraff genom att interpolera mellan poängen för intilliggande heltal.
Loony Moves
Den slutliga versionen av programmet inkluderar loony flyttanalys. I utgången efterföljs en poäng av v om spelare A måste göra nästa loony drag eller av ^ om spelare B måste. Om ingen spelare måste göra ett loony drag används inget suffix. Under analysen används två bitar av byten som används för att hålla poängen för att hålla det looniga tillståndet i rörelsen. Detta lämnar bara 6 bitar för poängen. Således kan endast poäng från -32 till +31 lagras. Detta gör den loony flyttanalysversionen av programmet opålitlig på brädor större än 5 av 6. Därför håller jag en version tillgänglig som inte gör loony move-analys för användning med större brädor.
För att hitta loony rörelser på en rimlig mängd datortid gör programmet en loony bonuscheck när det är möjligt att fånga en låda. Om rutan på den andra sidan av linjen som övervägs har exakt två andra sidor redan har fyllts i, drar programmet slutsatsen att motståndarens tidigare drag var trögt.
Hörn
William Fraser skrev: “Tar du hänsyn till det faktum att [ab] och [ba] hänvisar till motsvarande länkar? Således (om du placerar de åtta hörnlänkarna i den sista 8-radsgruppen) kan du bara lagra 3 ^ 4 = 81 poster istället för 2 ^ 8 = 256. Detta skulle vara helt oberoende av rotation / reflektion. Det minskar diskanvändningen med 75% och minnesanvändningen med i genomsnitt 75%. ”
Jag implementerade detta förslag, vilket gjorde det möjligt att analysera 4×4-spelet.