Van Maanen Hans van Maanen
klikklikklikklik

Hoogste score tot nu toe!

Een lijst met priemgetallen van 2 tot 20000 en een handig programmaatje dat direct uitrekent wat voor dag 3 juli 2091 is -- wat valt er verder nog te programmeren op de computer? Het is geen gebrek aan techniek, maar gebrek aan stof die ertoe leidt dat de meeste mensen hun computer ten slotte toch slechts als veredelde tekstverwerker gebruiken: er valt niets leuks te doen.
In dit boekje worden zij verder geholpen met een twintigtal spelletjes die iedereen kan programmeren. Veel meer dan basiskennis van een programmeertaal is niet nodig; bij mogelijke struikelblokken wordt assistentie verleend.
En de spelletjes zijn daarna nog leuk om te spelen ook.

Uitgeverij Aramith, Bloemendaal
Eerste druk 1993.
Uitverkocht.
ISBN 90-6834-123-5


Inhoud

Inleiding

Vijftien
Rotor
Carré
Berg en dal

M/V
Bozebol
Moordenaars
Onbenul
007
Autoweg
Stampede
Racen

Lucifersspel
37, 47, 57
Nim
Hip
Kim
Schateiland

Verdere suggesties
Biblografie
Register


Hip

Mensen die ‘hip’ zijn, hebben een hekel aan ‘squares’. De bedoeling van Hip is dan ook, ervoor te zorgen geen vierkanten te maken. De woordspeling en het spel komen van Martin Gardner, die het publiceerde in zijn boek New mathematical diversions from Scientific American.

Het speelbord van Hip is zeven bij zeven en bij het begin van het spel leeg. De ene speler heeft witte, de andere grijze stenen ter beschikking. Om beurten leggen zij een steen op het bord, en daarbij zorgen ze ervoor dat geen van hun eigen stenen in een vierkant komt te liggen. Wie dat als eerste toch overkomt, is ‘square’ en heeft verloren.

De figuur hierboven laat enkele mogelijke vierkanten zien. Gardner ontwierp het spel eerst voor een bord van zes bij zes, maar dat is makkelijk te winnen door de tweede speler. Van het bord van zeven bij zeven is nog niet bekend wie in het voordeel is. Remise wordt het in geen geval.
Het probleem van het spelen tegen een menselijke tegenstander is, dat hij het verschrikkelijk flauw kan maken door geen enkel risico te nemen: hij stelt zijn stenen gewoon zo veel mogelijk langs de randen op. Het aardige van het spelen tegen de computer is, dat (u ervoor kunt zorgen dat) hij dat niet zal doen. Bovendien kan hij ervoor zorgen dat u die tactiek ook niet kunt gebruiken door eerst als een soort scheidsrechter random een aantal stenen van elke speler neer te leggen (uiteraard zodanig dat nergens al een vierkant is gevormd), en pas daarna de rol van tegenstander aan te nemen. Doordat er al stenen liggen, ontbrandt de strijd direct en kunt u niet eerst veilige rijen maken.

De figuur toont een stand voor het spel zoals ik het heb geschreven voor de Apple Macintosh en dat u kunt ophalen.
Twee problemen doemen direct op: hoe herkent de computer vierkanten, maar vooral, hoe bepaalt hij zijn zet? Het meest voor de hand ligt het, om de computer een willekeurig vrij veld te laten kiezen en alleen te controleren of hij daarmee geen vierkant maakt. Dat kan, en het is verontrustend om te zien hoe goed hij dan toch nog speelt -- de kwaliteit van veel spelletjes kan op deze manier worden getest: hoe makkelijk wint de computer als hij random mag zetten -- wij willen echter dat hij het iets beter doet. Laten we zeggen dat hij in ieder geval geen eigen vierkanten maakt, en in principe ook niet gaat staan op velden waar de tegenstander een vierkant zou kunnen maken. Hogere eisen stellen we later.

