Seminar Outline


*          Game theory


*          Othello


*          Game playing programs


*                      Depth search


*                      Evaluation













Game theory


Strong gaming engines posses the following qualities:


*          Prediction of opponent’s move

*          Alpha-beta pruning

*          Fine-tuning to opponent’s strategy


*          Evaluation techniques

*          Structural

*          Adaptive evaluation

*          Depends significantly on the game









Depth 0




Depth 1




Depth 2



Depth 3



Depth N

Game Tree










*          A given game is a finite state machine

*          Nodes represent possible decisions points within game





Alpha-Beta Pruning


*          Evaluates paths in the game tree

*          Takes into account whose turn it is

*          Searches game tree to a given depth X

*          Seeks the state with the maximal evaluation


Oval: 0Oval: -3Oval: 12Oval: -10Oval: -12Oval: 15Oval: 10Player
















*          Assignment of value to a given game state

*          Common evaluation techniques:

*                      Structure/Layout

*                      Count of game pieces

*                      Prospective – where depth search utilised












*          Relevant Principals:

*                      Aim is to capture the most positions on board

*                      Stones can be flipped i.e. recaptured

*                      High number of available moves is advantageous

*                      Some positions on board e.g. corners are of tactical importance

*                      Some positions on board are undesirable













Evaluation in Othello


*          Score


*          Mobility


*          Position


*          Line structure











Game Playing Program Design


*          Depth Search:

*                      Recursion

*                      Prediction of opponent’s move

*                      Factorisation of opponent’s best choices


*          Evaluation:

*                      Accumulator

*                      Series of tests

*                      Obtain final value