Optimizing evaluation functions

[Chessnut1071]

Most attempts at assigning optimized weights to game metrics use ELO scores to determine the magnitude or priority of a particular metric when selecting the best move. Although this method is effective, it's not optimum. For example. Assume we are just looking for a known checkmate in a 10-ply, or 5-move checkmate. Using 10 5-move mate chess puzzles from Classical Chess Puzzles, we want to find an algorithm which has the fewest engine calls and consequently the minimal time to solution, depending on the speed of your engine.

The average moves in those 10 puzzles are 42 moves for white and 28 moves for black. At 10-ply, we are looking at (42x28)^5 = 2,249,224,179,093,376 possible moves. Applying alpha beta we can reduce that number to 1/2 of 941,965,711, a significant reduction from brute force, but, no where near the reduction that's necessary. So, we apply a Zobirst hash, reducing the number to 1/2 of 469,517,202, a significant improvement but no where near the improvement we need. Next we apply a simple algorithm with 6 metrics, 3 for white and 3 for black. The metrics are simple, number of check moves, the material consequence of the move and, the best one of all, previous success of failure on prior moves by ply. Optimizing the weights on those 6 metrics now yields only 1,163,033 engine calls, or less than a minute assuming your engine can solve around 20,000 positions/second. For those interested the optimized weights are: white: 31.331, 2,906, 42,796 ; black: 0,003, 0,723, 130.907.

The trick to finding the metric weights is a modified Hooke and Jeeves optimization, especially effective at optimizing evolutionary systems. The idea is to apply the optimization to actual game metrics from common openings and defenses. Instead of using ELO and let the computer play itself, I used Grandmaster games and minimized the number of moves that differed from the grandmaster. This method may be more than competitive even at 37-ply against programs like Stockfish and Fritz.

[Ferdy]

Next we apply a simple algorithm with 6 metrics, 3 for white and 3 for black. The metrics are simple, number of check moves, the material consequence of the move and, the best one of all, previous success of failure on prior moves by ply. Optimizing the weights on those 6 metrics now yields only 1,163,033 engine calls, or less than a minute assuming your engine can solve around 20,000 positions/second. For those interested the optimized weights are: white: 31.331, 2,906, 42,796 ; black: 0,003, 0,723, 130.907.

Could you describe more about the following?

previous success of failure on prior moves by ply

[Chessnut1071]

Next we apply a simple algorithm with 6 metrics, 3 for white and 3 for black. The metrics are simple, number of check moves, the material consequence of the move and, the best one of all, previous success of failure on prior moves by ply. Optimizing the weights on those 6 metrics now yields only 1,163,033 engine calls, or less than a minute assuming your engine can solve around 20,000 positions/second. For those interested the optimized weights are: white: 31.331, 2,906, 42,796 ; black: 0,003, 0,723, 130.907.

Could you describe more about the following?

previous success of failure on prior moves by ply

Hi Ferdy
That’s actually the best and most efficient metric, with respect to time, you can use on checkmate solutions. It’s easy to implement.
Define a matrix Index[np, nr] where np is the maximum ply and nr = 2048, or 32*64 (piece number * square). For example, if move Ra4 on ply 9 results in a checkmate, Index[9,1063] = Index[9, 1063) + 1. Subtract 1 if it did not result in a checkmate. Then, when you prioritize the best move simply add the Index score multiplied by the optimized weight to your evaluation function.

[Ferdy]

Next we apply a simple algorithm with 6 metrics, 3 for white and 3 for black. The metrics are simple, number of check moves, the material consequence of the move and, the best one of all, previous success of failure on prior moves by ply. Optimizing the weights on those 6 metrics now yields only 1,163,033 engine calls, or less than a minute assuming your engine can solve around 20,000 positions/second. For those interested the optimized weights are: white: 31.331, 2,906, 42,796 ; black: 0,003, 0,723, 130.907.

Could you describe more about the following?

previous success of failure on prior moves by ply

Hi Ferdy
That’s actually the best and most efficient metric, with respect to time, you can use on checkmate solutions. It’s easy to implement.
Define a matrix Index[np, nr] where np is the maximum ply and nr = 2048, or 32*64 (piece number * square). For example, if move Ra4 on ply 9 results in a checkmate, Index[9,1063] = Index[9, 1063) + 1. Subtract 1 if it did not result in a checkmate. Then, when you prioritize the best move simply add the Index score multiplied by the optimized weight to your evaluation function.

Thanks.