Genetical learning (again)

[Karlo Bala]

I've started another session of genetical learning in Satana, now that it uses transposition tables too:

Code: Select all

#----------------- generation 28
28	1	'Lucky Man'	5485	11	41	1	95	4	1	5	2	32	8	1	8	10	78	35	22	12	31	10	
28	2	'Battlefield'	3640	11	41	1	95	4	1	5	2	32	8	1	8	10	78	35	22	12	90	10	
28	3	'Tarkus'	2745	11	41	1	20	4	1	92	66	79	61	5	26	22	14	35	22	12	31	10	
28	4	'Eruption'	2618	11	41	1	95	4	1	5	2	32	8	1	8	10	78	35	22	12	90	10	
28	5	'Stones of Years'	210	73	55	1	95	4	1	5	2	32	8	1	8	10	78	35	22	12	90	10	
28	6	'Mass'	-836	52	24	10	43	12	44	61	86	79	61	5	26	22	14	35	22	12	31	77	
28	7	'Manticore'	-1802	73	41	1	95	4	1	61	7	32	8	1	8	10	78	35	22	12	31	10	
28	8	'Iconoclast'	-6613	11	41	1	29	67	23	70	82	57	86	68	25	6	20	93	91	40	31	10	

[...]

#----------------- generation 30
30	1	'Battlefield'	7341	11	41	1	95	4	1	5	2	32	8	1	8	10	78	35	22	12	90	10	
30	2	'Iconoclast'	1906	11	41	1	95	6	64	5	2	32	8	1	8	10	89	35	22	12	90	10	
30	3	'Lucky Man'	1875	52	24	10	43	12	44	61	86	79	8	1	8	10	78	35	22	12	31	10	
30	4	'Tarkus'	984	11	41	1	95	4	1	5	2	32	8	1	8	10	89	35	22	12	90	10	
30	5	'Manticore'	847	73	41	1	95	4	1	61	7	32	8	1	8	10	78	35	22	12	31	10	
30	6	'Stones of Years'	337	73	55	1	95	4	1	5	2	32	8	1	8	10	78	35	22	12	90	10	
30	7	'Mass'	-765	52	24	10	43	12	44	61	86	79	61	5	26	22	14	35	22	12	31	77	
30	8	'Eruption'	-3045	11	41	1	95	4	1	5	2	32	8	1	8	10	78	35	22	12	90	10

The new value since now seems coherent with my observation od the playing style of Satana:

- increase in development value from 10 to 41; Satana develops pieces better than my previous engines but still it is not enough

