## Go & chess

1. EXAMPLE of an evaluation function (Shannon, 1950):
2. Let K, Q, R, B, N, and P denote the number of White kings, queens, rooks, bishops, knights and pawns on the board
3. Let K′, Q′, R′, B′, N′, and P′ denote the number of Black kings, queens, rooks, bishops, knights and pawns on the board
4. Let D, S, and I denote the double, backward or isolated White pawns
5. Let D′, S′, and I′ denote the double, backward or isolated Black pawns

6. #### Function f = 200(K - K′) + 9(Q - Q′) + 5(R - R′) + 3(B - B′ + N - N′) + (P - P′) – 0.5(D - D′ + S - S′ + I - I′)

1. The drosophila (or the humble fruit fly) is a good model organism in biology, neuroscience, and genetics
2. Chess has been described by Alexander Kronrod as the drosophila of AI research

3. How do we design an AI system to play a skilful (i.e. human expert-level) game of chess?

4. RESPONSE 1: We could rely on a set of principles
1. PRINCIPLE 1: The player with greater mobility has the better game
2. PRINCIPLE 2: Different PRINCIPLES apply in different phases (e.g. opening, middle game, endgame) of the game
3.        ⋮

5. RESPONSE 2: We could rely on an evaluation function

6. RESPONSE 3: We could rely on a minimax algorithm

1. Go (围棋 or weiqi) is a 2-player sequential zero-sum game with perfect information
2. The aim of Go is for each player to surround more territory than the opponent

 Go board There are 19 vertical lines and 19 horizontal lines on the Go board This yields 361 (or 192) points or intersections 9 points on the board are dotted and called star points The point in the centre is called the central star The rules of Go P1 (Black) takes the black stones and makes the first move P2 (White) takes the white stones and makes the next move P1 (Black) and P2 (White) take turns to move and only one stone can be played per move A stone on the Go board has 2-4 adjacent intersections Whichever of these intersections is/are unoccupied would be called liberties Stones adjacent to other stones of the same colour form a unit and their liberties are counted together When all the liberties of a stone or group of stones have been taken by the opposite colour, those stones cannot remain on the board The game of Go ends when both P1 and P2 agree that there will be no more moves or when either P1 or P2 resigns Counting the score At the end of the game, whichever stones will inevitably be captured are dead Stones that cannot be captured are alive All dead stones of both P1 and P2 are removed from the board All living stones of each player are counted, including the vacant points enclosed by those stones Vacant points between the living stones of both P1 and P2 will be shared equally 180½ is half the number of points on the board Let t denote Pn's total number of living stones and enclosed vacant points If t > 180½, then Pn wins If t < 180½, then Pn loses If t = 180½, then the game has ended in a draw

1. Go is a far more complex game than chess

Chess Chinese Chess Shogi Go
Board size 64 (8 × 8) 90 (9 × 10) 81 (9 × 9) 361 (19 × 19)
State space complexity 1046 1048 1071 10172
Game tree complexity 10123 10150 10226 10360
Branching factor 35 38 92 250