DPS906 Lecture 3

Review So far
- A game tree is a method for evaluating who will win a game
- top node is a max node, next is min node, next is max, etc
- lots of what if -> get score.
- score is determined by what the children's score is unless terminating node
- if we cannot fit every terminating state in RAM, we need some sort of Evaluation function
- Evaluation function is a heuristic to determine the "value" of the board
- Eval must be fast, predictive, and have a known range
- Move Generation (does the MGH (move gen heuristic) come before or after the generation of the Node)

Transposition Tables Zobrist Keys
- idea is that a board's state may be identical although they are generated from multiple different paths.
- record the scores of boards you've already encountered, so that if you encounter them again, you dont have to re-calculate them.
- how do you remember? Use a hash tables
Zobrist Key
- create a matrix of random integers (on startup)
- - size = number of players * number of squares in game board * number of piece types
- - - eg tic-tac-toe = 2 * 9 * 1 = 18
- assign each value in the matrix a binary value (bigger randomness is better 1-100 > 1-10)
- Xor the tables to get a value... the final number is the zobrist key
- application for hash table tricks.

Two types of collisions
- two different boards have same zobrist key
- normal hash table collision (isn't bad - handle as normal)

Alpha Beta Pruning
- alpha beta is the same result as non-alpha beta... but is faster.