AEFGE: Asymmetric Evaluation function with Genetic Evolution

[stegemma]

I'm trying this new kind of dynamic evaluation function. In Satana, i make the parameters evolve with a genetical algorithm. I use two sets of parameters: one for white and one for black and both are evolving during the game. The program, before to start an almost standard alfabeta, will play a tourney against two sets of "players", each one with a different set of parameters. One set is the white team, the other is the black team. The genetical algorithm evolves both sets, with simple genetical crossing of any player (better one will merge with some random other player). At end of training set of matches, the white and black parameters are used in alfabeta evaluation function. Obviously the tourneys are played at low ply, because all the stuff are done during engine playing time, not as a training session.

It's interesting ihow the parameters tend to grow, do to the asymmetric evaluation function that depends on the fact that white and black use different sets. The first version have the amusing goal that parameters all tend to grow up to the maximum choosen by me (2 pawns value). This was the right thing to do, by the genetical algorithm, because it should get the maximum value from position... instead of getting this goal with the right proportion between parameters, because opponent uses a different set, the result was that the better way to grow result was to grow all parameters! This means that Asymmetric Evaluation Function (genetical or not genetical) should be handled differently from symmetric one. In my opinion, i think that a third evaluation function should be used to evaluate the goodness of any of the two evaluation functions derived from the two different sets of parameters. Number of victories in any tourney could be a good value of the goodness of any "genetic player" but with a low ply search the most of the game ends in a draw, so this value is useless. I'm trying a new kind of alfabeta that handles the asymmetric evaluation functions, as a possible solution.

[Daniel Shawul]

Do you just evolve parameters for white and black separately? I think asymmetric evaluation is defined as the use of different parameter values for the side to move and opponent (not just hardwired white/black parameters). I do not find optimizing with genetic algorithms that exciting because it takes a lot of games to remove associated noise. Most just tune a selected few parameters with gradient descent algorithms. Adding asymmetry to tuning doubles the number of parameters and I am not sure if it is worth the effort. For one alpha-beta is a zero sum game and as such asymmetry messes up with it (hash tables f.i). With the two ply games you are doing, asymmetries may actually show up since it is better to be speculative with such low search depth.

[stegemma]

The genetic algorithm lets evolve white and black parameters and then use them in the full alfabeta search. So they are not hardwired but evolves depending on the position reached time by time, during the game. It is the same as "side to move" vs "opponent" parameters, because at any move we know the color of the engine.

I would like to experiment various approach to the evaluation function, not just tuning parameters. A first try involved the use of a "macro language" for chess, that evolves with the GA. It was interesting but too many slow. I've used a stack where the GA puts command and values. The commands were simply AND/OR/XOR/NOT and so on and the values were taken in part from the bit board and in part from predefined C functions. I wish to try a mixed approach, simplifying the macro language to make it faster.

[stegemma]

Here's the very first Satana game. I play with white and Satana with black. The level was 6 plyes plus a simple quiescence; there are no iterative deepening, null moves, transposition tables and so on. The genetic plays 8+8 players teams, with 64 tourneys "all vs all", with a level of 2 plyes plus QS.

At move 33 i've make a mistake then i've choose to see if Satana could win... and it does.

It is not a very interesting game but gives me some useful information on how to make a better evaluation function.

PS: do you like the Satana icons? (is the one in my profile)

Code: Select all

1.e4 d5 2.exd5 Qxd5 3.Nf3 g5 4.Nc3 Qe6+ 5.Be2 f6 6.d4 a6 7.O-O h6 8.Re1 
Qd6 9.Bc4 e6 10.d5 e5 11.Nd4 h5 12.Ne6 Bxe6 13.dxe6 Qxd1 14.Rxd1 g4 15.Nd5
Bd6 16.Be3 Kd8 17.Bd3 Kc8 18.Bf5 Kd8 19.c4 Nc6 20.a3 Na5 21.Rac1 Nb3 22.
Rc3 c6 23.Nxf6 Nd4 24.Bxd4 exd4 25.Rxd4 Nxf6 26.Rxd6+ Ke7 27.Rcd3 c5 28.
Rb6 Rhb8 29.Kf1 Ne8 30.Rd7+ Kf6 31.Rf7+ Ke5 32.Bg6 Nd6 33.Rd7 Nxc4 34.Bxh5
Nxb6 35.e7 Nxd7 36.Bxg4 Nf6 37.Ke2 Nxg4 38.h3 Nh2 39.f3 a5 40.Kf2 Re8 41.
Kg1 Nxf3+ 42.gxf3 Rxe7 43.Kg2 Rf7 44.Kg3 Raf8 45.Kg4 Rg7+ 46.Kh5 Rh8#