Boter Kaas en Eieren (SOPX3).

Deze pagina is bestemd voor studenten van de Haagse Hogeschool - TH Rijswijk/Academie voor Engineering groep EH3 C&D.

In de les zijn de volgende documenten uitgedeeld:

Hoofdstuk 8.7 en 11.2 van het boek Data Structures and Problem Solving Using C++, 2/E van Mark Allen Weiss, ISBN: 0-201-61250-X.
Een deel van de zoekboom: ttt.pdf
Uitleg over alpha-beta pruning.

De door mij enigszins aangepaste programma's kun je hier vinden:

Hulp class Matrix: Matrix.h
Tic-Tac-Toe programma: TicTacSlow.cpp
Tic-Tac-Toe programma met alpha-beta pruning en transposition table met behulp van std::map: TicTac.cpp
Tic-Tac-Toe programma met alpha-beta pruning en transposition table met behulp van een (perfect) hash table (idee van Remco Boom in 2005): TicTacRemco.cpp

Snelheid van de verschillende transpositie tabellen:

MAX_TABLE_DEPTH moves considered time needed for first move
in std::map version time needed for first move
in perfect hashtable version size map size hashtable

4 11523 0.77 0.61 339 19682

5 7954 0.66 0.40 768 19682

6 5622 0.71 0.33 1364 19682

7 4487 0.77 0.22 1765 19682

8 4272 0.88 0.22 1927 19682

MAX_TABLE_DEPTH	moves considered	time needed for first move in `std::map` version	time needed for first move in perfect hashtable version	size map	size hashtable
4	11523	0.77	0.61	339	19682
5	7954	0.66	0.40	768	19682
6	5622	0.71	0.33	1364	19682
7	4487	0.77	0.22	1765	19682
8	4272	0.88	0.22	1927	19682

Zonder alpha-beta prunning en zonder transpositie tabel duurt het 27.4 s voordat de eerste zet is gevonden.