Boter Kaas en Eieren (ALGODS).

Deze pagina is bestemd voor studenten van de Haagse Hogeschool - Faculteit voor Technologie, Innovatie & Samenleving Delft groep ECV.

In de les is het volgende document uitgedeeld: Een deel van de zoekboom: ttt.pdf

Uitleg over het minimax en alpha-beta pruning kun je vinden in hoofdstuk 7 van het dictaat.

Verdere informatie over alpha-beta vind je hier:

Goed uitgelegd voorbeeld van alpha-beta pruning.
Een Java Applet die een animatie laat zien van alpha-beta pruning.
Aske Plaat van de Universiteit van Tilburg heeft het algoritme MTD(f) bedacht dat nog beter werkt dan alpha-beta pruning (waarin overigens ook weer gebruik gemaakt wordt van apha-beta pruning en van een transpositietabel. Zie: http://askeplaat.wordpress.com/534-2/mtdf-algorithm/
Kijk hier hier hoe Patrick Winston op het MIT het verhaal over gametrees verteld: https://www.youtube.com/watch?v=STjW3eH0Cik&list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi&index=6 Hij gebruikt schaken als voorbeeld in plaats van Boter, Kaas en Eieren.

De door mij geschreven programma's kun je hier vinden. Deze programma's zijn geïnspireerd door paragraaf 11.2 van het boek Data Structures and Problem Solving Using C++, 2/E van Mark Allen Weiss, ISBN: 978-0-201-61250-9:

Hulp class matrix: Matrix.h met bijbehorend testprogramma: MatrixTest.cpp .
Tic-Tac-Toe programma: TicTacSlow.cpp .
Tic-Tac-Toe programma met alpha-beta pruning: TicTacAB.cpp .
Tic-Tac-Toe programma met alpha-beta pruning en transposition table met behulp van std::map: TicTacMap.cpp .
De bovenstaande programma's kiezen geen zet als alle mogelijke zetten tot verlies leiden. Dit is bij Tic-Tac-Toe geen probleem omdat de computer niet kan verliezen maar bij ingewikkeldere spellen is dit wel een probleem! Dit probleem wordt gedemonstreerd en opgelost in het programma TicTacABLoser.cpp (met dank aan Marc Cornet).
Bij het gebruik van een transpositietabel kun je de diepte waarop de tabel gebruik wordt limiteren, zie TicTacMapRestrictedDepth.cpp . Daarbij moet de optimale waarde van MAX_TABLE_DEPTH worden bepaald. Dit kun je doen met het programma TicTacDetermineMaxTableDepth.cpp .

Snelheid van de verschillende transpositie tabellen (op mijn machine zonder optimalisatie):

TicTacDetermineMaxTableDepth

MAX_TABLE_DEPTH	moves considered	time needed for first move in `std::map` version	size map
2	16811	0,0706661	0
3	16811	0,0709619	30
4	14047	0,0632046	118
5	11523	0,0675519	369
6	7954	0,0937331	841
7	5622	0,139846	1513
8	4487	0,215412	2135
9	4272	0,259741	2407

Zonder alpha-beta prunning en zonder transpositie tabel duurt het op mijn machine 2,2 s voordat de eerste zet is gevonden.