Adversarial Search
By Robert Laing
Tables/Schemas
State Table
CREATE TABLE IF NOT EXISTS chess_states
( id SERIAL PRIMARY KEY
, state JSONB UNIQUE
, goal JSONB -- NULL for non-terminal states
);
Goal
Only final states have a goal value. So instead of a boolean value for terminal, non-terminal states have null for goal.
Move Table
CREATE TABLE IF NOT EXISTS chess_moves
( id SERIAL PRIMARY KEY
, move JSONB UNIQUE
);
MID is unique, Moves get appended, but never updated
Game Tree
CREATE TABLE IF NOT EXISTS chess_graph
( init_id INTEGER REFERENCES chess_states(id)
, move_id INTEGER REFERENCES chess_moves(id)
, next_id INTEGER REFERENCES chess_states(id)
, utility JSONB
, mobility JSONB
, visits INTEGER DEFAULT 0
, total JSONB
, PRIMARY KEY (init_id, move_id)
);
Utility
The utility for (init_id, move_id) is calculated from next_id
If the next state is a terminal, utility = goal
For non-terminal next states, utility needs to be guessed using heuristics for the next state and move:
- Piece count of next state
- Moves to be avoided (eg in chess, moving a king or rook which kills chances of later castling) and moves to be encouraged (eg in chess checking opponent, castling, advancing pawns two spaces)
Mobility
Use Json reserved word null to differentiate unexplored parts of the game tree from final states where moves are zero.
If next_id is a terminal, mobility for all players is zero eg:
[["white", 0], ["black", 0]]
State representation
Original kif
(init (cell a 1 wr))
(init (cell a 2 wp))
(init (cell a 3 b))
(init (cell a 4 b))
(init (cell a 5 b))
(init (cell a 6 b))
(init (cell a 7 bp))
(init (cell a 8 br))
(init (cell b 1 wn))
(init (cell b 2 wp))
(init (cell b 3 b))
(init (cell b 4 b))
(init (cell b 5 b))
(init (cell b 6 b))
(init (cell b 7 bp))
(init (cell b 8 bn))
(init (cell c 1 wb))
(init (cell c 2 wp))
(init (cell c 3 b))
(init (cell c 4 b))
(init (cell c 5 b))
(init (cell c 6 b))
(init (cell c 7 bp))
(init (cell c 8 bb))
(init (cell d 1 wq))
(init (cell d 2 wp))
(init (cell d 3 b))
(init (cell d 4 b))
(init (cell d 5 b))
(init (cell d 6 b))
(init (cell d 7 bp))
(init (cell d 8 bq))
(init (cell e 1 wk))
(init (cell e 2 wp))
(init (cell e 3 b))
(init (cell e 4 b))
(init (cell e 5 b))
(init (cell e 6 b))
(init (cell e 7 bp))
(init (cell e 8 bk))
(init (cell f 1 wb))
(init (cell f 2 wp))
(init (cell f 3 b))
(init (cell f 4 b))
(init (cell f 5 b))
(init (cell f 6 b))
(init (cell f 7 bp))
(init (cell f 8 bb))
(init (cell g 1 wn))
(init (cell g 2 wp))
(init (cell g 3 b))
(init (cell g 4 b))
(init (cell g 5 b))
(init (cell g 6 b))
(init (cell g 7 bp))
(init (cell g 8 bn))
(init (cell h 1 wr))
(init (cell h 2 wp))
(init (cell h 3 b))
(init (cell h 4 b))
(init (cell h 5 b))
(init (cell h 6 b))
(init (cell h 7 bp))
(init (cell h 8 br))
(init (control white))
(init (step 1))
Prolog
Start = [
cell(a,8,br),cell(b,8,bn),cell(c,8,bb),cell(d,8,bq),cell(e,8,bk),cell(f,8,bb),cell(g,8,bn),cell(h,8,br),
cell(a,7,bp),cell(b,7,bp),cell(c,7,bp),cell(d,7,bp),cell(e,7,bp),cell(f,7,bp),cell(g,7,bp),cell(h,7,bp),
cell(a,6,b),cell(b,6,b),cell(c,6,b),cell(d,6,b),cell(e,6,b),cell(f,6,b),cell(g,6,b),cell(h,6,b),
cell(a,5,b),cell(b,5,b),cell(c,5,b),cell(d,5,b),cell(e,5,b),cell(f,5,b),cell(g,5,b),cell(h,5,b),
cell(a,4,b),cell(b,4,b),cell(c,4,b),cell(d,4,b),cell(e,4,b),cell(f,4,b),cell(g,4,b),cell(h,4,b),
cell(a,3,b),cell(b,3,b),cell(c,3,b),cell(d,3,b),cell(e,3,b),cell(f,3,b),cell(g,3,b),cell(h,3,b),
cell(a,2,wp),cell(b,2,wp),cell(c,2,wp),cell(d,2,wp),cell(e,2,wp),cell(f,2,wp),cell(g,2,wp),cell(h,2,wp),
cell(a,1,wr),cell(b,1,wn),cell(c,1,wb),cell(d,1,wq),cell(e,1,wk),cell(f,1,wb),cell(g,1,wn),cell(h,1,wr),
control(white)
]
JSON Array
Json = [
["cell","a",8,"br"],["cell","b",8,"bn"],["cell","c",8,"bb"],["cell","d",8,"bq"],["cell","e",8,"bk"],["cell","f",8,"bb"],["cell","g",8,"bn"],["cell","h",8,"br"],
["cell","a",7,"bp"],["cell","b",7,"bp"],["cell","c",7,"bp"],["cell","d",7,"bp"],["cell","e",7,"bp"],["cell","f",7,"bp"],["cell","g",7,"bp"],["cell","h",7,"bp"],
["cell","a",6,"b"], ["cell","b",6,"b"], ["cell","c",6,"b"], ["cell","d",6,"b"], ["cell","e",6,"b"], ["cell","f",6,"b"], ["cell","g",6,"b"], ["cell","h",6,"b"],
["cell","a",5,"b"], ["cell","b",5,"b"], ["cell","c",5,"b"], ["cell","d",5,"b"], ["cell","e",5,"b"], ["cell","f",5,"b"], ["cell","g",5,"b"], ["cell","h",5,"b"],
["cell","a",4,"b"], ["cell","b",4,"b"], ["cell","c",4,"b"], ["cell","d",4,"b"], ["cell","e",4,"b"], ["cell","f",4,"b"], ["cell","g",4,"b"], ["cell","h",4,"b"],
["cell","a",3,"b"], ["cell","b",3,"b"], ["cell","c",3,"b"], ["cell","d",3,"b"], ["cell","e",3,"b"], ["cell","f",3,"b"], ["cell","g",3,"b"], ["cell","h",3,"b"],
["cell","a",2,"wp"],["cell","b",2,"wp"],["cell","c",2,"wp"],["cell","d",2,"wp"],["cell","e",2,"wp"],["cell","f",2,"wp"],["cell","g",2,"wp"],["cell","h",2,"wp"],
["cell","a",1,"wr"],["cell","b",1,"wn"],["cell","c",1,"wb"],["cell","d",1,"wq"],["cell","e",1,"wk"],["cell","f",1,"wb"],["cell","g",1,"wn"],["cell","h",1,"wr"],
["control","white"]
]
Expanding Minimax from 2 to n players
There is a tradition in textbooks to use an algorithm called minimax which uses one number to value states in a two player games, with one player ahead if this number is positive, the opponent ahead it’s negative, and zero indicating a draw.
This is often attributed to John von Neumann’s and Oskar Morgenstern’s book Theory of Games and Economic Behavior, though they never used the term and built their theory for “zero-sum two-person games” to zero-sum n-person games".
A snag with using one number and a Max and a Min player is it obscures the basic idea — the controlling player
in a given state will pick their most favourable move. Instead of one number, something like a vector is needed,
which I’ve done as [value(white, 50), value(black, 50)] which GGP provides with its goal(State, Player, Value)
predicates.
minimax tends to go hand-in-hand with α-β pruning, which again limits an idea applicable to n-players to just 2 players.
Essentially, what we need to do is:
- Assume the player whose turn it is —
member(control(Player), Parent)— will pick the maximum of thevalue(Player, Value)of next states available. - The opposing player needs to be forewarned about where future moves will lead. This means that while growing the game tree downward, parent nodes need to update their values with fresh values optained from children — what I think the jargon term dynamic programing means.
- Thanks to iterative deepening, the branches that need to be expanded narrow, helping the AI focus on
The above diagram indicates that once a terminal is reached that isn’t a draw, the existing value of its parent node can
be replaced with that value. The grandparent node in turn needs to check if member(control(Player), GrandParent) has
been snookered.
At this stage, I’m doing this upward propogation by replacin the existing max of member(control(Player, Parent) with
max of member(control(Player, Child), continuting upward to the root as long as changes are made.
One of the simplification in the example used in Game Trees was the entire graph was placed in the clausal store to search. Moving on, the game player starts only knowing the initial state and the rules for expanding the tree, so has to play blind man’s buff to find it’s way to winning states and avoid losing ones.
I’m going to continue using the clausal store as a place to memoize explored paths so that they don’t have to be constantly regenerated. Another reason to remember the game tree as it develops is to support dynamic programing.
?- bestmove([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o),
cell(2, 1, b), cell(2, 2, o), cell(2, 3, b),
cell(3, 1, b), cell(3, 2, o), cell(3, 3, x),
control(white)], Move).
% Generated
% [Thread 3] Generated
% [Thread 4] Generated
% [Thread 4] Generated
% [Thread 4] Memoized
% [Thread 4] Memoized
% [Thread 4] Generated
Move = [does(white, mark(3, 1)), does(black, noop)].