small update - search strategy and performance

Thanks to Deutsche Bahn I had an extra hour to do some small improvements on hiyace today. I implemented a minimax-strategy to determine the next move, basically that means the engine makes its assumption on the best possible move based on what it thinks would be the best move its opponent could make or as wikipedia puts it:

"A minimax algorithmis a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximizes the minimum value of the position resulting from the opponent's possible following moves. If it is A's turn to move, A gives a value to each of his legal moves."

Unfortunately time and computing power are limited, so in reality this will get us a search depth of only a couple of moves in an agreeable amount of time. With an average of 20 different possible moves per ply we get a steep exponential growth that without further optimization results in about 20^n (n = number of plies) positions that have to be evaluated - there definitely is room for improvement, perhaps Alpha-beta pruning will give us some edge her.

To get an idea what that means performance-wise, I have programmed a small benchmarking utility, that delivers the following results (note that absolutely no code-optimization has been done so far) on my machine (Core2Duo, 2,4 GHz, currently utilizing only one core): 



Please be patient...


10 ########################
09 ########################
08 ####RbNbBbQbKbBbNbRb####
07 ####PbPbPbPbPbPbPbPb####
06 ####................####
05 ####................####
04 ####................####
03 ####................####
02 ####PwPwPwPwPwPwPwPw####
01 ####RwNwBwQwKwBwNwRw####
00 ########################
01 ########################
   # # A B C D E F G H # #

Positions evaluated: 197281 in 00:00:03.2921186, that's 59925 positions/sec.

hit Enter to quit...

You can download the benchmark from here. (Tested on Ubuntu 10.4 with Mono 2.4.4 and Windows 7)

simple move-evaluation

I have added the a simple function that evaluates each possible move and selects the move with the best result. This is done by assigning a value to each piece (white pawn = 1, black pawn = -1, white knight = 3, black knight =-3...) and then building the sum of everything that is left on the board.
Right now the evaluation depth is set to one half move for debugging purpose, meaning that the evaluation function only takes into account the pieces it sees on the board and doesn't care about what happens after the next moves. This provides for a rather crude and greedy game-play, though it's definitely an improvement over selecting the next move at random.
Once I'm happy with it and some bugs are ironed out I will increase the evaluation depth by calling the evaluation function recursively. It will be interesting to see how everything performs at this level.
Strategic and positional knowledge  is an entirely different matter - I'll save that for some later time :)
Here is a debug output:




Possible moves: 17
E8-D7: Score -1
E8-D8: Score -1
E8-F8: Score -1
E8-F7: Score -1
E7-E6: Score -1
E5-E4: Score -1
E5-E3: Score -6
E5-E6: Score -1
E5-D5: Score -1
E5-C5: Score -1
E5-B5: Score -1
E5-A5: Score -1
E5-F5: Score -1
E5-G5: Score -1
E5-H5: Score -1
D3-E2: Score -2
D3-D2: Score -1
10 ########################
09 ########################
08 ####........Kb......####
07 ####........Pb......####
06 ####................####
05 ####........Rb......####
04 ####................####
03 ####......PbRw......####
02 ####........Pw......####
01 ####........Kw......####
00 ########################
01 ########################
   # # A B C D E F G H # #
Best move: E5-E3: Score -6

update

I spent some time on hiyace yesterday, here is where we are:

• moves for all pieces implemented (no castling, en passant and pawn promotion yet, so pawns just sit there if they reach the opposite side of the board)
• check detection

So far the engine is capable of actually playing a complete game. Moves are selected at random from the number of possible moves. After some debugging, no pieces leave the board and black pawns now move from row 7 towards row 1 ;)

Total time spent so far: 6 hrs

The next thing I'll be working on are a basic move evaluation algorithm and basic support for UCI.

here is the first "game":

