Nyt studie viser, hvor svært Kalaha kan blive på større brætter

Hvor svært kan Kalaha blive, hvis hver spiller får flere end seks små skåle? I et forskningsmanuskript offentliggjort den 12. november viser Ethan Dickey og Ethan Mader, hvor krævende det kan være at afgøre, om en spiller kan fremtvinge en sejr, når antallet af skåle kan variere.

Forskerne tager udgangspunkt i en given stilling, hvor kuglerne kan være ujævnt fordelt. Spørgsmålet er, om den ene spiller kan slutte med flere kugler end den anden uanset modstanderens træk. Uafgjort tæller ikke som en sejr. Forskningsmanuskriptet på arXiv

Kort fortalt

• Resultatet gælder givne stillinger på brætter med varierende antal skåle.
• Beviset gælder med to almindelige fangstregler, både med og uden ekstra ture.
• Tidligere computeranalyser fandt udfaldet for bestemte åbninger på standardbrætter. Den nye undersøgelse handler om, hvordan sværhedsgraden vokser.

Den sidste kugle ændrer mulighederne

På et almindeligt bræt har hver spiller seks små skåle og en større skål til point. På din tur tømmer du en af dine skåle og fordeler kuglerne én ad gangen. Den sidste kugle kan give dig en ekstra tur eller lade dig tage kugler fra modstanderen. Playiros danske Kalaha-regler forklarer, hvornår de to regler gælder.

I forskernes model har brættet stadig to rækker og en pointskål til hver spiller. Antallet af små skåle kan variere. Når en ekstra kugle ender i en skål, flytter den slutpunktet for næste træk fra den skål. Det ændrer, hvilke kugler en spiller kan fange senere. Beviset gælder også, når begge pointskåle er tomme i udgangsstillingen.

Hvad forskerne har regnet på

Forskerne kalder problemet PSPACE-komplet, når antallet af kugler i en skål skrives med ét tegn pr. kugle. Det hører dermed til blandt de sværeste problemer i en klasse, hvor den mængde arbejdshukommelse, en computer skal bruge, højst vokser polynomisk med størrelsen på beskrivelsen. Klassificeringen siger noget om de vanskeligste stillinger. Nogle stillinger har stadig et enkelt svar.

Tidligere har computerprogrammer fundet resultatet for bestemte åbningsstillinger med seks skåle pr. spiller. Det gælder blandt andet et bræt med fire kugler i hver skål. Den nye undersøgelse tillader forskellige antal kugler fra skål til skål. Forskerne lader spørgsmålet stå åbent for den familie af åbninger, hvor alle skåle skal rumme lige mange kugler. MathWorlds gennemgang af Kalah