Hints & tips
De hoekpunten van een vierkant zullen we aanduiden met linksonder en rechtsonder (x1,y1) en (x2,y2), en linksboven en rechtsboven (x3,y3) en (x4,y4). Het is natuurlijk direct te zien dat er een vierkant wordt gevormd als x1 = x3, y1 = y2, x2 = x4 en y3 = y4. Maar hoe zit het met scheve vierkanten?
Het is ondoenlijk om alle mogelijke vierkanten in een tabel te zetten en daarin op te zoeken of vier gegeven punten een vierkant vormen. In een vierkant van zeven bij zeven zijn meer dan vierhonderd kleinere vierkanten te tekenen.
We zullen dus moeten rekenen. Daartoe maken we gebruik van het feit dat twee punten op het speelveld een vierkant definiëren. Als we de hoekpunten (x1,y1) en (x2,y2) als vaste punten nemen, dan voldoet het derde hoekpunt aan x3 = x1 + (y1-y2) en y3 = y1 + (x2-x1), en het vierde hoekpunt aan x4 = x2 + (y1-y2) en y4 = y2 + (x1-y2). Er is nog een vierkant mogelijk, maar daarover straks.
Om te zien of vier stenen in een vierkant liggen, beginnen we linksonder, x1 = 1, y1 = 1, en ‘scannen’ vervolgens het complete bord. We bekijken telkens een hokje verder, x1 = x1 + 1, tot we aan de rechterrand komen, dan gaan we naar de volgende regel: x1 = 1, y1 = y1 + 1. Als y1 = 8 is, hebben we alle hokjes gehad.
Zodra op een van de gescande velden een steen ligt van de speler ligt die we controleren, dus h(x1,y1) = speler, zetten we x2 = x1 + 1, y2 = y1. Daarmee hebben we (x1,y1) en (x2,y2) gevonden, is het vierkant gedefinieerd, en kunnen we kijken of op de velden (x3,y3) en (x4,y4) stenen liggen, dus of die ook de waarde speler hebben. De procedure zoek1e heeft een ‘parameter’ speler: die krijgt de waarde 1 of 2 mee, al naar gelang de mens of de computer gecontroleerd wordt.

procedure zoek1e(speler)
  x1 = 1; y1 = 1
  while y1 < 8
    if h(x1, y1) = speler then
      zoek2e(speler)
    else
      x1 = x1 + 1
      if x1 = 8 then
      x1 = 1; y1 = y1 + 1
  endwhile
endprocedure

procedure zoek2e(speler)
  x2 = x1 + 1; y2 = y1
  if x2 = 8 then
    x2 = 1; y2 = y2 + 1
  while y2 < 8
    if h(x2, y2) = speler then
      zoek3e4e(speler)
    else
      x2 = x2 + 1
      if x2 = 8 then
        x2 = 1; y2 = y2 + 1
  endwhile
endprocedure

Het ophogen van de x en de y kan ook nog in een aparte procedure worden samengevat.
De coördinaten van de derde en de vierde steen laten zich nu eenvoudig berekenen volgens de gegeven formules. Nadat met de functie opbord is gecontroleerd of de berekende waarden binnen het speelveld liggen (dus groter dan nul en kleiner dan acht zijn), kunnen we gaan kijken of er op beide velden een steen van speler ligt:

procedure zoek3e4e(sp)
  x3 = x1 + (y1 -- y2)
  y3 = y1 + (x2 -- x1)
  x4 = x2 + (y1 -- y2)
  y4 = y2 + (x2 -- x1)
  if opbord(x3, y3, x4, y4) then
  beginif
    if h(x3, y3) = sp and h(x4, y4) = sp then
      vierkant = true
    else
      vierkant = false
  endif
endprocedure

Het gaat overigens sneller om alleen de laatst geplaatste steen te controleren, dus x1 = 1 en y1 = 1 te stellen en x2 en y2 de coördinaten van de geplaatste steen te geven (anders moet de computer ook de andere kant op kijken), maar wat te doen met een zet op (1,1)? Misschien iets voor versie 2.0 om uit te zoeken.
Belangrijker is, dat de procedure zoek3e4e een bepaald soort vierkant kan missen. Als de eerste twee stenen verticaal liggen, bijvoorbeeld x1 = 3, y1 = 1 en x2 = 3, y2 = 3, dan kijkt de computer volgens de formule alleen naar (1,1) en (1,3). Maar er zouden ook twee stenen kunnen liggen op (5,1) en (5,3), en die vormen ook een vierkant. Met andere woorden:

if x1 = x2 then
beginif
  x3 = x1 -- (y1 -- y2)
  y3 = y1 -- (x2 -- x1)
  x4 = x2 -- (y1 -- y2)
  y4 = y2 -- (x2 -- x1)
endif

waarna er eenmaal extra gecontroleerd moet worden met if opbord(x3,y3,x4,y4) then begin enzovoort.
Het eerste deel van het probleem, het onderkennen van vierkanten, is nu opgelost. Het tonen van de aanstootgevende stenen door een vierkantje of een kleurtje zal geen moeilijkheden opleveren.
Er zijn natuurlijk nog wel andere manieren om vierkanten te vinden, maar deze biedt het voordeel dat nu ook het tweede deel van het probleem, het spelen door de computer, dicht bij een oplossing is.
De velden van het speelbord kunnen op het ogenblik drie waarden aannemen: h(x,y) = 0 betekent dat het veld nog leeg is, h(x,y) = 1 dat er een steen van de mens staat, en h(x,y) = 2 dat er een steen van de computer ligt.
Om de computer zijn beste zet te laten kiezen, passen we een bekende en veelgebruikte techniek toe. We breiden de schaal naar onder uit, en geven een hok de waarde -1 als een steen daarop een vierkant voor de mens volmaakt, en -2 als een steen daar fataal is voor de computer. Voor de computer ziet het spel van de figuur, met alvast acht stenen neergelegd, er dus anders uit dan voor de mens, zoals de figuur laat zien. Een veld dat voor beide spelers fataal is, heeft uiteraard de waarde -3.

