WisFaq!

Kat en muis

Vier witte speelstukken (de kat) worden aan de ene kant van het schaakbord geplaatst, en een zwart speelstuk (de muis) wordt aan de overzijde geplaatst. Het spel wordt gespeeld volgens de volgende regels:

Zwart wint als het de overkant bereikt (de muis ontsnapt).
Wit wint als het zwart zodanig blokkeert dat zwart geen legale zet meer kan doen (de kat heeft de muis gevangen).
Het is alleen toegestaan om de speelstukken diagonaal te verzetten (met stapgrootte 1).
Wit mag alleen (schuin) vooruit zetten.
Zwart mag zowel vooruit als achteruit.
Afwisselend mogen zwart en wit een zet doen (zwart mag beginnen).
De Vraag: Is dit spel berekenbaar (ofwel: kun je op voorhand al beslissen wie er kan winnen, ongeacht de zetten die de ander zal doen om dat te voorkomen)

Samantha
7-7-2003

Antwoord

Het maximaal aantal zetten in dit spel is hoe dan ook eindig en lijkt me vrij beperkt. Schrijf er eens een programmaatje voor dat het minimax-zoekalgoritme gebruikt in combinatie met alfa-beta-snoeien (Engels: "alpha-beta pruning"). Zoek eens op google wat deze termen precies betekenen als ze je niks zeggen.

PS: 1ste graad ASO-TSO-BSO? Yeah right

cl
7-7-2003