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

 

 

Opponent

 

 

 

Player

 

 

 

 

 

 

Evaluation

 

*          Assignment of value to a given game state

*          Common evaluation techniques:

*                      Structure/Layout

*                      Count of game pieces

*                      Prospective – where depth search utilised

 

 

 

 

 

 

 

 

 

Othello

 

*          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

 

 

 

 

 

Summary