Transcript Renju

Renju
Presented by JungYun Lo
National Dong Hwa University
Department of Computer Science and Information Engineering
Artificial Intelligence Laboratory
2004/12/02
Outline
•
•
•
•
The rules of Renju
Threat-Space Search
Proof-Number Search
Reference
2004.12.02
Renju
2
The rules of Renju (1)
• Opening
– the players are preliminary black and
preliminary white
– The player who is preliminary black
puts three stones on the board - two
black ones and one white stone. This
start of the game is called the
opening
2004.12.02
Renju
3
The rules of Renju (2)
• The first move is always in the centre (marked
on the board) with the black stone! The second
stone is white put in the 3x3 square around the
first move. The third stone is again black and
put in the area of 5x5 intersections around the
first move.
Direct openings
2004.12.02
Renju
Indirect openings
4
The rules of Renju (3)
• When the first player has put all the three
stones on the board, the second player can
choose the color of the stones she wants to
play with.
• When the fifth move. The player with black
stones puts two fifth moves on the points,
which she/he considers as the best ones.
White player takes one of the moves away and
makes a move in his/her turn.
2004.12.02
Renju
5
The rules of Renju (4)
• The forbidden moves for black
– Double threes
– Double fours
– Overlines
2004.12.02
Renju
6
The rules of Renju (5)
• How could black win?
– Four-three
2004.12.02
Renju
7
Proof-Number Search
• Proving the true value of the root
• Using two criteria to expand next
node
– The potential range of subtree values
– The number of nodes which must
conspire to prove or disprove that
range of potential values
• Enable pn-search to treat efficiently
game trees with a non-uniform
branching factor.
2004.12.02
Renju
8
Threat-Space Search (1)
• A winning threat sequence consists of
threats.
– Reducing the size
– More efficient
• After a four, one
defensive is possible
• After a three, two or
three are possible
2004.12.02
Renju
9
Threat-Space Search (2)
• Definitions
– The gain square of a threat is the square
played by the attacker
– The cost squares of a threat are the squares
played by the defender, in response to the
threat
– The rest squares of a threat are the squares
containing a threat possibility; the gain
square expected
– Threat A is dependency on threat B, if a rest
square of A is the gain square of B
2004.12.02
Renju
10
Threat-Space Search (3)
a b cd e fg h i j k l mn o
e15 is a gain square
with e15:
cost square is d15
rest squares are a15, b15
and c15
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
After the moves e15 and d15
playing i11 creates a four
(rest square e15,f14 and g13)
thus the gain square i11 is
dependent on gain square e15
2004.12.02
Renju
11
Threat-Space Search (4)
• Definitions
– The dependency tree of a threat A is the
three with root A and consisting of
dependent nodes only
– Two dependency trees P and Q are conflict,
if within dependency tree P a threat A exists
and within dependency tree Q a threat B, in
such a way that
• The gain square of A is cost square in B
• Vice versa
• A cost square in A is also cost square in B
2004.12.02
Renju
12
Threat-Space Search (5)
a b cd e fg h i j k l mn o
The dependency tree of
threat i11 is the four with gain
square i11.
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
It also the only child of root of
dependency tree of threat
e15.
Threat with gain square e15
( cost square d15)
and threat with gain square
d15 ( cost square e15) are
conflict
2004.12.02
Renju
13
Threat-Space Search (6)
a b cd e fg h i j k l mn o
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
2004.12.02
Renju
14
Reference
•
Renju International Federation
–
•
Go-moku and Threat-Space Search (1993)
–
–
•
Janos Wagner, Istvan Virag
ICGA march 2001
Combining Proof-Number Search with Alpha-Beta Search (2001)
–
–
•
L.V. Allis, H.J. van den Herik, M.P.H. Huntjens
Report CS 93-02, Department of Computer Science, Faculty of General
Science, University of Limburg. Maastricht, The Netherlands
Solving Renju (2001)
–
–
•
http://www.renju.nu/
Mark H.M. Winands, Jos W.H.M. Uiterwijk
http://www.cs.unimaas.nl/m.winands/
Proof-number search (1994)
–
–
L. V. Allis, Maarten van der Meulen and H. J. van den Herik
Artificial Intelligence vol.66 Issue.1 pp.91-124
2004.12.02
Renju
15
Thanks for your
attention!
2004.12.02
Renju
16