hiyace 0.01 vs hiyace 0.01

  0. G2-G4 - E7-E6 

  1. F2-F4 - G8-H6 

  2. D2-D3 - F8-C5 

  3. D3-D4 - D8-H4 

  4. E1-D2 - A7-A5 

  5. G1-F3 - F7-F6 

  6. B1-C3 - H4-G5 

  7. A2-A4 - C7-C6 

  8. D2-D3 - F6-F5 

  9. D4-C5 - G7-G6 

 10. H2-H3 - E8-E7 

 11. B2-B3 - H8-F8 

 12. E2-E3 - B8-A6 

 13. G4-F5 - A6-C5 

 14. D3-E2 - G5-F4 

 15. H1-G1 - F4-F5 

 16. G1-G2 - H6-F7 

 17. F3-E5 - D7-D6 

 18. D1-D3 - F5-D3 

 19. C2-D3 - B7-B5 

 20. E5-G4 - C5-E4 

 21. B3-B4 - D6-D5 

 22. C1-B2 - E7-D7 

 23. A1-A3 - C8-B7 

 24. A3-A1 - C6-C5 

 25. G4-H2 - F7-D8 

 26. A1-E1 - D7-C6 

 27. G2-G5 - F8-F5 

 28. G5-G2 - E6-E5 

 29. B4-A5 - F5-F7 

 30. E1-D1 - F7-D7 

 31. B2-A1 - E4-G3 

 32. E2-F3 - D8-F7 

 33. F3-G3 - G6-G5 

 34. G2-E2 - D7-E7 

 35. C3-A2 - H7-H5 

 36. D1-D2 - B5-B4 

 37. E2-E1 - F7-D8 

 38. D2-F2 - E5-E4 

 39. F2-B2 - E7-E8 

 40. F1-G2 - E8-E6 

 41. H2-F1 - C6-D6 

 42. B2-C2 - B7-C6 

 43. A2-C1 - E6-G6 

 44. A5-A6 - D6-E7 

 45. G3-H2 - A8-C8 

 46. A1-G7 - C6-A8 

 47. D3-E4 - E7-E6 

 48. G7-H8 - C5-C4 

 49. H2-H1 - C8-B8 

 50. H8-G7 - A8-C6 

 51. C1-E2 - C6-D7 

 52. E2-C3 - B8-B5 

 53. H1-H2 - D7-C8 

 54. A6-A7 - C8-B7 

 55. G7-H8 - E6-E7 

 56. E1-C1 - G6-G7 

 57. C3-D5 - E7-E8 

 58. C2-B2 - D8-C6 

 59. A4-B5 - G5-G4 

 60. B2-B1 - G4-H3 

 61. G2-H3 - G7-G3 

 62. D5-B4 - G3-G8 

 63. H8-E5 - E8-F7 

 64. B4-A2 - G8-G3 

 65. E5-C7 - F7-F8 

 66. F1-G3 - F8-F7 

 67. C1-F1 - F7-G6 

 68. H3-G2 - G6-H6 

 69. B1-B3 - C6-A7 

 70. F1-A1 - B7-A8 

 71. A1-H1 - A8-C6 

 72. G3-E2 - C6-B7 

 73. E2-D4 - H6-G7 

 74. C7-E5 - G7-G6 

 75. H2-G1 - G6-F7 

 76. G2-F1 - F7-G6 

 77. F1-E2 - C4-C3 

 78. B3-B1 - A7-C6 

 79. B1-F1 - G6-H6 

 80. H1-H4 - C6-A7 

 81. E2-H5 - A7-C8 

 82. D4-B3 - C8-B6 

 83. G1-G2 - B7-A6 

 84. G2-H3 - B6-D7 

 85. E5-H2 - H6-H7 

 86. F1-F8 - D7-F8 

 87. H2-G1 - F8-G6 

 88. B3-C5 - H7-H8 

 89. C5-A4 - A6-C8 

 90. H4-G4 - C8-F5 

 91. A2-C1 - G6-H4 

 92. A4-B2 - H4-G6 

 93. E4-E5 - G6-E7 

 94. C1-A2 - C3-C2 

 95. H3-H4 - C2-C1 

 96. A2-B4 - E7-G8 

 97. G4-G5 - F5-H3 

 98. G1-F2 - H3-F1 

 99. E5-E6 - F1-E2 

100. H5-F7 - H8-H7 

101. F2-E1 - E2-B5 

102. G5-G8 - B5-D7 

103. G8-F8 - D7-E6 

104. F8-E8 - E6-G4 

105. B4-C2 - G4-H5 

106. E8-D8 - H5-G4 

107. D8-G8 - G4-F3 

108. E1-C3 - H7-H6 

109. G8-G4 - F3-G4 

110. E3-E4 - G4-E2 

111. B2-A4 - E2-F3 

112. H4-H3 - F3-H1 

113. C2-D4 - H1-G2 

114. H3-H4 - H6-H7 

115. H4-G4 - G2-H3 

116. G4-F3 - H3-C8 

117. A4-B2 - C8-H3 

118. D4-C6 - H3-G4 

119. F3-G2 - G4-E2 

120. C6-A7 - E2-D3 

121. F7-H5 - H7-G8 

122. G2-F2 - D3-B5 

123. C3-F6 - B5-C6 

124. F2-E3 - C6-D5 

125. B2-A4 - D5-B3 

126. F6-H8 - B3-A2 

127. H8-E5 - A2-C4 

128. A4-C3 - C4-A6 

129. E5-D4 - G8-H7 

130. E3-F2 - A6-B5 

131. C3-B1 - B5-F1 

132. D4-G7 - F1-E2 

133. A7-C6 - E2-B5 

134. C6-D4 - B5-A6 

135. H5-D1 - A6-F1 

136. D4-F5 - F1-E2 

137. F2-G1 - E2-D1 

138. G7-H8 - D1-G4 

139. B1-A3 - H7-G8 

140. A3-B5 - G4-H3 

141. B5-A7 - G8-H8 

142. A7-C6 - H3-F1 

143. C6-A7 - F1-D3 

144. A7-C6 - D3-B1 

145. F5-E3 - B1-A2 

146. E3-C4 - H8-G8 

147. E4-E5 - G8-F8 

148. C4-D6 - F8-G8 

149. E5-E6 - G8-H7 

150. D6-B7 - A2-C4 

151. C6-D4 - C4-B5 

152. D4-C6 - H7-G8 

153. G1-F2 - G8-H8 

154. B7-D6 - B5-E2 

155. F2-E1 - H8-G8 

156. D6-B5 - E2-D3 

157. B5-D4 - G8-H7 

158. C6-E5 - D3-C2 

159. E1-F2 - C2-E4 

160. F2-E2 - E4-C6 

161. E2-D2 - C6-A4 

162. D2-E3 - A4-B3 

163. D4-F5 - B3-E6 

------------------

         1/2 : 1/2

10 ########################

09 ########################

08 ####..Kb............####

07 ####................####

06 ####........Bb......####

05 ####................####

04 ####............Kw..####

03 ####................####

02 ####..........Nw....####

01 ####................####

00 ########################

01 ########################

   # # A B C D E F G H # #