Buffl

Game Playing

NK
by Noel K.

What are the key ideas behind techniques such as transition tables, Zobrist keys, null-move pruning, …?


  • Null-move pruning

    • Add a null-move to the search i.e. assume taht the current player doesn’t make a move. If the null-move results in a cutoff, assume that making a move will do the same.

  • Transposition Tables

    • Different sequences of the same moves come to the same result: Find them and save them in Hash Tables, so that you have to compute / search only once.

  • Zobrist (Hash) Keys

    • A way to store the sequences of moves in the transposition table. Take an 3d-array with arbitrary long random int numbers (for example 64 bit or even longer) as values. The coordinates are piece type, location and color. Initialize a 64 bit Hash Key with 0. Now each turn you need to look up the value from the moved piece in your array and xor it with the last position of the piece and afterwards xor the result with the hash key. If the last position is empty use 0 instead. Biggest plus is that it can be updated incrementally.

  • Forward Pruning

    • Pruning is part of a heuristic, which removes completely certain branches of the search tree. You can do this because the algorithm knows, or thinks (Dangerous!) that the tree does not change the result of the search. Forward pruning in particular always involves some risks to overlook something, with influence on the root score.

  • Zermelo Theorem

    • A deterministic, perfect information, 2 player game can be sorted in one of three categories:

      • Player 1 wins

      • Player 2 wins

      • Both Player can force a draw

  • Solving a Game ultra weakly

    • Prove whether the first player will win, lose or draw from the initial position, given perfect play from both sides

      • by non-constructive proof, which does not help in the play

      • by complete min-max or alpha-beta search

  • Solving a Game weakly

    • Provide an algorithm which secures a win for one player or a draw for either, against any possible moves from the opponent, from the initial starting position only

  • Solving a Game strongly

    • Provide an algorithm, which can produce perfect play from any position ⇒ mostly with some kind of database

  • Quiescence Search

    • We do evaluation only during quiescent states.

      • Those states are without wild swings in value in the near future

      • states in the middle of exchange are not

    • When search depth is reached look whether this is a quiescence state

    • if not search further until you find one. Evaluate Heuristic

  • Search Extensions

    • When a force move is found look further. The reason is that a forced move narrows width of the tree. Be careful, search must always terminate somehow.

  • Move Ordering 

    • Crucial to the performance of alpha-beta search

    • Domain dependent heuristics: capture and forward moves first

    • Domain independent heuristics: killer heuristic (if there is a strong threat, this should be searched first; history heuristic (if a move produces a cutoff, its value is increased)


Author

Noel K.

Information

Last changed