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)