Computer generated Opening set

Code, algorithms, languages, construction...
lucasart
Posts: 201
Joined: Mon Dec 17, 2012 1:09 pm
Contact:

Re: Computer generated Opening set

Post by lucasart » Sun Dec 29, 2013 3:13 am

Yes, I could have filtered at 4 plies before filtering the 5 ply set. But ultimately I will have to filter the 5 ply anyway, so I prefer not to reduce the diversity too early. I've generated the 5-ply set now, and I will not go further. I have more than enough positions. It's interesting to note that the branching factor keeps going down: more and more transpositions and more and more moves become bad (initially all moves are ok, but after a few moves you can't just play random anymore):

Code: Select all

$ wc -l ./book*.epd
      1 ./book0.epd
     20 ./book1.epd
    230 ./book2.epd
   2041 ./book3.epd
  17926 ./book4.epd
 141186 ./book5.epd
Now I'm running a Critter filtering of book5.epd (ab)using cutechess-cli. Basically I play each opening (Critter vs Critter) and adjudicate as draw if the first 4 plies (2 moves) of the game all have a score within +/-50cp, and resign at the 5-th ply if a 5-ply is reached (meaning the draw adjudication did not kick in at ply 4). That way I don't need to make long analyses, because I play 4 plies (relatively fast) and make sure no accident happens along that 4 ply mini game.

The filtering rate is about 10.5%, meaning 10.5% of positions are excluded by thie Critter filter. It does not mean they are all bad, far from that, but this filter is more conservative by construction (score needs to be within +/-50cp for 4 plies consecutively). I'll put the filtered 5-ply opening set when it's finished (a few more hours).
"Talk is cheap. Show me the code." -- Linus Torvalds.

User923005
Posts: 616
Joined: Thu May 19, 2011 1:35 am

Re: Computer generated Opening set

Post by User923005 » Sun Dec 29, 2013 7:59 am

This experiment is extremely interesting to me for several reasons.
One of which is the following question:
"Have humans discovered all of the good, solid chess openings?"
In other words, will this initially weakly directed search through an ocean of unplayed positions create new openings that are just as playable as those that are popular?

In your reduced set, I have 16813 positions with games = 0 and 1113 with games > 0.
Now, it is not nearly as lopsided as it sounds, since I do not record counts for games with 4 or less games played.

However, it does show that most possible positions are very rarely played. And with 17926 positions, the median (sorted by score) centipawn evaluation is from row 8963, which has a centipawn evaluation of 18, which sounds immensely playable.

So, are we missing out on most of the fun? Will we need to invent a million new opening names after research like this?

Certainly, there are many more questions a lot more interesting than these.

lucasart
Posts: 201
Joined: Mon Dec 17, 2012 1:09 pm
Contact:

Re: Computer generated Opening set

Post by lucasart » Sun Dec 29, 2013 8:44 am

Yes, it's a fascinating project. What I like the most is to be able to play completely original openings, and bring engines into completely unknown territory. Force them to develop their own strategy from the word "go", rather then force them to play boring drawish lines that humans have memorized for centuries and have arrogantly decided are "best".

In the starting position, there are 20 legal moves. I am intimately convinced (although I cannot prove it) that any of these legal moves is correct, in the sense that it preserves the draw with perfect play.

After each of these moves, black has 20 moves, so we have perft(2)=400. I will not go as far as saying that any answer from black to any first white move is ok, but more than half are playable. In my sample (second run with stricter filtering) I had 230 leaves for the 2-ply book, and with the looser filter 330. I don't know the real number is, but there is also a strong biais in engine eval of opening positions too (engines designed by humans favor orthodox developpement). Let's make a wild guess: 300.

Really the ultimate question is: what is the perfect chess tree? From the starting position (which is a draw with perfect play, let's accept that postulate), play only the moves that preserve the draw, and so on. I'm sure this tree is very dense close to the root. The closer to the root the higher the branching factor.

Anyway, that's another discussion, which could go on eternally. And perhaps will be solved one day, but not in the foreseeable future.
"Talk is cheap. Show me the code." -- Linus Torvalds.

lucasart
Posts: 201
Joined: Mon Dec 17, 2012 1:09 pm
Contact:

Re: Computer generated Opening set

Post by lucasart » Sun Dec 29, 2013 8:52 am

OK, I've finished the Critter verification. I decided to take a random sample of 64k positions out of the 141k positions of book5.epd, and only analyze those.

The resulting opening set has 57910 unique positions. I will post it in the Engine/Book forum, so more people can find it. Perhaps we will see tournaments being played from that opening set, which will deliver plenty of diversity and fun games. That's my hope anyway.
"Talk is cheap. Show me the code." -- Linus Torvalds.

Post Reply