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.

## Wednesday, January 16, 2008

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment