Genetical tuning

[stegemma]

I've done some try with the genetical tuning of the evaluation function in Satana, some that gives only garbage someone interesting. First of all: starting from random values takes too many time and gives no efficient result. The next try was to start from one half of the population with hand typed values, those that already works almost well. This second test seems to gives valid and interesting results (i?ve changed the algorithm itself too).

The actual algorithm, after 15 iterations, shows that the values that I've wrote are almost the best but of 3. The interesting part is that those 3 parameters are all related to rook (in 7th rank, on open column and so on) and this could means that the algorithm has found that rook positioning was the wrong part of my evaluation.

The actual code for the genetic algorithm does this:

Code: Select all

* at start
- creates N players
- assigns standard value to N/2 players, random values to the other

* play a match between any couple of players
- add 1 to the score of the winning player
- add -1 to loser
- 0 if draw

* at the end of any match:
- genetically cross N/4 players with another random player, but the last one
- set random values to the last player
- cross the last player with the first one
- cross the last player with another random one

(cross means assigning first (or last) random parameters of player b to player a)

[stegemma]

Here's some generation of the algorithm:

Code: Select all

#----------------- generation 0																					
0	1	Iconoclast'	7	7	10	1	20	4	1	5	2	5	8	1	8	10	10	20	3	1	5
0	2	Lucky Man'	6	7	10	1	20	4	1	5	2	5	8	1	8	10	10	20	3	1	5
0	3	Eruption'	5	7	10	1	20	4	1	5	2	5	8	1	8	10	10	20	3	1	5
0	4	Tarkus'	-4	55	11	83	0	67	24	90	97	25	53	51	94	103	53	34	43	5	12
0	5	Mass'	-5	55	70	58	63	15	97	15	35	72	11	36	48	19	99	77	46	65	97
0	6	Stones of Years'	-9	20	2	90	41	63	75	17	64	20	73	40	35	36	95	0	101	72	2

#----------------- generation 10				7	10	1	20	4	1	5	2	5	8	1	8	10	10	20	3	1	5
10	1	Tarkus'	12	7	10	1	20	4	1	5	2	5	8	1	78	58	1	20	3	1	5
10	2	Lucky Man'	8	7	10	1	20	4	1	64	2	5	35	1	78	58	1	20	3	1	5
10	3	Eruption'	2	7	10	9	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5
10	4	Iconoclast'	1	100	10	1	20	4	1	5	2	5	35	1	78	58	1	20	3	1	5
10	5	Stones of Years'	0	7	10	9	48	0	1	5	2	5	8	1	78	58	1	20	3	23	5
10	6	Mass'	-8	7	10	9	20	4	1	64	2	5	35	1	78	58	20	90	49	77	3

#----------------- generation 15																					
15	1	Tarkus'	22	7	10	1	20	4	1	5	2	5	8	1	78	58	1	20	3	1	5
15	2	Iconoclast'	6	75	10	9	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5
15	3	Lucky Man'	4	7	10	9	48	4	1	64	2	5	35	1	78	58	1	20	3	1	5
15	4	Stones of Years'	3	75	10	9	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5
15	5	Mass'	2	10	27	14	11	86	8	102	2	5	8	1	78	58	1	20	3	1	5
15	6	Eruption'	-1	5	33	1	20	4	1	5	2	5	8	1	78	58	1	20	3	1	5

#----------------- generation 20				7	10	1	20	4	1	5	2	5	8	1	8	10	10	20	3	1	5
20	1	Tarkus'	16	7	10	1	20	4	1	5	2	5	8	1	78	58	1	20	3	1	5
20	2	Lucky Man'	5	7	10	1	48	0	1	5	34	5	8	1	78	58	1	20	3	1	5
20	3	Stones of Years'	4	7	10	1	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5
20	4	Mass'	-1	10	27	14	11	86	8	102	2	5	8	1	78	58	1	20	3	1	5
20	5	Eruption'	-5	85	74	21	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5
20	6	Iconoclast'	-7	7	27	14	11	86	68	102	18	5	8	69	34	47	46	66	15	45	5

#----------------- generation 25				7	10	1	20	4	1	5	2	5	8	1	8	10	10	20	3	1	5
25	1	Iconoclast'	8	7	10	1	48	36	1	5	2	47	32	53	78	58	1	20	3	1	5
25	2	Mass'	6	7	10	1	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5
25	3	Lucky Man'	1	7	10	1	48	36	1	5	2	5	8	1	78	58	1	87	3	1	5
25	4	Tarkus'	-1	7	10	1	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5
25	5	Stones of Years'	-2	72	92	8	51	43	48	84	2	47	32	53	78	58	1	20	3	1	5
25	6	Eruption'	-2	7	10	1	48	0	1	5	2	5	8	1	78	58	1	20	3	1	5

NB: first number in the list is the score, the other are the parameters 

Observing the evolution of the parameters, I've seen that there are two direction of growing:

- from top to bottom: good parameters will be distributed along all the population
- from bottom to top: random values that seems good raise from weaker engine to stronger one

It seems that it works like a real world of players: the strongest imposes their ideas (fromt op to bottom) until someone from the bottom can shows that they are wrong (from bottom to top).

[stegemma]

The first attempt to apply genetically computed parameters to the real software gives me some interesting result. In a little tournament, the genetic parameters gives equivalent score than non-genetical (so they are not only random or garbage). This parameters has grown from the standard ones with only 15 generations... then Windows overnight starts some "important update" and restart by its own

Now I'm try a bigger number of generations. The test is done with this options:

- 8 players (each one is a set of parameters)
- round robin, 2 games (one with white and one with black)
- 1 second per move
- stop with draw on half-move 100

