Opdracht 5: Eindopdracht ALDAT.

© Harry Broeders.

Kies één van de onderstaande opdrachten of bedenk zelf een opdracht in overleg met de docent. Deze eindopdracht is je afsluitende toets voor de cursus ALDAT. Deze opdracht wordt ook beoordeeld op originaliteit.

Je moet het volgende opleveren:

Je moet dit uiterlijk op de vrijdag van de eerste toetsweek inleveren. Je krijgt dan voor de herkansingsweek het resultaat te horen. Als je niet tevreden bent met het resultaat kun je op de vrijdag van de herkansingsweek een verbeterde versie inleveren. Natuurlijk is het, net zo als bij schriftelijke toetsen, mogelijk om alleen met de herkansing mee te doen. In dat geval lever je het werk op de vrijdag van de herkansingsweek in.

Alle opdrachten gaan over het uitbreiden of aanpassen van het in les 5 besproken Tic-Tac-Toe programma uit hoofdstuk 8.7 en 11.2 van het boek van Weiss. Je kunt de door mij aangepaste versies als uitgangspunt gebruiken:

Opdracht 5a. Verbeteren van het TTT algoritme.

Bij deze opgave kun je jezelf verder verdiepen in het toegepaste algoritme en de gebruikte datastructuren. Het toegepaste minimax algoritme  met alpha-beta pruning en transposition table kan nog verder worden verbeterd:

  • Als de computer gewonnen staat neemt hij niet altijd de kortste weg naar de winst (uiteindelijk wint hij natuurlijk wel). Zie ook opgave 11.8 pagina 407 van Weiss. Voorbeeld: 
  • Enter row and col (starts at 0): 0 0
---
x


---
Computer plays: ROW = 1 COL = 1
---
x
 o

---
Enter row and col (starts at 0): 2 2
---
x
 o
  x
---
Computer plays: ROW = 0 COL = 1
---
xo
 o
  x
---
Enter row and col (starts at 0): 0 2
---
xox
 o
  x
---
Computer plays: ROW = 1 COL = 2
---
xox
 oo
  x
---

  • Als laatste zet was ROW = 2 COL = 1 sneller geweest!

  • Als de computer mag beginnen dan kiest de computer een willekeurige beginzet. Als de gebruiker mag beginnen dan volgt op een bepaalde beginzet van de gebruiker altijd dezelfde zet van de computer. Bij het uitvoeren van het minimax algoritme kiest de computer altijd hetzelfde maximum of minimum. Als je deze keuze random maakt speelt de computer met meer variatie.
  • Het speelbord waarop Tic-Tac-Toe gespeeld wordt is symmetrisch. Door het bord te draaien of te spiegelen veranderd de stelling niet. Als je stellingen, die niets anders zijn dan een verdraaiing of spiegeling van een al geëvalueerde stelling herkent, dan kan het aantal recursieve aanroepen van chooseMove nog verder verminderd worden. Bij de beginzet hoeft de computer nog maar 3 mogelijke eerste zetten te evalueren (in plaats van 9). Natuurlijk moet je de transpositietabel nu al vanaf level 1 gebruiken.
  • Misschien kun je zelf nog meer verbeteringen vinden?

Pas het algoritme zo aan dat de computer de kortste weg naar de winst neemt,  met meer variatie speelt en verdraaiingen en spiegelingen herkent.

Opdracht 5b. 5x5 TTT.

Bij het Tic-Tac-Toe spel is het mogelijk om een stelling helemaal door te rekenen. Bij veel andere spellen is dat niet mogelijk. Lees paragraaf 11.2.3 over schaakprogramma's.

Schrijf een uitgebreide versie van Tic-Tac-Toe dat op een bord van 5x5 wordt gespeeld en waarbij de eerste speler met 4 aansluitende kruisjes of rondjes wint. Beantwoord voor je gaat beginnen de volgende vragen:

  • Kun je het spel helemaal doorrekenen?
  • Hoe kun je de waarde bepalen van een stelling die geen eindstelling is?
  • Hoe kun je voorkomen dat de computer een eenmaal gekozen pad helemaal tot het eind probeert door te rekenen?
  • Hoe kun je de "intelligentie" van de computerspeler instelbaar maken?

Opdracht 5c. 3D TTT.

Ontwerp een 3D versie van het spel boter, kaas en eieren. In deze 3D versie bestaat het speelbord uit een kubus van 4x4x4 = 64 vakjes.  De eerste speler die 4 symbolen op een rij weet te zetten wint. Ontwerp het spel zodanig dat het door één persoon tegen de computer gespeeld kan worden.

Opdracht 5d. Mega TTT.

Ontwerp een mega versie van het spel boter, kaas en eieren. In deze mega versie bestaat het speelbord uit 9 spelletjes die tegelijkertijd gespeeld worden. Elk spelletje bestaat uit 9 vakjes waarin boter, kaas en eieren gespeeld kan worden. Als in een spelletje de kruisjes winnen wordt dit hele spelletje een kruis. Als in een spelletje de rondjes winnen wordt dit hele spelletje een rondje. Als een spelletje helemaal gevuld is zonder dat er drie kruisjes of rondjes op een rij staan wint degene die de meeste symbolen in dit spelletje heeft staan. Het speelveld bestaande uit de 9 spelletjes wordt op deze manier zelf ook weer een boter kaas en eieren spelletje. Zodra één van de twee spelers drie spelletjes op een rij wint, wint hij of zij het totale spel. Ontwerp het spel zodanig dat het door één persoon tegen de computer gespeeld kan worden.

Opdracht 5e. TTT for kids.

Het is voor kinderen helemaal niet leuk/motiverend om met het bovenstaande TTT programma te spelen omdat ze nooit kunnen winnen. Pas het programma zo aan dat de stand over meerdere spelletjes ook wordt bijgehouden en dat zodra de computer een voorsprong heeft (of misschien zelfs ook bij een gelijke stand of een kleine achterstand) de gebruiker ook een kans krijgt om te winnen. Het zou mooi zijn als de gebruiker meer kansen krijgt om te winnen (in één spel) als zijn achterstand (over meerdere spelen) groter is.