Hvor meget betyder én fri celle?

Hvorfor vi målte det

Da vi testede 10.000 kabaler med en solver, stod vi med et resultat, vi ikke havde regnet med: Otte kabale, varianten med de strengeste byggeregler, var lettere at løse end FreeCell. Mindst 99,90 % af udlæggene i Otte kabale kunne vindes mod mindst 99,76 % i FreeCell. Vores bedste forklaring var, at forskellen ikke lå i reglerne for, hvordan man bygger, men i noget langt mere jordnært: Otte kabale har otte frie celler, FreeCell har fire.

Men en forklaring, man ikke har efterprøvet, er bare en formodning. De to varianter adskiller sig nemlig på flere punkter end cellerne, så vi kunne ikke afgøre spørgsmålet ved at sammenligne dem direkte. I stedet gjorde vi det, man gør i et ordentligt forsøg: Vi ændrede én ting ad gangen og lod alt andet stå urørt.

Sådan gjorde vi

Vi tog vores FreeCell-motor og lod alle regler stå, som de er: fire fundamenter, otte kolonner, byg ned i skiftende farve, flyt ét kort ad gangen. Det eneste, vi skruede på, var antallet af frie celler, fra én til otte. For hvert celletal forsøgte solveren at løse de samme 1.000 udlæg, valgt deterministisk med formlen:

seed = round(i × 1000000 / 1001), hvor i går fra 1 til 1000

At det er de samme 1.000 udlæg hele vejen, er hele pointen. Hvis andelen af løste kabaler ændrer sig, kan det ikke skyldes, at det ene hold udlæg var heldigere end det andet. Den eneste forskel er cellerne.

Solveren fik samme søgebudget pr. udlæg som i hovedstudiet: 1,5 millioner stillinger. Fandt den ingen løsning inden for budgettet, tæller udlægget som uafgjort, ikke som uløseligt. Alle procenter herunder er derfor nedre grænser; det vender vi tilbage til.

Resultatet

Kurven fortæller tre ting, og de er værd at tage én ad gangen.

Springet sker mellem to og tre celler

Med én celle kunne solveren kun løse 172 af de 1.000 kabaler. Med to celler blev det til 765. Men det store spring kommer med den tredje celle: 984 af 1.000, og dermed er spillet reelt forvandlet fra et, man som oftest taber, til et, der stort set altid kan vindes. Den tredje celle er den dyreste plads i hele spillet.

Den fjerde celle er en forsikring

FreeCell spilles med fire celler, og vores måling antyder hvorfor: Den fjerde celle løfter andelen fra mindst 98,4 % til mindst 99,5 % og halverer samtidig solverens arbejde endnu en gang. Den gør ikke spillet trivielt, men den fjerner de fleste af de udlæg, der ellers ville ende som rene tålmodighedsprøver. Med andre ord ligger det klassiske FreeCell lige på det sted, hvor spillet er næsten altid vindbart, men stadig kræver, at man tænker sig om.

Derefter flader kurven ud

Fra fire celler og op sker der næsten ingenting med vindchancen: 99,5, 99,5, 99,8, 99,9, 99,9. Til gengæld sker der noget markant med, hvor svært det er at finde løsningen. Medianen af solverens gennemsøgte stillinger falder fra 23.367 ved én celle til 72 ved otte. Spillet bliver ikke bare mere vindbart af flere celler; det bliver også langt lettere at regne på. Det er i øvrigt præcis det mønster, vi så i hovedstudiet, hvor Otte kabale med sine otte celler var markant billigere for solveren at gennemsøge end FreeCell.

Hvad en fri celle egentlig gør

For den, der ikke har FreeCell siddende i fingrene: En fri celle er en tom plads ved siden af spillet, hvor ét kort kan parkeres midlertidigt. Det lyder uskyldigt, men næsten alt, hvad man foretager sig i spillet, går gennem cellerne. Skal man have fat i et kort, der ligger begravet under tre andre, skal de tre andre hen et sted, og cellerne er ofte det eneste sted, der er.