Voordat de computer zet, kijkt hij eerst wat de hoogst beschikbare waarde van alle lege hokjes op het bord is. Als de computer dan een steen legt in een hokje met de hoogste waarde, dan heeft hij de best mogelijke zet gedaan. Als er alleen nog hokjes met de waarde --3 of --2 zijn, heeft hij verloren, desnoods kiest hij voor --1, en anders zet hij in een hokje met waarde 0. Zo vermijdt hij zo lang mogelijk zwakke zetten.

max = -3
for j = 1 to 7
  for i = 1 to 7
    if h(i, j) < 1 and h(i, j) > max then
      max = h(i, j)
  next i
next j
repeat
  x = random(1, 7)
  y = random(1, 7)
until h(x, y) = max
hok(x, y) = 2

Na elke zet maakt de computer weer de stand op, maar nu kent hij ook negatieve waarden aan hokjes toe. Het eind van de procedure zoek3e4e wordt:

if h(x3, y3) = sp and h(x4, y4) < 1 then
  h(x4, y4) = h(x4, y4) -- sp
if h(x4, y4) = sp and h(x3, y3) < 1 then
  h(x3, y3) = h(x3,y3) -- sp
if h(x4, y4) = sp and h(x3, y3) = sp then
  vierkant = true
else
  vierkant = false

Er moet nog een voorziening komen dat de waarde van h niet onder de -3 kan zakken, maar dat is u verder wel toevertrouwd.
Merk op dat we in feite al weten of vierkant de waarde true zal krijgen voordat we de zoekprocedure ingaan: dan is er namelijk op -1 of -2 gezet. Toch is het nuttig om er doorheen te gaan, want we willen ook weten wat de fatale stenen zijn om ze te kunnen aangeven voor de speler -- die moet natuurlijk niet te horen krijgen dat hij heeft verloren zonder dat het vierkant getoond wordt.
Als de computer acht stenen van tevoren moet neerleggen, hoeft hij alleen maar met de waarden 1 en 2 (alletwee acht keer) een steen neer te leggen en te controleren tot er een legaal bord uitkomt.
Daarmee zijn we waar we wezen willen.

Versie 2.0
Maar het kan, als we er zijn, nog beter, en wel op twee manieren.
De computer hoeft niet te wachten tot er al drie stenen van het vierkant liggen voor hij de laatste als gevaarlijk herkent. Hij kan ook met twee stenen al voorzichtig worden, en h(x3,y3) en h(x4,y4) een negatieve tussenwaarde geven -- bijvoorbeeld -1,5 voor zichzelf en -0,5 voor velden van de tegenstander.
Een verdere mogelijkheid is, de computer na het bepalen van het maximum niet willekeurig te laten kiezen, maar hem ook in dit stadium nog te laten nadenken. Hij zou bijvoorbeeld van elke mogelijke zet kunnen bepalen, hoeveel -2’s die oplevert: de zet met de minste -2’s levert het minste gevaar. En dan kan hij ook nog wel uitzoeken hoe veel velden de waarde -1,5 krijgen. Ik garandeer u dat u dan niet meer kunt winnen van de computer.

De bourgeois-variant van Hip ligt voor de hand: om beurten leggen de spelers een damsteen op het bord, en ze proberen steeds vierkanten te maken en tegelijkertijd de tegenstander te beletten vierkanten te vormen. De vierkanten mogen weer scheef op het bord liggen, en een steen mag aan meer dan een vierkant meedoen. Winnaar is degeen die aan het eind de meeste vierkanten heeft (de computer houdt de stand bij en weet ook wanneer er geen vierkanten meer te vormen zijn). Dit spel heet in Frankrijk Grille, in Engeland Squares en bij ons Vierkant.
U kunt ook eens proberen of het spel zich ook in een kubus laat spelen.
In plaats van vierkanten te verbieden, kan men ook spelen met de afspraak dat er geen drie stenen op een rechte lijn -- horizontaal noch verticaal noch diagonaal -- mogen liggen. Dan heet het spel Trianon. Een voorbeeld op een veld van vijf bij vijf geeft de figuur; wit aan zet verliest. Bij het programmeren kunt u van dezelfde principes gebruikmaken als bij Hip.

Of men kan afspreken dat er juist zoveel mogelijk drietallen moeten worden gevormd -- dan tellen vier op een rij niet voor twee drietallen, maar mag een steen wel deel uitmaken van rijen van drie in verschillende richtingen. Verdere varianten laten zich raden.

Terug naar boeken