In this second test, I start with the best parameters found in the previous one, so it is as a continuation of the previous one for more generations.

Next I want to try starting from random positions, to have a bigger variability.

The test tournament is available on the chess page of my site www.linformatica.com

I would like to have some other weak engine on the ELO range of Satana... but all seems or too strong or too bugged

[Fabio Gobbato]

You can use Pedone with the strength level set to 1 it should play to the same level as satana.

[stegemma]

Thanks, I will add Pedone to the next verifying session.

In the running tuning session, at generation 7 something happens: the best set of parameters has been casually modified by the algorithm, so that the first engine of the population now have a score near to those of the second one. The parameters look to be mixed with some minor engine set. In summary: the best set is "dead" and a son of it and some other engine has taken its place. In fact, the algorithm seems to have abandoned a local maximum and it is exploring another space of the possible solutions.

That looks great to me but I'm curious to see where (and if) it would converge to a better solution or not.

Any generation takes more than one hour... so the progress are very slow...

[matthewlai]

Thanks, I will add Pedone to the next verifying session.

In the running tuning session, at generation 7 something happens: the best set of parameters has been casually modified by the algorithm, so that the first engine of the population now have a score near to those of the second one. The parameters look to be mixed with some minor engine set. In summary: the best set is "dead" and a son of it and some other engine has taken its place. In fact, the algorithm seems to have abandoned a local maximum and it is exploring another space of the possible solutions.

That looks great to me but I'm curious to see where (and if) it would converge to a better solution or not.

Any generation takes more than one hour... so the progress are very slow...

The usual solution to that is elitism. Basically always move the best (or best-n) individuals to the next generation without modification.

[stegemma]

Thanks, I will add Pedone to the next verifying session.

In the running tuning session, at generation 7 something happens: the best set of parameters has been casually modified by the algorithm, so that the first engine of the population now have a score near to those of the second one. The parameters look to be mixed with some minor engine set. In summary: the best set is "dead" and a son of it and some other engine has taken its place. In fact, the algorithm seems to have abandoned a local maximum and it is exploring another space of the possible solutions.

That looks great to me but I'm curious to see where (and if) it would converge to a better solution or not.

Any generation takes more than one hour... so the progress are very slow...

The usual solution to that is elitism. Basically always move the best (or best-n) individuals to the next generation without modification.

Yes, I know (someone remember me this in another thread) but I store any generation, so that I could do a tournament with the best partial set of any time, if needed. I've found that this algorithm is enough "robust"; for the top-bottom/bottom-top raising of parameter values, the best set can propagate its best values before it would be "killed". The other sets will keep those best value even when the best one is gone. This happen even in nature, when a father/mother die, its sons keep its DNA.

In the overnight test (still running) another best set has rise after 15 generations, that seems to be more strong than the others. In effect, the others keeps most of the original "DNA" of the dead one:

Code: Select all

#----------------- generation 15				14	7	10	1	22	82	19	17	53	5	89	54	86	12	59	14	14	1
15	1	Lucky Man'	20	14	7	10	41	55	21	54	104	88	55	103	81	2	79	17	71	10	47
15	2	Manticore'	6	14	7	10	1	28	82	19	17	53	5	89	54	86	12	59	14	14	1
15	3	Mass'	1	14	7	10	1	78	82	19	17	53	5	89	54	86	12	59	14	14	1
15	4	Iconoclast'	-2	14	7	10	1	78	82	19	17	53	5	89	54	86	85	59	14	14	1
15	5	Eruption'	-3	14	7	10	1	78	82	19	17	53	5	89	54	86	12	59	14	14	1
15	6	Tarkus'	-6	1	7	10	1	28	82	19	17	53	5	89	2	86	12	59	14	14	1
15	7	Battlefield'	-7	1	7	10	1	28	82	19	17	53	5	89	54	86	12	59	14	14	1
15	8	Stones of Years'	-9	79	90	88	103	78	82	19	104	88	55	103	81	2	79	17	71	10	47

The previous best DNA was those on the line "generation 15" and the new is those near to "Lucky man". As you can see, this new best set has a score of 20 against a score of 6 of "Manticore" and other sets (that keeps original values) have a negative score: this means that the death of the previous best one lead the algorithm to explore a better region, without losing all the previous set.

[Ferdy]

- genetically cross N/4 players with another random player, but the last one

Could you describe in a layman's terms how this is done with the engine?

[stegemma]

- genetically cross N/4 players with another random player, but the last one

Could you describe in a layman's terms how this is done with the engine?

I have a group of players, each one is an engine with its parameters. The parameters all together describe a single individual in the population (in effect, a single array, in C++). The genetic algorithm works on those sets of parameters. We can think at this sets as they were the DNA of the players, so a single array of parameters is a single DNA of a single player.

I start learning defining:

- the number of iterations
- the number of players (the population)
- the time per move
- the max number of moves, to stop endless games

At any iteration, I play a round-robin match (all against all), in the population; 8 players (engines), for sample, plays each one 7 game with white and 7 game with black. I collect the score of any player and I sort players at the end of the tournament (the best scores first) and now I apply the genetic algorithm:

1) I randomly choose player A out the whole population (but the last)
2) I randomly choose player B (idem)
3) I merge the parameters from player B into player A (this changes player A, not player B)
4) I repeat step 1 for N/4 times (2 times, if population is of 8 players)
5) I set the last player (the worst) with random values then I merge that player with the first and the second one (the best ones)

Of course, because the last player will be changed at any time, in step 1 I avoid choosing that player for random merging.

That's all folks

[jdart]

8 players (engines), for sample, plays each one 7 game with white and 7 game with black.

The results of a game match of this number of games do not give you a reliable indicator of how good a change is. The standard deviation of the result is very large.

--Jon