It was 1987 that I had been interested in the Shogi(Japanese chess) program.
I found "ESS" in the secondhand book shop.
"ESS" (Electro-brains Shogi System) was printed to the magazine of “MICRO"
of the sale in 1984. I began to make shogi program “YSS(Yamashita Shogi
System)" at that time.
And I (YSS 2.0) participated in the first time the 2nd computer shogi
championship in 1991. I participated in the championship continuously after
that. My rank was 5, 4, 4, 3, and the 4th place from the 2nd championship.
Finally "YSS 7.0" won the 7th championship in February 1997.
And "Kanazawa Shogi" that won four times continuously lost.
I explain search algorithm and evaluation function of "YSS 7.0".
"YSS 7.0" is sold as“AI Shogi 2" in Japan form Ascii Something Good
Company in April, 1997.
1. Data structures
To make computer play shogi, it is necessary to teach the rule of shogi at
least.
The first plan of data structures is important because the influence is the
largest in the programming afterward. I changed basic data structure three
times. Finally I adopted using Piece Number.
All programs are written in the C language, and move on WindowsNT.
A basic data structure of YSS is following.
All 40 pieces are numbered as 1-40.
Black King is 1. White King is 2. Rook is 3-4, Bishop 5-6,
Gold 6-10, Silver 11-14, Knight 15-18, Lance 19-22, Pawn 23-40.
Position and status ( black or white, promoted or non ) are maintained each
pieces.
In real shogi board, right top is (1,1) and left bottom is (9,9).
But this coordinate system is bad for computer.
So I use left top (1,1) and right bottom (9,9).
Real 77-76 Pawn is changed 37-36 Pawn. X coordinates reverse.
Shogi board is 9*9. So it is easy to use two dimension of 9*9.
But I use one dimension board[256] for speed.
The position of coordinates is shown with y*16+x.
So 76 Pawn is 36 Pawn, and x=3, y=6.
Because x=3 and y=6, z = y*16+x = 0x63 ( in the C ).
Board[0x63] show number of piece that exists here.
For clearly outside of board, I make a frame in surroundings of the board.
So board size is 11*11 in program.
When Kiki table (this shows the place where each piece can move) is made,
an extra judgment is unnecessary.
- Table 1 - Kind of Black piece and number
Pawn Lance Knight Silver Gold Bishop Rook King
1 2 3 4 5 6 7 8
Promoted Pawn Pro.Lance Pro.Knight Pro.Silver ---- Horse Dragon
9 10 11 12 13 14 15
When piece promote, number is add 8. White piece is added 0x80(=128).
For example, White Dragon is 0x8f(= 128+7+8). Do you think shogi piece
is convenience for expressing by hexadecimal notation?
Initialize board data is following. 0xff is outside.
int board[256]= {
0xff, 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, 0xff,0,0,0,0,0,
0xff, 0x82,0x83,0x84,0x85,0x88,0x85,0x84,0x83,0x82, 0xff,0,0,0,0,0,
0xff, 0x00,0x87,0x00,0x00,0x00,0x00,0x00,0x86,0x00, 0xff,0,0,0,0,0,
0xff, 0x81,0x81,0x81,0x81,0x81,0x81,0x81,0x81,0x81, 0xff,0,0,0,0,0,
0xff, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0xff,0,0,0,0,0,
0xff, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0xff,0,0,0,0,0,
0xff, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0xff,0,0,0,0,0,
0xff, 0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01, 0xff,0,0,0,0,0,
0xff, 0x00,0x06,0x00,0x00,0x00,0x00,0x00,0x07,0x00, 0xff,0,0,0,0,0,
0xff, 0x02,0x03,0x04,0x05,0x08,0x05,0x04,0x03,0x02, 0xff,0,0,0,0,0,
0xff, 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, 0xff,0,0,0,0,0};
Piece Number(1-40) that don't exist in the board is pushed in the stack
according to each kind of piece.
When dropping the piece from the hand, program pop the empty Piece Number
from the stack.
For example, when Black drop Pawn to 47 in Fig. 1,
Pawn that don't exist in the board is 4. ( All Pawn is 18)
/* Content of stack */
PN_stack[1][0] = 0 （unused）
PN_stack[1][1] = 25
PN_stack[1][2] = 33
PN_stack[1][3] = 36
PN_stack[1][4] = 27 The number of pawns not used is 4.
PN_stack_number[1] = *PN_stack[1][4] (indicate）
|
V
PN[27][0] = 0x01 Piece Number 27 is Black Pawn.
PN[27][1] = 0x76 Position is 0x76 (=47 Pawn)
PN_stack_number[1]-- decrease stack, [1] is Pawn ,[2] is Lance.
Table 2. Main Data Array of YSS ( all is int.)
board[256] Piece Number is entered.
init_board[256] Kind of piece (nothing is 0, outside is 0xff,
Black Piece is 0x01-0x0f, White is 0x81-0x8f)
Hand_Black[8] Number of Black Hand
Hand_White[8] Number of White Hand
Kiki_Black[256] Kiki number of Black.
Kiki_White[256]
KikiC_B[256][32] Content of Black Kiki (what kind of piece?).
Kiki number maximum is 18.
KikiC_W[256][32] Content of White Kiki
PN[41][2] Piece Number [][0]...kind of piece, [][1]...position of piece.
PN_stack[8][32] Empty Piece Number.
*PN_stack_numbe[8] Pointer of empty Piece Number.
move[64][64][8] Move of each ply. (64 plies depth, 64 moves in one depth,
8 is move content and etc..)
best[64][64][4] best sequence. maximum depth is 64.
(4 is move content. Before, After, Capture piece, Promote flag)
ret_depth[64] depth of calling evaluation function.
depth_add Decimal point part of depth max.
depth_max depth_max.
*MoveP[64] Move pointer in each depth. This indicate move[64][64][8].
In the C language, an internal calculation is expressed by the bit shift
when you use array of 2^n ( for example, [53][64] or [3][16][256] ).
So you should use 2^n array for speed up.
Figure 1: explain of Kiki
There are two kinds of Kiki, indirect Kiki and direct Kiki.
Direct Kiki is the place which piece can actually move.
In indirect Kiki, piece can't move actually.
But when exchange is continue, indirect Kiki become effective.
For example in Figure 1, the place of 86 have indirect Kiki of 82 Rook.
Exceptionally, Kiki of Rook, Bishop and Lance go through opponent King one
step. This is useful in the checkmate judgment of king.
In Figure 1, Kiki of Black 44 Bishop go through opponent 33 King and reach 22.
Additionally in Figure 1, when 62 Silver move to 71, 44 Bishop Kiki is
effective in 71. This is called shadow Kiki. But YSS don't have Shadow Kiki.
KikiC_B[256][32] have Black Piece Number that can move here
(direct or indirect).
For example Figure 1 in White, the place of 86 have Kiki of 85 Pawn
(Piece Number is 26) and 83 Lance (Piece Number is 19) and 82 Rook
(Piece Number is 3).
Kiki_White[0x62] = 3; The number of White Kiki.
KikiC_W[0x62][0] = 26; The 26 Pawns work.
KikiC_W[0x62][1] = 3 + 0x80; The 3 Rook work
(0x80 is added because it is indirect).
KikiC_W[0x62][2] = 19 + 0x80;
The 19 Lance work (0x80 is added because it is indirect).
When the piece moves, these data structure is update partially only the place
with the change.
When 39 Silver moves to 38, all Kiki of 39 Silver is deleted.
And all 38 Silver is written. In this case, right Kiki of 88 Rook is
stopped by 38 Silver. So only right Kiki of Rook is deleted and written.
Besides, the data updated at the same time is hash (transposition) code
and basic value of pieces.
Table 2 shows main data structure of YSS.
Because I divide all data to Black and White, program have exclusive move
generator routine for Black and White.
For example, there are two routines which search fork of Bishop.
It is very useless, but when thinking of speed, it is slight.
2. Move generator
2.1 Classification of move
At first, YSS classify all move to "attacking move" and "defense move".
"Attack move" is the following three.
- Capture opponent's piece.
- Promote piece.
- Threat to capture (include fork).
"Defense move" is following 6.
- Capture piece that threaten my piece.
- Drop my piece before opponent drop.( when opponent drop is good.)
- Threaten square where opponent piece intend to move.
- Threatening piece run away.
- Interposes any piece when opponent rook or bishop or lance moving is good.
- Interposes any piece in square where opponent's rook or bishop or lance
threaten.
Only run away move in this 6, I actually move the piece on the board, and
calculate gain of piece, and select upper 3 or 5 move ( rook and bishop
is 5, gold and silver is 4), when (depth_max - depth) >= 3 .
Other move, I evaluate moves without actually moving on the board (only
temporary evaluation). When fork, the move that the threatening piece run
away and protect another piece can be discovered by actually moving a step.
2.2 Temporary move evaluation
A temporary evaluation of move is processed by the MIN-MAX method
according to the number of opponent and friend's threat in moving square.
Figure 1: explain capturing 85 pawn ( show once more )
For instance, I explain value of capturing 85 pawn in figure 1.
At first, value of pieces is assumed Table 3.
Second, piece exchange is done sequentially from low value piece to high
value piece.
In figure 1, Black pieces moving to 85 is knight, silver, bishop and to rook
sequentially. White is lance, gold and rook. (In figure 2, when white rook
and lance places change, lance can't move 85 first. But my program doesn't
consider it.)
Here, black has right to capture or not capture 85 pawn first.
If black capture 85 pawn by knight, white also has right to capture or not
capture 85 black knight by lance.
Figure 2
This makes Figure 2.
In figure 2, black is max, white is min, capture is left, not capture is
right. At first, if black don't capture 85 pawn, black score is 0 of course.
When black capture, if white don't capture, black score is +200 ( a pawn ...
this use exchange value in Table 3).
And when white recapture, if black don't, white score is +700. ( a knight -
a pawn )
Thus, making MIN-MAX tree, the value of capturing 85 pawn is +160 after all.
I use this value with adding board fixed value etc...
Table 3: value of pieces
Pawn Lance Knight Silver Gold Bishop Rook King
basic value 100 430 450 640 690 890 1040 ----
promotion value 320 200 190 30 ---- 260 260
add in hand (one) 15 50 60 80 90 220 230
exchange value 200 860 900 1280 1380 1780 2080
exchange promoted value 520 1060 1090 1310 ---- 2040 2340
p.s. exchange value = basic value * 2.
exchange promoted value = basic value * 2 + promotion value.
2.3 Sequence of move generation
In searching depth N position, the sequence of move generation is following.
If (depth_max - depth) >= 1, these move is generated.
- Capture opponent piece that move immediately before.
- Capture opponent pieces (if effective)
- Promotion piece.
- Regret move. ( explain 2.4 )
- Effective check( piece exchange is effective)
- Most high value piece run away if threaten. ( second doesn't consider)
If (depth_max - depth) >= 2, these move is generated.
- Threaten move (include fork)
- Discovered check.
- Drop Gold and Silver in front of opponent King.
- Discovered threaten move.
- Threaten pin piece. ( Pin piece can't move. If move, King ( or other piece)
is captured by Rook (or Bishop or Lance). )
- Drop Rook and Bishop in opponent's camp.
If (depth_max - depth) >= 3, these move is generated.
- Wild drop around opponent King. ( Drop piece in square that have many
friend and opponent Kiki.)
- Send off move. ( Sacrifice check. And if taken by King, defense piece is
captured.)
- Capture Silver, Gold, Bishop and Rook, even if not effective )
If depth <= 2, these move is generated.
- Pawn move in front of Rook and Lance.
- Sacrifice move and drop. (If taken, new capture and fork is effective.)
- Dangle ( drop a pawn before the target field, threatening promotion next)
- Strike ( drop a pawn right in front of an enemy piece )
- Sacrifice promotion of Pawn.
- Interpose (against enemy Rook and Bishop)
- Promoted pawn (and all) in enemy camp move sideways toward enemy King.
- Drop pawn in front of before move.
- Threaten against before move. Or gold and silver move toward before move.
- King move.
If depth == 2 and opening, these move is generated.
- Threaten pawn.
- Vanguard pawn.
- Random move. ( not include drop )
If depth == 1, these move is generated.
- Random move. ( not include drop )
- Check ( not consider value gain)
- Random pawn drop (under 15)
All move generation subroutine have a upper bound of move number.
And moves is picked up from a move that to be important.
And, the upper bound of number depends on the remainder search depth.
Program does not consider fork if search remainder is only one ply.
It only consider over 2 plies. For example, fork of King and Rook by Bishop
need 2 plies. 2 plies is drop Bishop, and King run away.
You may think that a move Bishop capture Rook can't consider only 2 plies.
It need 3 ply? Yes. But in practice, exchange evaluation routine of end node
is in place of it. ( Of course, certainty is not.)
In short, the move should consider if there is the remainder search depth to
achieve the move's aim.
The threaten move subroutine is made especially and carefully in all move
generations.
In YSS, when remainder search depth is over 3 plies, upper 5 threaten moves
is only made.
However, threaten moves reaches 10 or 20 moves occasionally. So picking up
sequence is important.
YSS is following.
- Fork by Lance, Knight, Silver, Gold, Bishop and Rook. Move is given
priority than drop.
- Threaten (from Rook to Lance) move. Move is also given priority than drop.
Especially, Gold and Silver drop for threaten Rook and Bishop, is evaluated
low. But Pawn drop is high.
YSS don't sort moves. Move sequence and generation sequence is same.
After generation, YSS only vanish same moves. ( However the last best move
is putted at first.)
The average number of move generation is 80 ( one depth), 40 ( 2 depth ),
20 ( 3 depth ), 6-13 ( over 4 depth ) in the middle and end game.
There is no upper bound number as whole.
In iterative deepening, if it takes 6 times time, YSS can search one ply over.
2.4 Null move and regret move generation
Regret move generation is defense purpose generation.
In selecting defense move, if silver will be captured for free, you can find
easy to protect it.
For example, threatening square that silver exist, or silver run away.
But if opponent rook sacrifice is effective ( if capture rook, king mate!),
you can't find to protect it easy. One ply search can't find rook sacrifice.
In other words, if you see only position ( not include searching), you can't
find defense move.
One of the methods of solving this is regret move.
First of all, program pass and get opponent best move.
And program generate moves to protect it.
In a word, program find an opponent most effective move when I idle (same
Null Move), and program protect it.
In reality, program pass and get best sequence. And in this sequence, if it
is own move, it is generated,
and if it is opponent move, a move to protect it is generated.
Figure 3 is shown as an example. It is Sente turn.
Figure 3
In this position if Sente pass, Gote 54 pawn and Sente bishop run away, and
76 rook will capture 77 knight.
If in this position 55 bishop does not exist, you find that 77 knight is
captured next. So you can easy find threatening move 77 square, ex. 78
silver or 68 gold.
Here I assume Sente passes.
In this case opponent best move is 54 pawn and ... capture 77 knight.
The best sequence will be PASS, 54 pawn, 46 bishop, 77 rook promote, 69 king.
In this sequence Sente moves is added the generation list, and moves to
protect Gote moves is added.
In this case, 2 moves (46 bishop and 69 king) is added, a move to protect 54
pawn ( nothing this case) and a move to protect 77 rook promote, for example
78 silver, 68 gold.
Then, program can find protect moves that can't find in one ply search.
Notice! These moves might be impossible for changing board if it is not the
move to protect immediate before move. Therefore, it is necessary to check
whether the move is a violation of the rule severely.
In an actual search, YSS passes all nodes without end node and get best
sequence. And in best sequence YSS don't generate to protect opponent move
over 3 depth. ( when root node, generate all.)
The reason for this is that the protect moves will be too much when the best
sequence is long ( 10 plies or more ).
This regret move generation also has the fault.
At first there is need to get opponent best move when pass.
Alpha-beta value must be reset -infinity and +infinity.
So the efficiency of the search worsens (The idea of Window can not be used.)
Moreover, the best opponent move might be always actually the not best
because YSS use alpha-beta value that is taken over from parent node without
root node.
For instance, alpha-beta cut has occurred by capture rook (but a ply mate
exist! in reality).
So program generate moves to protect capture rook, not a ply mate.
For using iterative deepening, I think this fault is less, but not complete.
2.5 Killer move
The best opponent move that is obtained by a pass will become ideal killer
move. However I don't use killer move now, because the necessity is not so
much for remembering all position's best move in big hash table.
3. Evaluation function
3.1 Judgement opening, middle-game and endgame
The evaluation function is divided into two (opening and middle-end game)
in YSS. Program judge before searching whether a present position is opening
or middle-end game. (Do not change during the search).
The standard of the judgment is as follows.
- Sum of both Sente and Gote hand (over lance) is more than three pieces.
- The piece more than silver (or promoted piece) invades the enemy's camp
(Friend's camp is too).
- The piece more than lance is threatened (enemy and friend).
When these three condition is approved, it is judged the middle-end game.
However, if it is less 10 moves from game start, it is opening.
Value of pieces is always constant in YSS. However its value increases and
decreases severely by the position in middle-end game.
3.2 Value of pieces
The value of pieces is Table 3.
Table 3: value of pieces (again)
Pawn Lance Knight Silver Gold Bishop Rook King
basic value 100 430 450 640 690 890 1040 ----
promotion value 320 200 190 30 ---- 260 260
add in hand (one) 15 50 60 80 90 220 230
exchange value 200 860 900 1280 1380 1780 2080
exchange promoted value 520 1060 1090 1310 ---- 2040 2340
p.s. exchange value = basic value * 2.
exchange promoted value = basic value * 2 + promotion value.
Exchange value is used when piece exchange. It is twice of basic value.
(Why? if piece is captured, board value is down. and opponent hand value up.
so twice.)
Exchange promoted value is twice of basic value and promotion value.
(You should think yourself!)
"Add in hand" in Table 3. shows one piece hand.
If you have 1 gold, 90 is added . If 2 gold , 90 + 40 is added.
So 1,2,3,4 is 90,40,10,0. Capturing same kind of pieces is less value.
3.3 Castle making in opening
Piece value is constant in opening.
Additional value ( the nearer the center of the board or opponent's king,
the higher value.) is a little (under 10% of the value of the pawn).
A main increase and decrease standard depends on "Increase and decrease table
for the castle making" and "Vanguard Pawn".
YSS don't use opening book at all. So YSS's opening is weak.
But I think computer should not use difficult opening that computer can not
understand. He can't play from the end of it.
YSS use "Pitfall method" (I called) in opening making castle.
YSS makes table that if gold and silver is in a certain position, it is +n
point. If YSS wants to make a piece move fast, the point difference of
square and square is bigger. So each pieces fall (move) in high value
difference order. And Yagura castle or Mino castle is made at last.
YSS makes this table for all pieces.
Actually YSS has this table for "Yagura", " Static Rook Bear-in-the-hole",
"Left(side) Mino", "Yamada System(57Silver Quick Attack)", "Aerial Fight",
"Ranging Rook", "Ranging Rook Bear-in-the-hole", "A castle in 2-(or 4 or 6)
piece handicap)", "undecided castle".
And what table YSS use is decided by random and opponent's rook position.
The increase and decrease by which the actual combat meaning is considered is
added to this "Pitfall" table.
For instance, the lance position lower, the value higher. The jumped knight
to the edge of board is low.
The gold and silver in a corner is big low. The rook in 7 rank is a little
low. And etc..
- Vanguard Pawn
Following description is seen from Sente.
Object of vanguard pawn is only Sente pawn in 3, 4, and 5 rank.
- If a pawn is in 5 rank and opponent pawn is in 3 rank, points is +1.
If there is no opponent pawn and my pawn don't threaten from friend,
+2 points. If threaten , +15 points.
- If a pawn is in 4 rank and it can promote next (the forward square
don't have enemy's threat.) is +100 points. If opponent pawn is in 2
rank, +20. If not, +40. If a pawn in 4 rank have friend threat, +10
additionally.
- If a pawn is in 3 rank, its value is low than in 4 rank.
In short, if a pawn is in 3,4,5 rank and opponent pawn is not in 1,2,3 rank,
pawn value is up.
The other pawn value is as follow.
If there is no pawn in same file that have rook, +35. And if enemy don't
protect its file by pawn, +30. If there is no pawn ahead of king, -15.
Because it is worse that exchange a pawn ahead of king in Yagura fight.
I think making castle in opening can be generalize in the future.
It is sure to become the balance problem between the concept of vanguard
and gold (and silver) position basically.
3.4 Middle-game and endgame
The evaluation function of middle and end game divides into three part that
is value of pieces, king safety and the increase and decrease by piece
position. Piece value is always constant. The big change elements is king
safety and piece position value. I don't care which turn do Black or White
have.
The each king position decide the increase and decrease by piece position.
If a piece is near friend(or opponent) king, value is up. If a piece is
far from both kings, value is down.
Table 4 shows White(Gote) piece value toward Black(Sente) king. It assume
that piece value is 100. If point is 50, piece value is half. It omit
minus X axis because of symmetry.
For instance, if Black king is in 69, and White gold is in 37, it is 114
(69-->(0,0) 37--->(3,+2)). Because gold value is 690, the added point
becomes 690* (114-100)/100=+96 points. It is 690*(75-100)/100=-172 points
when there is gold in 19 (69-->(0,0) 19--->(5,+0)).
--- Table 4 ---
Increase and decrease rate by relative position of Black piece toward White
king. It is symmetry for X axis.
0 1 2 3 4 5 6 7 8 (X distance)
+8 50 50 50 50 50 50 50 50 50
+7 50 50 50 50 50 50 50 50 50
+6 62 60 58 52 50 50 50 50 50
+5 80 78 72 67 55 51 50 50 50
+4 100 99 95 87 78 69 50 50 50
+3 140 130 110 100 95 75 54 50 50
+2 170 160 142 114 98 80 62 55 50 <--- Two above king is maximum.
+1 170 165 150 121 94 78 58 52 50
0 170 145 137 115 91 75 57 50 50 <--- This is center.
-1 132 132 129 102 84 71 51 50 50 Black king is in (0,0).
-2 100 97 95 85 70 62 50 50 50
-3 90 85 80 68 60 53 50 50 50
-4 70 66 62 55 52 50 50 50 50
-5 54 53 51 50 50 50 50 50 50
-6 50 50 50 50 50 50 50 50 50
-7 50 50 50 50 50 50 50 50 50
-8 50 50 50 50 50 50 50 50 50
(Y distance)
Table 5 shows Black piece value toward Black king.
Exceptionally pawn, lance and knight value is less than Table 5. And lance
and knight value are calculated by assuming that lance and knight is in
one rank up position.(Lance and knight maximum value is three above king.)
Finally piece value is decided by larger value from Black king or from
White king.
--- Table 5 ---
Increase and decrease rate by relative position of Black piece toward
Black king. It is symmetry for X axis.
0 1 2 3 4 5 6 7 8 (X distance)
+8 50 50 50 50 50 50 50 50 50
+7 56 53 50 50 50 50 50 50 50
+6 64 61 55 50 50 50 50 50 50
+5 79 77 70 65 54 51 50 50 50
+4 100 99 95 87 74 58 50 50 50
+3 116 117 101 95 88 67 54 50 50
+2 131 129 124 114 90 71 59 51 50
+1 137 138 132 116 96 76 61 53 50
0 142 142 136 118 98 79 64 52 50 <--- This is center.
-1 132 132 129 109 95 75 60 51 50
-2 121 120 105 97 84 66 54 50 50
-3 95 93 89 75 68 58 51 50 50
-4 79 76 69 60 53 50 50 50 50
-5 64 61 55 51 50 50 50 50 50
-6 56 52 50 50 50 50 50 50 50
-7 50 50 50 50 50 50 50 50 50
-8 50 50 50 50 50 50 50 50 50
(Y distance)
Figure 5 is made thus.
Figure 5: gold addition value by position
This figure shows the increase and decrease by the position of Black gold.
Value is added near both kings and value is growing especially in the upper
part of White king. (This feeling is restraining opponent king.)
If one ply search, program select dropping gold in two above opponent king
(attack) in place of dropping near friend king (defense).
In respect of Horse and Dragon, if its position is plus, value is added.
But if its position is minus, value in not added. Major piece(rook and
bishop) have big movement. So if they are far from battlefield, they are
working well.
If rook(dragon) is in enemy camp, addition value is much influenced its
position (obstacle from king to rook). If anchor pawn exists between opponent
king and friend rook, value is low.
The increase and decrease table for pawn, lance and knight is calculated from
the position of king before searching.
So if king moves while searching, table value will go wrong. Other piece
(Silver, Gold, Rook, Bishop, Promoted piece) are calculated correctly.
This is for speed-up.
King safety element is following.
- Wall gold(silver) is minus.
If king is in 4 or 3 file and king can not move 3 or 2 file, it is minus.
- If surrounding 8 square of king have opponent threatening,
-- If friend piece is in this square, and enemy threatening is ahead
(or same), minus is 1/4 of this piece value.
If friend threatening is ahead, minus is 1/8 of this piece value.
-- If square has no piece, and enemy threatening is ahead, -250.
If threatening is same, and enemy has piece that can be dropped this
square, -200. If no drop piece, -130. And another is -50.
These value is for king above square. Value falls by going below square.
- The piece that is pinned by enemy rook or bishop or lance, is minus.
For entering king, king value is up by nearer enemy camp.
For instance, the addition value form 1 step to 9 step in 1 file is
following.
Step 1 2 3 4 5 6 7 8 9
add 0, 0, 0, 150, 450, 900, 1300,1550,1600 (1 or 9 File)
3.5 Evaluation of end node
Evaluation of end node is following.
At first if there is check, program search more one ply unconditionally.
In another position, program find maximum value of capturing piece by next
move. And program adds this value to the static evaluation function value.
Additional value is piece exchange value. If a pawn is captured next turn,
+200 is added. And add in hand is added.
I don't consider stop searching depth is odd or even. If search depth reaches
depth limit, search stops and evaluation function is called.
I don't use singular extension (that is used in Deep Blue).
4. Search algorithms
4.1 Half ply extension
I used fixed depth alpha-beta search till YSS 6.0. But I have used iterative
deepening from YSS 7.0. The reason is that I want to try whether half ply
extension algorithm is effective.
Iterative deepening (maybe you have known in chess program) is not fixed depth
search, but increase depth search one by one.
At first, program runs one ply depth search, and found a best move. Second,
program runs two ply depth search. This time, program search from the best
move that is found in one ply depth search.
In the same way, program searchs 1,2,3,4,5, ... ,n-1,n ply depth search.
Program can search effectively with alpha-beta algorithm because of searching
from the best move that is found n-1 ply depth search.
This method is effective for time limit play. When time limit has come while
thinking n ply depth search, if program is searching first move(the best move
in n-1 ply depth search), program select this first move.
If searching second move, program select first move because program don't know
the correct value of second move. If searching third or over, and the best
move is changed, program select the now best move.
Half ply extension algorithm is a variation of iterative deepening.
When half ply extension is used, program searches the memorized best move at
first and depth max is added 0.5 ply only first move. Two 0.5 ply extension
make one (real) ply extension. So a move that is thought good is searched
deeper.
Figure 6 is shown as an example.
Figure 6: Three depth game tree of half extension algorithm
Fig.6 shows basic three depth search tree with half ply extension algorithm.
Each node has two branches. And left branch (thick line) shows best move.
The number (that is shown in node left side) shows depth max.
If program select left(best) node, depth max is add 0.5 ply. If program select
right node, depth max is not added.
If program select best move 3 times from root node(depth max = 3), depth max
is +0.5, +0.5, +0.5, so depth max = 4.5 .
If normal search, search stops this 3 depth. But in this case, program can
search continue because of 4.5 depth max.
If program select best move from this depth 3 node, depth max is 5.0 .
Program can search one ply again.
If program select best move from this depth 4 node, depth max is 5.5 .
This depth is 5, and depth max is 5.5. This doesn't reach 6. So program
stops searching this 5 depth.
On the contrary, if program select right branch 3 times, depth max is 3, not
adding. So program stops searching this 3 depth.
As a result, when basic n (=3) depth search, program can search plausible
branch 2n-1 (=5) depth in the maximum.
The feature of this algorithm is that time (number of end position) takes
only 2〜3 times in comparison with normal search. For instance, search
time takes only 2.35 times when basically depth max is 8, maximum is 15,
and branching factor is 20. Table 6 shows this.
Table 6: Time and maximum depth. Branching factor is 20.
Basic Time Maximum
Depth Depth
2 1.04 3
3 1.14 5
4 1.28 7
5 1.46 9
6 1.70 11
7 2.00 13
8 2.35 15
9 2.79 17
10 3.32 19
In the actual search, branching factor is about 6-80, and extend move is only
one move (best move) in all moves. Program check the hash table for finding
n-1 search's best move. If n-1 best move doesn't exist in hash table,
program have 2 ways. One is extension stop. In this case, node is end node.
Second, program restart iterative deepening from this node and find best move.
(multi iterative deepening) If depth_max = 7 and depth = 3, program change
depth_max = 4, 5, 6, 7.
If program find new best move, depth max is added 0.5 and program search this
new best again.
Why? because old best move have searched in (depth max + 0.5), and new best
move have searched only (depth max).
The most difficult problem is to test strength up by this half extension
method. In my now experiment (1998-03-25), the half extension program
win 249, lose 150, draw 1, against not use half extension. Winning rate is
0.62. Do you feel this is big or small? If my program use twice time,
twice's winning rate is about 0.6. three times is 0.75, fifth times is 0.88.
Ten times is 0.88 ( no big change from fifth).
Note:2003-02-19
Now YSS is using perfect half ply extension.
"Perfect" means if program finds ex-best move from hash table is not "best",
he searches this new best move by added +0.5 depth limit again.
And YSS also uses "Internal Iterative Deepening".
If YSS find there is no "hash" move in 5 left depths search, YSS searches
this node from 1 depth search to 5 depths search one by one.
This is done in all node. Only PV node "internal iterative deepening" was
no good for YSS.
This requres three times thinking time, but it became stronger.
I think it's important how deep it can search when best move is changed.
Table 7 shows the rate of depth by which the evaluation function is called.
This is made by YSS self play. All rate is sum for white and black.
In opening, search stop in short depth, so main depth rate is from middle and
end game. 60 percent or more exceeds basic 8 depth. The maximum depth is 20.
This is because of king check extension and 2 ply extension for horizon
effect.
-- Table 7 -- the depth rate that evaluation function is called.
depth: %
1: 0.0:
2: 0.0:
3: 0.2:
4: 0.5:
5: 1.2: **
6: 3.3: ******
7: 10.7: *********************
8: 21.0: *****************************************
9: 25.7: ***************************************************
10: 20.3: ****************************************
11: 10.1: ********************
12: 3.9: *******
13: 1.7: ***
14: 0.9: *
15: 0.4:
16: 0.1:
17: 0.0:
18: 0.0:
19: 0.0:
20: 0.0:
Game end 140 moves. Basic depth max is 8.
A move search is permitted for 40 second.
All search node is 78436893.
All thinking time is 2250 minutes. (CPU Alpha500MHz).
I don't know extension rate 0.5 is best.
Another idea is change rate from 0.1 - 0.9, and extended another move in
addition to best move or shortening.
Figure 7 and Figure 8 show the max function of simple alpha-beta search
and the min function of YSS that use half ply extension.
Figure 7. - Max function of simple alpha-beta search -
int f_max( int alpha, int beta )
{
if ( depth >= depth_max ) return(evaluation value);
making moves
for ( i=0 ; i < number of moves ; i++ ) {
go ahead a move
depth++;
k = f_min( alpha, beta );
go back a move
depth--;
if ( k > alpha ) alpha = k;
if ( alpha >= beta ) return(alpha);
}
return(alpha);
}
Figure 8 - Min function of YSS that use half ply extension -
int f_min( int alpha, int beta )
{
Check the hash table. (left search depth)
If already searched or high limit <= alpha, return value , best move,
and search depth of value.
if ( depth >= depth_max && King is not check ) {
Set of search depth of value.
Call evaluation function. And add next capturable piece value.
}
if ( King check ) defense move is generated.
else {
Check 1 ply mate.
Call check mate program that depend on left search depth.
Generate move that capture opponent piece that move immediately
before.
Generate move that capture pieces.
Regret move. ( explain 2.4 )
Generate another moves.
}
Cut same move.
Set n-1 best move to first move.
Check 2 ply extension for Horizon Effect in this position.
for ( i=0 ; i < number of moves ; i++ ) {
Go ahead a move.
depth++;
if ( i==0 ) depth_max += 0.5;
k = f_max( alpha, beta );
if ( k < beta && 2 ply extension flag ) {
depth_max += 2;
k = f_max( alpha, beta );
depth_max -= 2;
}
Go back a move.
depth--;
if ( k < beta ) {
beta = k;
Copy search depth of value.
Copy best sequence.
}
if ( i==0 ) depth_max -= 0.5;
if ( alpha >= beta ) {
Set hash table.
return(beta);
}
}
If there is no move to protect King check, drop pawn mate is checked.
if ( Is beta value is renewal once? ) Set beta value to hash table.
return(beta);
}
4.2 Transposition table (Hash table)
YSS use Hash table in Tume search and actual search. End node is not
registered in both searches. I use Open Address method. And re-hash times
are 16. Re-hash sequence is fixed random sequence. ( This is effective in
Open Address method.)
If YSS use 75% hash table, YSS judge that hash table is full, so registration
stop at 75%.
I use 64 bit value in hash code. At first, I used 32 bit value.
But in 32 bit, 2 or 3 misconceptions occurred frequently at 300,000 position
search. This was very reliability. So I changed 64 bit.
In my rough estimate, if using 64 bit, the probability that one misconception
will occur is 1% at during a day searching.
( Search speed is 10,000 node/sec. And all position in a day search is about
2^32 positions.)
Random number is made by the multiplier combination method.
( a=16807, m=2^32-1 )
In main thinking routine, YSS search Tume search at first. And only position
that is TUMI (checkmate) is registered for main search hash table.
I separate main search hash table and Tume search hash table. And in Tume
search, I separate Black Tume and White Tume. Why? This is for Gyaku Oute
position. ( Black check white king, but next white defense move is check
to black king! This makes confusion.)
Whether now turn is black or white is shown by reversing hash code.
If two pass, hash code returns original. (0x01 -> 0xfe -> 0x01)
Table 8. Value registered in hash table
1. Hash code 64 bit
2. Hand code 32 bit
(Each kinds of number of white hands. Black hands is none.)
3. Evaluation value for main search
( upper bound, or lower bound, or accurate value)
4. Flag that whether (3.) value show upper or lower or accurate.
5. Search depth ( How depth is searched from this position?)
This is shown by (real depth * 256).
If 3.5 depth is searched, the value is 3*256 + 128 = 0x0380.
6. Relative search depth for Black Tume.
7. Value for Black Tume.
( TUMI(checkmate), UTI-FU-TUME(drop pawn checkmate),
FUMEI(unknown), KIRE(can not checkmate) )
8. Relative search depth for White Tume.
9. Value for White Tume.( TUMI, UTI-FU-TUME, FUMEI, KIRE )
10. Best move
4.3 Two type of Horizon effect
In computer shogi (of course, in computer chess), the program often play some
meaningless striking pawn or strange moves that will be only loss of tempo
or loss of pieces.
This is called "Horizon effect".
Figure 9. Horizon effect is apt to happen.
Figure 9 is YSS - Kiwame at 4th Computer Shogi Championship in 1993.
This is Black turn.
Black king (YSS's king) is checkmate by next White drop 58 Gold.
The best move will be 57 Silver with capturing 57 pawn. But if this move,
87 Horse (check), 58 King, and 65 Horse with capturing Knight. So Black
can't play 53 Knight promote with capturing Rook!
If human, he will think "I have no choice but to play 57 Silver."
This is good. But if computer, he doesn't think so.
YSS's next move was 62 drop Kin. Why? At this time YSS's search depth was
fixed 6 plies. And in 6 depth, YSS could not search check to my king from
enemy.
YSS's thought was that 62 Gold, 82 King, 72 Gold, 72 Do Gold, 53 Knight
promoted. 53 Knight was 5 depth, so YSS didn't search next 58 Gold drop,
and he thought this line was my Rook gain!
Thus, by continuing check, computer pushes out enemy's effective move from
his search limit.
Actual game was played following.
62 Gold, 82 King, 71 Silver, 71 Do Gold, 72 Gold, 72 Do Gold, 57 Silver.
The most fatal move in this line was 71 Silver (check).
62 Gold (check) and 72 Gold (check) were not profitable moves, but not fatal
moves. (If 62 Gold - Do 62 Gold, Do 62 Knight promote - Do King - 53 Knight
promote. This was good for black.)
But 71 Silver was blunder. This was only loss of Silver.
And for this one move, position changed from a little better to very bad.
The reason why played 71 Silver was same as 62 gold.
The problem is here. When Horizon effect happens by a not profitable move
(check or etc.), it is not fatal.
But if he play a loss of piece to protect own one ply checkmate, it is fatal.
If Horizon effect happens without loss of piece (ex. effective check or
threaten move without loss of piece),
I call this "Slight injury Horizon effect", and I don't deal with it.
(To tell the truth, I don't know how to deal with it...)
The important problem is "Heavy injury Horizon effect".
This plays a loss of piece actually.
I wanted to solve "Heavy injury Horizon effect".
As a result, my conclusion is following two.
1. Don't search such a violent move!
2. It is necessary to make the computer understand a useless attempt after
all when a violent move looks effective.
The first method is applied to deeper node.
It is important that program should not search violent move in deeper node.
In deeper node, program should search only a few moves that is clearly
effective. (runaway or capture)
To solve the second problem, YSS use +2 plies extension.
At first, program search by normal depth limit.
If program play sacrifice move, and value is updated against capturing
sacrifice piece (Horizon effect happen?), depth limit is added 2 plies for
this sacrifice move and capture.
For example in Figure 9, program searchs 79 Silver - Do 79 Gold line. Horizon
effect was happened, and value was updated. So program research 6 depth
limit search after this 79 Silver - Do 79 Gold. (8 depth limit search from
root node.)
Simply, search space is twice. So thinking time is twice too.
If capturing sacrifice move is not only one, program research all capturing
moves.
The best move after 2 plies extension seems root node's best move.
At first I picked up the root best move from hash table, and I only
searched this best move after 2 plies extension for speed up.
But this was not stable. Why? Because this best move was influenced Horizon
effect too. It was often "striking pawn".
Now YSS only use this 2 plies extension at depth 3 and 4.
So YSS play meaningless (sacrifice) move only depth 1 and 2.
By this method, YSS doesn't play "Horizon effect" very much in inferior
position.
4.4 Breakthrough repetition moves (successive check)
I judge repetition moves by preserving all game record position's hash code.
If same position and my hands is less, value -= 5000.
(This is only loss of piece.)
If same position and my hands is same and enemy king is check, value -= 1000.
(This is maybe successive checks.)
If same position and my hands is same, value -= 200.
(I want to break loop.)
5. Checkmate problem (Tsume shogi)
5.1 Checkmate problem
YSS use iterative deepening and hash table in Checkmate problem.
However, it is a routine extremely simplified.
I think YSS only can mate position that will be seen in actual game.
Art of checkmate problem is out of my idea.
So many violence check move is cuted.
1. If piece loss sum is over 2 rook from counting start position, search
stops.
2. Don't search victim interpose move (also drop).
3. If before move is discard move and enemy capture it, don't search discard
move. (Don't search continuous discard move!)
4. Don't search drop move of rook, bishop, and lance. If its position is
over 4 space from enemy's king.
5. If rook and bishop and pawn can promote, it promote.
I don't think check moves order. But in king run move, if it can capture
check piece, searching its move first is effective.
For speed up, I made the last one ply check mate.
At first, YSS search king's around 8 space. And if enemy's threat is not
in each space, movable bit flag is on.
Next, if drop check move, (YSS have made that its drop check move can fill
which king's 8 spaces.) YSS check this fill bit flag AND movable bit flag.
(This AND is '&'. Of course, I believe you know. :-) )
For this method, YSS can search one ply drop mate soon. But in actual, this
idea was bug.
Figure 10. Mistake of one ply drop mate
Figure 10 shows a mistake of one ply drop mate.
In this case, YSS thought 22 drop Silver, and mate! ...No, this is wrong.
King can move 12 square. (Promoted rook line is vanished!)
So now YSS is testing by dropping piece in actual board after bit test. One
ply move check complicate board position. So YSS test these moves in actual
too.
For these extreme cut off, YSS can find over 20 plies check mate problem in
only 10000 node search. Of course, it may be not correct mate because YSS
doesn't search some interpose moves.
5.2 Brink mate
....next is now translating.
6. Reference game record
Black: Kanazawa Shogi 2
White: YSS 7.0
1.S-4h P-3d 2.P-2f G-3b 3.P-7f Bx8h+ 4.Sx8h S-2b
5.S-7g S-3c 6.P-6f S-6b 7.G-7h G-5b 8.K-6i K-4a
9.G-5h K-3a 10.K-7i G5b-4b 11.P-5f P-6d 12.S-5g P-8d
13.P-2e K-2b 14.S-4f P-4d 15.S-5e S-6c 16.K-8h P-7d
17.G5h-6g N-7c 18.P-3f P-4e 19.N-3g P-3e 20.Px3e P-5d
21.S-4d N-8e 22.Sx3c+ G4bx3c 23.S-8f S*3f 24.S*4h R-9b
25.B*1h Sx3g+ 26.Sx3g N*4b 27.S-2f G-4d 28.S*5c G4d-4c
29.Sx4b= Rx4b 30.N*3d Gx3d 31.Px3d S-5b 32.P-7e Px7e
33.Sx7e P*7d 34.Sx7d N*7e 35.G-7f S*6g 36.Gx7e B*3i
37.Gx6g Bx2h+ 38.S*5a R-4c 39.N*3e R-4d 40.P-2d Px2d
41.P*2c Gx2c 42.Nx2c+ Kx2c 43.G*3e R-4a 44.G*4b +Bx1i
45.Gx5b R*2h 46.S*7h Rx2f+ 47.Gx4a +Rx3e 48.B-2g +B-2h
49.B-1f K-1d 50.P-3c+ S*2e 51.P*2f +Bx1g 52.Bx2e Px2e
53.R*3d +Rx3d 54.+Px3d K-1e 55.Sx8e Px8e 56.N*2i +B-2g
57.R*2b Kx2f 58.Rx2a+ R*3i 59.N*1i +B-1h 60.S*3g K-1e
61.+R-2d K-1f 62.P*1g +Bx1g 63.+Rx2e Kx2e 64.Nx1g K-1f
65.S-2h R-2i+ 66.B*2e K-1e 67.S-2g S*7i 68.K-7g B*5i
69.G-6h Bx6h+ 70.K-7f G*8f 71.Px8f +Bx8f 72.K-6g S-6h+
73.K-5g +R-5i 74.G*5h +Rx5h 75.quit
7. Solve the shogi equation
8. Epilogue
P.S.
Thank you for advice and reminder :-).
Nobuhiro Yoshimura
Jeff Rollason
Pauli Misikangas
Reijer Grimbergen's "A Basic Shogi Vocabulary" in his Homepage
And all shogi and computer shogi funs.