Cellerne afgør også, hvor meget man kan flytte ad gangen. Motoren flytter ét kort ad gangen, så en pæn sekvens på fem kort kan kun vandre samlet, hvis der er fire ledige pladser at mellemlande på. Hver optaget celle gør altså ikke bare én plads mindre; den skærer et helt lag af de træk, der overhovedet er mulige. Det er derfor, kurven reagerer så voldsomt: Antallet af lovlige veje gennem spillet vokser eksplosivt med hver ekstra celle, og med én celle er nettet af veje så tyndt, at de fleste udlæg simpelthen ikke har en gennemgang.

Deraf følger også et par råd, som tallene nu bakker op:

Først: Cellerne er ikke opbevaring, de er et værktøj. Et kort, der parkeres uden en plan for, hvordan det kommer ned igen, svarer til frivilligt at spille varianten et trin til venstre på kurven, og forskellen mellem fire og tre celler er målbar: fra 5 uafgjorte pr. 1.000 til 16. Dernæst: En tom kolonne virker som en ekstra celle, bare bedre, for den kan tage imod en hel sekvens. Den, der rydder en kolonne tidligt og holder den ryddet, spiller reelt med fem celler og har dermed købt sig kurvens sikkerhedsmargin. Flere af den slags råd, med tal bag, står i vores strategigennemgang.

Forbeholdene, før nogen citerer tallene

Solverens søgning er ikke udtømmende. Når den giver op på et udlæg, ved vi ikke, om udlægget er uløseligt, eller om løsningen bare lå uden for budgettet. Alle procenter i tabellen er derfor nedre grænser: mindst så mange kan vindes.

Det forbehold vejer tungest i venstre side af kurven. Ved én og to celler er spillet så trangt, at mange udlæg ramte søgebudgettet, og de reelle andele ligger derfor formentlig et stykke over de 17,2 % og 76,5 %. I grafikken er de to punkter tegnet hule netop af den grund. Kurvens form, det stejle spring efterfulgt af udfladningen, står dog ikke til diskussion; den kan kun blive endnu stejlere, hvis de sande tal ved få celler er højere.

Vi siger med vilje ikke "vindchance" om disse tal. De beskriver, hvor stor en andel af udlæggene der overhovedet kan vindes med perfekt spil, ikke hvor ofte et menneske vinder. De to tal er meget forskellige, og forskellen er forklaret i vores gennemgang af vindchancer.

Hvad det betyder for hovedfundet

Tilbage til det spørgsmål, der startede det hele: Hvorfor er Otte kabale lettere at løse end FreeCell, når reglerne er strengere? I Otte kabale skal man bygge i samme kulør, og en tom kolonne må kun fyldes med en konge. Begge dele burde gøre spillet sværere.

Denne måling giver svaret en helt anden vægt end før. Da vi ændrede antallet af celler og intet andet, flyttede andelen af løselige udlæg sig fra 17,2 % til 99,9 %. Cellerne alene kan altså flytte resultatet mere end nogen byggeregel, vi kender. At Otte kabale med otte celler slår FreeCell med fire, selv om byggereglerne trækker den anden vej, er dermed ikke længere overraskende. De frie celler er spillets arbejdshukommelse, og arbejdshukommelse slår regelstramninger.

Man kan prøve det selv: FreeCell og Otte kabale kan begge spilles i browseren her på siden, uden login og uden reklamer, og med spilnumre, så et bestemt udlæg kan findes igen.

Sådan genskaber man målingen

Studiet er bygget til at kunne gentages uden vores filer. De 1.000 udlæg er givet ved seed-formlen ovenfor, blandingen af kort ud fra et seed er beskrevet i metodeafsnittet på datasiden, og søgebudgettet er 1,5 millioner stillinger pr. udlæg. Enhver, der skriver sin egen solver efter den opskrift, bør lande på de samme nedre grænser eller over; en bedre solver kan kun løse flere af de uafgjorte udlæg, ikke færre. Finder nogen en løsning på et udlæg, vi har som uafgjort, hører vi meget gerne om det, for så skal vores tal rettes op. Det er sådan, nedre grænser skal fungere: De tåler at blive udfordret, og de kan kun flytte sig i én retning.