- increase in castling value from 20 to 95; this seems to me to be too high but maybe is because of the method used in this session (if you don't start from initial position maybe castling has already become urgent)

- increase in passed pawns value from 5 to 32; in fact, Satana lose a lot of game between LarsenVB because of passed pawns (LVB is not in the training set)

- rooks on open column from 10 to 78; this is a little surprise

- pyramid 3 to 22; this is how pieces are near to enemy king and maybe it means that Satana must be more aggressive

- potential castling from 5 to 31; this is coherent with the increase of castling value

It is interesting that about half the parameters keeps their original values.

This learning session has been done this way:

- 8 versions of Satana (population): half with standard parameters and half with random ones
- 200 ms per move
- 100 half moves limit per game
- one game with white and one with black for any single match (A vs B + B vs A)
- any game starts from positions randomly selected from file "ficsgamesdb_2014_standard2000_nomovetimes_1286521"
- Pentium Intel i7 4790K (only one core used)
- 32 Mb hash

28 generations are not enough to have some definitive result but the learning session is till in progress.

IMO, your pool is just too small.

[BeyondCritics]

You could search for "tutorial" or "overview":
https://scholar.google.de/scholar?hl=en ... n+tutorial

This method seems attractive to practitioners, due to its simplicity.
Alas, a noise free fitness function is assumed. You had to first overcome this difficulty and would then be on your own i think.

[stegemma]

The results are interesting but I need more work, to automize testing. The genetical tuning has been done only with the same satana engine, with different parameters and this lead to a population that grows to a closed sub-set of "players", that is not optimal against external opponents. It is as a closed chess club where all players always play against the club members for years and years... and suddenly they go to an external tourney! That's no good.

In Satana I already have a "tourney mode", that I can use to challenge external engines, instead or in addition to self-playing mode. In this scenario, I could explore other algorithm too (particle swarm, simulated annealing, neural networks...) but first of all I have to complete the "tourney mode" then the algorithm used could be interchangeable and maybe I could use more of them and let algorithm to compete.

Of course Satana is not the best target for this, because it is a limited engine, but that's what I have now.

[stegemma]

[...]
I doubt that PSO for chess can work efficiently. There are some problems with PSO for chess.

In early generations, all parameters are more or less random, and engines are very weak. It is possible that one is better then others simply because all other engines are too weak.

For example, Engine1 make 80% of wins, and all others much less. Now, parameters of Engine 1 become global optimum toward which particles move. In later generations, all engines are making progress, and none of engines can make 80% of wins. Problem is that until to end particle move toward weak global optimum. One must make some correction of global optimum that is to old, but it is not simple to find right formula.

There are some other problems also. Basically, there is no absolute measure of engine strength, just relative to others. For PSO there must be some absolute measure that is always the same for same parameters.

These problems occurs with almost any algorithm. I've read the paper:

Code: Select all

Particle Swarm Optimization: A Tutorial
James Blondin September 4, 2009

and it is very simple to understand, even with low mathematical knowledge.

The idea is interesting, maybe applied with some changes. In effect it is not so far from GA: in both algorithms you have a population of solutions and you change them generation by generation. In GA you mix/swap the genes and add some randomness; in PSO you "move" the particles toward local/global optimum, with some random deviation on the path and coefficient for inertia.

Despite from the algorithm itself, the idea of particle running/moving/floating in the solution space is somehow fascinating... you can imagine solutions swimming in an aquarium like a red fish does

[tpetzke]

I also had my doubts about PSO. I use a different kind of GA but I experienced problems when I used ELITISM. It moves the GA to much toward a possible weak optimum.

The most success I had with algorithms that don't overvalue the results of a few matches, like thinking the winner is really cool and we must move toward him the next n generations.

[Karlo Bala]

[...]
I doubt that PSO for chess can work efficiently. There are some problems with PSO for chess.

In early generations, all parameters are more or less random, and engines are very weak. It is possible that one is better then others simply because all other engines are too weak.

For example, Engine1 make 80% of wins, and all others much less. Now, parameters of Engine 1 become global optimum toward which particles move. In later generations, all engines are making progress, and none of engines can make 80% of wins. Problem is that until to end particle move toward weak global optimum. One must make some correction of global optimum that is to old, but it is not simple to find right formula.

There are some other problems also. Basically, there is no absolute measure of engine strength, just relative to others. For PSO there must be some absolute measure that is always the same for same parameters.

These problems occurs with almost any algorithm. I've read the paper:

Code: Select all

Particle Swarm Optimization: A Tutorial
James Blondin September 4, 2009

and it is very simple to understand, even with low mathematical knowledge.

The idea is interesting, maybe applied with some changes. In effect it is not so far from GA: in both algorithms you have a population of solutions and you change them generation by generation. In GA you mix/swap the genes and add some randomness; in PSO you "move" the particles toward local/global optimum, with some random deviation on the path and coefficient for inertia.

Despite from the algorithm itself, the idea of particle running/moving/floating in the solution space is somehow fascinating... you can imagine solutions swimming in an aquarium like a red fish does

I've tried many algorithms, GA, PBIL, PSO, and several others. All of them with binary and floating representations. Best results I got with GA with the binary representation, but for 12 parameters I have used between 50 and 100 individuals. I used PSO to optimize various multidimensional functions and PSO was better than the other two, but for chess was worse. In addition, I used the aging of the global optimum. Without aging PSO for chess was almost unusable.

[stegemma]

[...]

I've tried many algorithms, GA, PBIL, PSO, and several others. All of them with binary and floating representations. Best results I got with GA with the binary representation, but for 12 parameters I have used between 50 and 100 individuals. I used PSO to optimize various multidimensional functions and PSO was better than the other two, but for chess was worse. In addition, I used the aging of the global optimum. Without aging PSO for chess was almost unusable.

It has been said by some people that my GA population is too little and that PSO isn't very good for chess. This would avoid me loosing time in the possibly wrong direction.

Thanks for the hint, I'll retry with a bigger population and let you know, time by time while running.

[jdart]

I am really finding it hard to believe this method can work, since if you are running limited numbers of matches to gauge difference between versions the noise (error bars) from that is very large.

CLOP often requires tens of thousands of games for convergence. Not because it is a worse method but because you need that many to get parameter values that are reliable given the measurement error from games.

There are derivative free methods that converge faster but IMO you still need at least few thousand games to measure whether version A is better than version B.

--Jon

[mike_bike_kite]

I use genetic tuning in my own little chess program. Pretty much every part of the program can be either tuned or turned on/off via these parameters. I tend to let it play itself for say 100 games and altering one param at a time. I appreciate that this isn't optimal but it's enough to highlight issues in my settings. As well as suggesting better values for parameters it also tells me if a certain part of the code is completely useless (that happens a lot) or if there's a bias for black or white which tends to indicate a bug. I used it so much that I ended up writing a little language to control what the genetic tuning actually does.

[tpetzke]

There are derivative free methods that converge faster but IMO you still need at least few thousand games to measure whether version A is better than version B.

It is not so bad actually. If you have a population size of 256 and play a knockout tournament you will end up with a probably good sample as winner (very likely not the best but a good one). This doesn't take thousands but a few hundred games. Using this winning sample to guide the GA a little step into that direction actually works.

If by bad luck you end up with bad sample that managed to win through noise - it is overall not so bad. More likely good ones win.

Overall you still play a huge number of games, several 100.000 usually if you go for 1000 generations like I usually do.