Opdracht 6: Boter Kaas en Eieren.

© Harry Broeders.

Bij deze opdracht mag je kiezen uit 6a t/m 6d. Je hoeft dus maar 1 deelopgave te maken! Alle opdrachten gaan over het uitbreiden of aanpassen van het in les 15 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 6a. 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.

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 6b. 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 6c. TTT GUI.

Bij deze opgave kun je jezelf verder bekwamen in het schrijven van windows applicaties. Er wordt bij deze opgave vanuit gegaan dat je de inleidende opdracht over het programmeren van windows applicaties met Borland 6 hebt gemaakt.

Maak een gebruiksvriendelijke (grafische) user interface voor het Tic-Tac-Toe spel.

Opdracht 6d. Mega TTT.

Ontwerp een mega versie van het spel boter, kaas en eieren. In deze mega versie bestaat het speelbord uit 9 spelletjes. 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.