Transcript 1 - Imai Laboratory

Imai Laboratory Introduction
Game Tree Search
The Purpose of Game Research
Clear Goal
Beat Human Champion
Show the Ability
of Computers
Current Strength of Computers
Fair Comparison
Strength !
Difficulty
Enormous Search Space
Enough Speed for Interactive Play
Checkers : Defeated Human Champion in 1994
Solved in 2007
Reversi : Defeated Human Champion 6-0 in 1996
Chess
: Defeated Human Champion in 1997
Shogi (Japanese Chess) : Only some hundreds of
people can beat strongest programs
Go
Ideal Test Bed for AI research
: Strongest Programs are at weak
amateur player level (about 1dan)
Alpha-Beta search and its variants
2 Person Zero-Sum Perfect Information Games can be solved by mini-max search
Max node
1 player tries to maximize the score, while the other tries to
minimize the score. (Zero-Sum)
65
Min node
65
62
65
90
62
There is no need to search all nodes, to find out a provably
optimal leaf node.
Using alpha-cut and beta-cut, we can reduce search space.
83
Original Search Space = N
65
35
90
49
62
30
83
Alpha-Beta Search Space 
80
Df-pn (Depth First Proof Number Search)
PNS (Proof Number Search) [1] is a
strong algorithm for AND/OR tree search
Proof number : The lower bound of the
number of nodes which is needed to be
proved in order to prove (attacker’s WIN)
Attacker expands from
the node with the
smallest proof number
In other words, players
try to minimize the
opponent’s options
min
3
Represents
defender’s turn
sum
1
1
1
1
Df-pn [2] is a depth-first version of
proof number search
th∞,th∞
th2,th∞-1
(2,2)
th4,th∞-1
a (3,1)
Represents
attacker’s turn
AND node
Attacker’s win if all
the child nodes are
WIN for the attacker
2 n
2 m
OR node
Attacker’s win if one
of the child nodes is
a WIN
N
th3
th2
b (2,1)
th3
c (1,2) th3
d (1,2)
(1,1) (1,1) (1,1)
(1,1)
(1,1)
(1,1)
(1,1)
Df-pn uses 2 thresholds each for
proof numbers and disproof numbers
1
Works fast with small size of memory
Df-pn and it’s variants are currently the best algorithms for checkmate search.
Df-pn+ [2] : Df-pn with heuristic (dis)proof number generation. Best Tsume-shogi solver.
Df-pn(r) [3] : Df-pn+ with exact repetition handling. Best TsumeGo solver.
Df-pn(l) [4] : Combination of Df-pn+ and l search. Solves Capturing Problem in Go.
References (Imai lab. Members in Red)
[1] Victor Allis, “Searching for Solutions in Games and Artificial Intelligence,” Ph.D. Thesis, University of Limburg, Maastricht, 1994.
[2] Ayumu Nagai, “Df-pn Algorithm for Searching AND/OR Trees and Its Applications”, Ph.D. Thesis, University of Tokyo, 2002.
[3] Akihiro Kishimoto, “Correct and Efficient Search Algorithms in the Presence of Repetitions,” Ph.D. Thesis, University of Alberta, 2005 .
[4] Kazuki Yoshizoe, Akihiro Kishimoto and Martin Müller, “Lambda Depth-First Proof Number Search and Its Application to Go,”
In Proceedings of 20th International Joint Conference on Artificial Intelligence (IJCAI-07), pages 2404-2409, 2007