Database storage methods

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
Rebel
Posts: 6991
Joined: Thu Aug 18, 2011 12:04 pm

Re: Database storage methods

Post by Rebel »

mar wrote:Good idea Julien except that I think this can't handle transpositions :wink:
Depends what you are planing to do with the data. For instance my opening book is 2-bytes move based:

byte-1, 6 bits square from, 2 bits guiding the tree.
byte-2, 6 bits square to, 2 bits for priority (play often, play frequently, play seldom, don't play).

The book is read into memory at program start and when searching the book a hashkey is maintained and compared to the hashkey of the board position. It's still fast enough. Of course with a real big tree you will have to go the hash way.
Top
User avatar
Rebel
Posts: 6991
Joined: Thu Aug 18, 2011 12:04 pm

Re: Database storage methods

Post by Rebel »

JuLieN wrote:

Code: Select all

(e4(e5(Nf3(Nc6(Bb5 a6)Bc4)Nf6)f4)(c5 Nf3)(d6 d4)Nc6)e6)(d4(Nf6 c4(g6 Nc3)e6(Nc3 Bb4)Nf3)(d5(c4(c6 Nf3)(e6 Nc3)dxc4)Nf3)f5) etc.
Funny, mine is the same, still is, but added transpositions to it later :wink:
Top
User avatar
hgm
Posts: 27790
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Database storage methods

Post by hgm »

I am not sure what problem you try to solve here. In a collection of games almost all positions will occur in only a single game. So there is not a huge gain in terms of number of positions when you cllapse multiply occurring (opening) positions to one. If combining involves some overhead, like extra pointers, you quickly lose more than you gain.

If you want to store PGN that includes comments or recursive variations, you have the additional problem that games with the same initial moves might have different comments, or ar annotated with different variations. So it is crucial to know how you want to handle comments and variations. Is this for an application where you can simply strip them? Are they stored separately from the moves?
Top
Dave_N
Posts: 153
Joined: Fri Sep 30, 2011 7:48 am

Re: Database storage methods

Post by Dave_N »

hgm wrote:I am not sure what problem you try to solve here. In a collection of games almost all positions will occur in only a single game. So there is not a huge gain in terms of number of positions when you cllapse multiply occurring (opening) positions to one. If combining involves some overhead, like extra pointers, you quickly lose more than you gain.

If you want to store PGN that includes comments or recursive variations, you have the additional problem that games with the same initial moves might have different comments, or ar annotated with different variations. So it is crucial to know how you want to handle comments and variations. Is this for an application where you can simply strip them? Are they stored separately from the moves?
Yeah the annotations would be stripped from the game data that is stored in the tree, I guess this is the problem with the entire sparse storage idea too, and if I wanted a large tree / trie / graph for position searching I would need to write all the moves into the hash.

I think a graph structure in a hash table that handles retrieval of game indexes en-masse (the games themselves can be kept in pure form with comments) is what I am trying to achieve here - to solve problems of position searching and statistics.

I really don't know how much the merged positions would compress, the number seems to be something like num_games * 75, however that might be without merging.

The other way might be a hash entry for each position collision, with a list of pointers back to the trie nodes that transposed to the position ... this would also index a game list.
Top
User avatar
hgm
Posts: 27790
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Database storage methods

Post by hgm »

In WinBoard's position search I currently do the same thing (keeping the original PGN, as well as making a compact, search-friendly version of the moves). The compact representation is just a sequence of (from, to) 8-bit square-number pairs, where an off-board from-square is used as escape for special moves that need extra information (like promotion piece, which is then given in the second byte). There is an index that tells where each game starts in the compact representation, so that you only have to search through them to a point where you can no longer find the position you are looking for (e.g. because the number of pieces has dropped to below what you were looking for), and then skip to the next game.
Top
Harald
Posts: 317
Joined: Thu Mar 09, 2006 1:07 am

Re: Database storage methods

Post by Harald »

The discussion would not be complete without this link:
http://www.gotw.ca/gotw/072.htm
"Data Formats and Efficiency. How good are you at choosing highly
compact and memory-efficient data formats? How good are you at writing
bit-twiddling code? This GotW gives you ample opportunity to exercise
both skills, as we consider efficient representations of chess games and a
BitBuffer to hold them."

And just for fun I add this:

This is a 'game' that is merged from all 27202 games in the database gm2600.pgn.
The +win=draw-loss numbers are written in comments.
I reduced this opening database 'game' to variants
with a maximum depth of 6 half moves and at least 20
played games with the help of some filter functions.

Code: Select all

1. e4 {+2725=4855-1579} (1. d4 {+3228=6480-2014} Nf6 {+2223=4463-1406} (1... d6 
{+108=156-51} 2. c4 {+20=29-9} (2. Nf3 {+39=64-18} Bg4 {+16=33-7} (2... g6 
{+15=24-10} 3. c4 {+8=11-6} Bg7 {+7=10-6}) 3. c4 {+13=21-3} Nd7 {+9=15-3}) (2. 
e4 {+42=60-23} Nf6 {+27=43-19} (2... g6 {+14=17-4} 3. Nc3 {+7=12-2}) 3. f3 
{+5=10-5} (3. Nc3 {+20=30-13} g6 {+17=25-12})) 2... e5 {+16=24-5} 3. Nf3 
{+14=19-5} e4 {+8=16-3}) (1... d5 {+658=1464-402} 2. c4 {+578=1247-351} (2. Nf3 
{+66=194-41} Nf6 {+42=121-22} (2... c6 {+8=23-8} 3. c4 {+7=18-3}) (2... e6 
{+7=27-5} 3. c4 {+6=21-4} dxc4 {+5=14-2}) (2... c5 {+4=14-4}) 3. c4 
{+39=114-22} c6 {+21=43-14} (3... dxc4 {+13=48-3}) (3... e6 {+4=23-5})) (2. Bg5 
{+11=17-7}) 2... e6 {+171=370-76} (2... dxc4 {+130=257-78} 3. e3 {+27=44-12} 
(3. Nf3 {+51=122-34} a6 {+16=35-8} (3... Nf6 {+25=79-23})) (3. e4 {+51=84-30} 
Nf6 {+18=36-15} (3... c5 {+8=5-8}) (3... Nc6 {+9=11-4}) (3... e5 {+16=32-3})) 
3... Nf6 {+15=28-11}) (2... c6 {+264=607-187} 3. e3 {+13=42-8} (3. Nc3 
{+120=248-83} Nf6 {+100=228-73} (3... e5 {+8=8-6})) (3. Nf3 {+121=285-89} Nf6 
{+118=281-85}) (3. cxd5 {+8=30-6} cxd5 {+8=30-6}) 3... Nf6 {+11=35-7}) 3. Nc3 
{+120=263-53} (3. Nf3 {+49=105-23} c6 {+5=16-2} (3... Nf6 {+29=73-18}) (3... c5 
{+14=13-2})) 3... Be7 {+52=113-14} (3... c5 {+10=28-8}) (3... c6 {+14=30-9}) 
(3... Nf6 {+37=78-18}) (3... Bb4 {+6=11-4})) (1... e6 {+137=225-81} 2. c4 
{+101=131-55} (2. Nf3 {+20=46-12} Nf6 {+7=13-4} (2... f5 {+7=11-3})) (2. e4 
{+14=44-12} d5 {+14=38-10} 3. Nd2 {+5=15-0} (3. Nc3 {+2=16-6})) 2... b6 
{+10=16-9} (2... Bb4+ {+14=28-7} 3. Bd2 {+10=20-2}) (2... Nf6 {+30=54-21} 3. 
Nf3 {+18=34-12} (3. Nc3 {+10=20-8} Bb4 {+8=19-7}) 3... b6 {+10=18-4}) (2... d5 
{+16=11-7} 3. Nc3 {+9=8-4}) (2... f5 {+28=22-11} 3. g3 {+22=13-7} Nf6 
{+22=13-7})) (1... f5 {+57=107-50} 2. Nc3 {+8=11-5} (2. g3 {+31=51-28} Nf6 
{+27=48-26} 3. Bg2 {+27=47-26} g6 {+19=30-14}) (2. c4 {+13=14-6} Nf6 
{+13=12-6}) (2. Nf3 {+5=24-8} Nf6 {+3=20-8})) (1... g6 {+30=41-17} 2. e4 
{+15=23-7} (2. c4 {+9=13-7} Bg7 {+9=12-6}) 2... Bg7 {+9=17-6}) (1... c5 
{+7=14-4} 2. d5 {+6=10-4}) 2. c4 {+1832=3482-1113} (2. Nf3 {+360=911-253} g6 
{+121=309-108} (2... e6 {+151=414-111} 3. c4 {+94=255-69} (3. e3 {+7=31-8} c5 
{+3=16-3} (3... b6 {+4=14-5})) (3. Bg5 {+20=61-16} h6 {+5=17-6} (3... c5 
{+11=37-9})) (3. g3 {+28=64-18} b6 {+9=17-8} (3... b5 {+10=29-6})) 3... b6 
{+50=156-39} (3... Bb4+ {+13=39-11}) (3... c5 {+17=22-13}) (3... d5 
{+11=36-6})) (2... d5 {+42=114-21} 3. c4 {+41=109-19} e6 {+24=81-14} (3... c6 
{+12=19-5})) (2... c5 {+31=35-8} 3. d5 {+28=28-8} b5 {+10=9-4} (3... g6 
{+10=12-3})) (2... b6 {+4=23-1}) (2... d6 {+11=12-3}) 3. Bf4 {+4=16-12} (3. c4 
{+72=142-53} Bg7 {+69=136-53}) (3. g3 {+31=77-12} Bg7 {+24=58-11} (3... d5 
{+4=16-0})) (3. Bg5 {+10=55-23} Bg7 {+10=53-23}) (3. c3 {+4=14-3} Bg7 
{+4=14-3}) 3... Bg7 {+4=16-12}) (2. Bg5 {+26=54-35} Ne4 {+12=24-14} (2... e6 
{+11=11-9}) 3. Bf4 {+9=18-7}) 2... e6 {+1101=2352-669} (2... g6 {+543=881-334} 
3. Nc3 {+446=678-284} (3. g3 {+38=89-18} c6 {+5=25-3} (3... Bg7 {+31=53-14})) 
(3. Nf3 {+55=111-27} Bg7 {+55=111-27}) 3... d5 {+171=292-110} (3... Bg7 
{+274=384-173})) (2... c5 {+128=157-86} 3. d5 {+110=143-75} (3. Nf3 {+14=13-10} 
cxd4 {+13=10-10}) 3... b5 {+47=70-37} (3... g6 {+17=26-13}) (3... e6 
{+21=24-12}) (3... e5 {+14=7-5}) (3... d6 {+9=15-8})) (2... c6 {+24=29-7} 3. 
Nc3 {+16=22-5} d5 {+15=21-5}) (2... d6 {+28=46-14} 3. Nc3 {+25=36-10} Nd7 
{+12=21-4}) (2... e5 {+5=15-2} 3. dxe5 {+5=14-2} Ng4 {+5=14-2}) 3. Nf3 
{+601=1350-338} (3. Nc3 {+440=831-285} Bb4 {+375=721-258} (3... d5 {+51=99-22}) 
(3... c5 {+14=10-5})) (3. g3 {+59=168-46} c5 {+8=22-10} (3... d5 {+28=108-22}) 
(3... Bb4+ {+23=36-14})) 3... d5 {+142=357-91} (3... b6 {+333=743-177}) (3... 
Bb4+ {+84=198-44}) (3... c5 {+42=52-25})) (1. c4 {+789=1644-463} Nf6 
{+252=492-132} (1... c6 {+35=90-28} 2. e4 {+10=28-13} (2. Nf3 {+8=17-2} d5 
{+6=17-2}) (2. d4 {+17=33-8} d5 {+16=33-8} 3. Nf3 {+7=14-2} (3. Nc3 {+7=12-4}) 
3... Nf6 {+7=13-2}) 2... d5 {+8=25-12} 3. exd5 {+6=23-9} cxd5 {+5=19-6}) (1... 
e5 {+183=367-123} 2. g3 {+30=68-26} (2. Nc3 {+149=295-97} Nc6 {+35=94-29} (2... 
Bb4 {+19=20-9} 3. Ncd5 {+16=16-6} Be7 {+10=6-5}) (2... d6 {+29=27-10} 3. Nf3 
{+9=11-4} (3. g3 {+12=13-2})) (2... Nf6 {+65=153-48} 3. Nf3 {+47=121-38} (3. g3 
{+18=30-10} Bb4 {+4=16-4} (3... d5 {+10=5-5})) 3... Nc6 {+46=119-37}) 3. g3 
{+20=58-13} (3. Nf3 {+14=31-12} Nf6 {+5=20-9}) 3... g6 {+15=55-12}) 2... Nf6 
{+12=32-12} (2... Nc6 {+8=26-10} 3. Bg2 {+7=25-10} g6 {+7=18-8}) 3. Bg2 
{+12=32-12} d5 {+7=12-7}) (1... c5 {+117=277-63} 2. Nf3 {+86=188-36} (2. g3 
{+19=49-10} g6 {+12=33-6} 3. Bg2 {+11=31-6} Bg7 {+11=31-6}) (2. Nc3 {+11=38-15} 
g6 {+2=16-5} (2... Nc6 {+4=14-3})) 2... Nf6 {+52=133-24} (2... Nc6 {+19=38-7} 
3. d4 {+7=16-4} (3. Nc3 {+10=21-3} Nf6 {+6=13-2}) 3... cxd4 {+7=16-4}) (2... g6 
{+13=13-3}) 3. g3 {+3=17-5} (3. Nc3 {+48=108-18} Nc6 {+19=41-5} (3... e6 
{+19=41-9}) (3... d5 {+9=19-4}))) (1... e6 {+120=270-70} 2. Nf3 {+21=63-18} (2. 
g3 {+12=47-16} d5 {+11=39-14} 3. Bg2 {+11=32-13} Nf6 {+10=22-6}) (2. Nc3 
{+76=128-33} d5 {+55=98-25} 3. d4 {+55=97-24} Be7 {+20=38-11} (3... Nf6 
{+24=45-11})) (2. d4 {+10=32-3} d5 {+8=22-3} 3. Nc3 {+7=13-3}) 2... d5 
{+13=30-10} (2... Nf6 {+7=33-8} 3. Nc3 {+4=12-4} (3. g3 {+3=17-3})) 3. d4 
{+7=17-6} Nf6 {+7=15-3}) (1... g6 {+56=117-40} 2. d4 {+24=30-6} (2. Nc3 
{+14=43-18} Bg7 {+12=32-14} 3. g3 {+3=23-11}) (2. e4 {+13=21-11} Bg7 {+7=16-7} 
3. d4 {+7=16-7} d6 {+7=16-7}) 2... Bg7 {+11=18-4} (2... Nf6 {+13=11-2}) 3. Nc3 
{+5=11-4}) (1... f5 {+12=16-2}) (1... b6 {+12=13-4}) 2. Nc3 {+195=323-101} (2. 
Nf3 {+31=122-15} g6 {+7=17-4} (2... c6 {+3=16-1}) (2... c5 {+7=20-4} 3. Nc3 
{+6=11-4}) (2... e6 {+11=46-3} 3. g3 {+5=20-2}) (2... b6 {+3=23-3} 3. g3 
{+3=16-2} Bb7 {+2=16-2})) (2. g3 {+16=25-7}) (2. d4 {+9=22-9} e6 {+4=15-8}) 
2... g6 {+31=40-21} (2... e5 {+26=61-28} 3. Nf3 {+25=51-25} Nc6 {+25=51-25}) 
(2... c5 {+48=73-22} 3. Nf3 {+34=44-13} (3. g3 {+14=29-9} e6 {+10=15-3}) 3... 
d5 {+11=7-4} (3... e6 {+11=25-6}) (3... Nc6 {+7=10-3})) (2... d5 {+16=21-4} 3. 
cxd5 {+14=20-4} Nxd5 {+14=20-4}) (2... e6 {+66=118-26} 3. Nf3 {+49=81-19} (3. 
e4 {+9=21-3}) (3. d4 {+8=16-3} Bb4 {+8=12-2}) 3... b6 {+16=27-6} (3... d5 
{+18=32-6}) (3... c5 {+7=15-3})) 3. g3 {+9=17-6} (3. e4 {+16=14-12} d6 
{+16=14-12}) 3... Bg7 {+9=15-5}) (1. Nf3 {+800=1946-451} d5 {+179=465-93} (1... 
Nf6 {+440=1115-241} 2. c4 {+367=896-180} (2. d4 {+21=74-18} g6 {+8=31-4} (2... 
e6 {+9=20-8} 3. c4 {+7=13-5}) (2... d5 {+3=17-2})) (2. g3 {+51=136-39} b6 
{+2=17-6} (2... d5 {+20=50-15} 3. Bg2 {+19=49-15} c6 {+12=31-13}) (2... g6 
{+21=57-12} 3. Bg2 {+13=30-9} (3. b3 {+5=15-2} Bg7 {+5=14-2}) 3... Bg7 
{+13=28-9}) 3. Bg2 {+2=15-6} Bb7 {+2=15-6}) 2... g6 {+106=223-39} (2... e6 
{+126=321-63} 3. Nc3 {+77=170-22} (3. g3 {+34=108-26} d5 {+26=69-16} (3... b6 
{+5=29-4})) (3. d4 {+15=35-13} b6 {+12=18-6}) 3... Bb4 {+44=75-14} (3... d5 
{+22=71-8})) (2... c5 {+68=177-34} 3. Nc3 {+49=118-22} (3. g3 {+15=55-7} b6 
{+6=24-4} (3... d5 {+6=14-0})) 3... Nc6 {+28=43-7} (3... d5 {+4=30-5}) (3... e6 
{+11=38-8})) (2... b6 {+49=132-33} 3. g3 {+32=94-29} (3. d4 {+5=16-2} e6 
{+5=14-1}) (3. Nc3 {+12=18-1} Bb7 {+11=13-1}) 3... Bb7 {+19=63-11} (3... c5 
{+9=26-12})) (2... c6 {+12=34-7} 3. Nc3 {+8=16-4} d5 {+8=16-4}) 3. Nc3 
{+67=130-26} (3. g3 {+32=73-9} Bg7 {+31=69-9}) 3... Bg7 {+54=83-21} (3... d5 
{+13=46-5})) (1... c5 {+93=197-62} 2. c4 {+66=146-39} (2. g3 {+10=32-11} Nc6 
{+4=14-4}) (2. e4 {+12=11-3}) (2. b3 {+5=8-8}) 2... Nc6 {+22=41-20} (2... Nf6 
{+27=79-14} 3. Nc3 {+16=55-8} (3. g3 {+10=20-5} b6 {+6=12-3}) 3... e6 {+5=25-4} 
(3... Nc6 {+6=16-0})) (2... g6 {+13=23-4} 3. d4 {+8=11-4}) 3. Nc3 {+14=26-10} 
(3. d4 {+6=10-5} cxd4 {+6=10-5}) 3... Nf6 {+9=12-3}) (1... e6 {+6=23-7}) (1... 
d6 {+17=28-17} 2. d4 {+10=23-13} Bg4 {+7=16-8}) (1... g6 {+46=67-26} 2. d4 
{+20=28-10} (2. e4 {+17=19-10} Bg7 {+8=8-9} 3. d4 {+8=8-9} d6 {+8=7-9}) (2. c4 
{+8=15-6} Bg7 {+8=12-6}) 2... Bg7 {+14=15-7}) (1... f5 {+12=38-5} 2. g3 
{+11=24-2} Nf6 {+11=20-2} 3. Bg2 {+11=19-2}) 2. d4 {+107=262-39} (2. c4 
{+30=90-25} e6 {+9=27-6} (2... d4 {+8=16-9}) (2... c6 {+8=36-7} 3. d4 {+5=17-3} 
(3. e3 {+3=15-3}) 3... Nf6 {+5=17-3}) 3. g3 {+7=11-3}) (2. g3 {+37=102-23} Nf6 
{+8=32-7} (2... Bg4 {+3=14-7} 3. Bg2 {+3=13-7}) (2... c6 {+15=30-6} 3. Bg2 
{+14=30-6} Bg4 {+12=24-6}) 3. Bg2 {+8=32-7} c6 {+4=12-4}) 2... Nf6 {+66=206-26} 
(2... e6 {+12=19-1} 3. c4 {+11=16-1}) (2... c6 {+15=16-5} 3. c4 {+15=14-5} Nf6 
{+9=9-4}) (2... Bf5 {+7=14-3} 3. c4 {+6=13-3} e6 {+6=13-3}) 3. c4 {+65=203-26} 
e6 {+33=96-14} (3... dxc4 {+6=55-5}) (3... c6 {+26=52-7})) (1. b3 {+11=16-13} 
e5 {+7=7-6} 2. Bb2 {+7=7-6}) (1. g3 {+38=75-36} d5 {+12=39-13} (1... g6 
{+16=13-6} 2. Bg2 {+15=12-6} Bg7 {+15=11-6}) (1... e5 {+7=9-7}) 2. Bg2 
{+8=23-10} (2. Nf3 {+4=16-3})) 1... e6 {+376=704-213} (1... e5 {+653=1337-361} 
2. Bc4 {+16=30-9} (2. Nf3 {+609=1258-336} Nf6 {+88=229-29} (2... Nc6 
{+517=1021-306} 3. Bb5 {+396=801-243} (3. Bc4 {+65=103-28} Bc5 {+32=51-15} 
(3... Nf6 {+31=47-13})) (3. d4 {+32=62-18} exd4 {+32=62-18}) (3. Nc3 
{+22=49-14} Nf6 {+17=48-13}) 3... Nf6 {+47=66-27} (3... a6 {+314=664-194}) 
(3... Bc5 {+4=11-5}) (3... g6 {+12=31-13}) (3... Nd4 {+5=13-2})) 3. Nxe5 
{+40=151-20} (3. Nc3 {+10=21-4} Nc6 {+8=15-3}) (3. d4 {+37=57-5} Nxe4 
{+34=43-5}) 3... d6 {+40=151-20}) (2. f4 {+14=14-6} exf4 {+12=11-6}) (2. Nc3 
{+12=30-7} Nf6 {+8=24-4}) 2... Nf6 {+13=29-8} 3. d3 {+12=25-8} Nc6 {+3=13-5}) 
(1... c5 {+1178=2016-741} 2. Nf3 {+1044=1744-638} (2. Nc3 {+76=154-64} e6 
{+13=31-11} (2... d6 {+20=45-14} 3. g3 {+8=13-5} (3. f4 {+6=20-4}) 3... Nc6 
{+5=12-3}) (2... Nc6 {+43=75-36} 3. g3 {+18=36-16} (3. Nf3 {+6=16-10}) (3. Ne2 
{+12=13-2}) (3. f4 {+7=7-6}) 3... g6 {+18=35-15}) 3. Nf3 {+8=16-7}) (2. c3 
{+38=88-26} e6 {+7=14-4} (2... d5 {+15=29-8} 3. exd5 {+15=26-7} Qxd5 
{+15=26-7}) (2... Nf6 {+11=38-11} 3. e5 {+10=38-10} Nd5 {+10=38-10}) 3. d4 
{+5=14-4} d5 {+5=14-4}) 2... e6 {+264=441-130} (2... Nc6 {+229=384-124} 3. d4 
{+176=302-88} (3. Bb5 {+41=61-26} g6 {+18=32-9} (3... e6 {+15=15-10})) (3. Nc3 
{+8=20-8}) 3... cxd4 {+176=302-88}) (2... d6 {+546=904-379} 3. d4 
{+489=761-328} (3. c3 {+11=20-4} Nf6 {+11=20-4}) (3. Bb5+ {+30=103-32} Bd7 
{+19=83-14} (3... Nc6 {+6=9-11}) (3... Nd7 {+5=11-7})) (3. Nc3 {+7=14-10}) 3... 
cxd4 {+466=736-314} (3... Nf6 {+23=25-14})) 3. d4 {+213=337-108} (3. c3 
{+6=28-4} d5 {+2=27-4}) (3. Nc3 {+22=39-12} a6 {+8=13-6} (3... Nc6 {+6=19-5})) 
(3. d3 {+14=20-3} Nc6 {+12=16-2}) 3... cxd4 {+213=337-108}) (1... c6 
{+250=488-140} 2. d4 {+210=390-114} (2. c4 {+15=43-6} d5 {+11=33-5} 3. exd5 
{+6=23-3} cxd5 {+3=20-3}) (2. Nc3 {+10=28-8} d5 {+10=27-8} 3. Nf3 {+8=21-6} Bg4 
{+4=17-6}) (2. d3 {+11=23-11} d5 {+8=18-8} 3. Nd2 {+8=18-8}) 2... d5 
{+210=388-114} 3. Nd2 {+63=131-34} (3. Nc3 {+44=97-25} dxe4 {+43=95-25}) (3. e5 
{+61=85-32} Bf5 {+58=83-31}) (3. exd5 {+40=72-21} cxd5 {+40=72-21}) 3... dxe4 
{+62=127-34}) (1... g6 {+55=63-29} 2. d4 {+55=61-29} Bg7 {+48=52-25} 3. Nc3 
{+34=26-17} (3. Nf3 {+10=21-5} d6 {+9=21-5}) 3... c6 {+16=11-13} (3... d6 
{+18=15-4})) (1... d6 {+119=164-53} 2. d4 {+113=163-50} Nf6 {+90=127-36} (2... 
g6 {+23=34-13} 3. Nc3 {+17=20-9} Bg7 {+15=19-8}) 3. Nc3 {+75=112-35} g6 
{+66=104-31}) (1... Nf6 {+44=48-22} 2. e5 {+42=43-19} Nfd5 {+42=43-19} 3. d4 
{+39=39-18} d6 {+39=39-18}) (1... d5 {+37=21-16} 2. exd5 {+36=21-16} Qxd5 
{+34=17-11} 3. Nc3 {+31=16-10} Qa5 {+30=16-10}) (1... Nc6 {+12=12-3}) 2. d3 
{+17=36-7} (2. d4 {+356=659-201} d5 {+356=658-201} 3. Nd2 {+109=268-75} (3. Nc3 
{+217=326-107} Nf6 {+74=129-40} (3... dxe4 {+17=40-1}) (3... Bb4 
{+121=146-60})) (3. exd5 {+8=31-8} exd5 {+8=31-8}) (3. e5 {+22=33-11} c5 
{+20=30-10}) 3... c5 {+56=189-45} (3... Nf6 {+19=26-15}) (3... a6 {+11=27-8}) 
(3... Nc6 {+7=9-4})) 2... d5 {+11=24-4} 3. Nd2 {+9=20-3} Nf6 {+6=14-3}
Another output format is easier to read.

Code: Select all

1. e4 e6 2. d3 d5 3. Nd2 Nf6  {+6=14-3}
          2. d4 d5 3. Nd2 c5  {+56=189-45}
                    3. ... Nf6  {+19=26-15}
                    3. ... a6  {+11=27-8}
                    3. ... Nc6  {+7=9-4}
                    3. Nc3 Nf6  {+74=129-40}
                    3. ... dxe4  {+17=40-1}
                    3. ... Bb4  {+121=146-60}
                    3. exd5 exd5  {+8=31-8}
                    3. e5 c5  {+20=30-10}
1. ... e5 2. Bc4 Nf6 3. d3 Nc6  {+3=13-5}
          2. Nf3 Nf6 3. Nxe5 d6  {+40=151-20}
                    3. Nc3 Nc6  {+8=15-3}
                    3. d4 Nxe4  {+34=43-5}
          2. ... Nc6 3. Bb5 Nf6  {+47=66-27}
                    3. ... a6  {+314=664-194}
                    3. ... Bc5  {+4=11-5}
                    3. ... g6  {+12=31-13}
                    3. ... Nd4  {+5=13-2}
                    3. Bc4 Bc5  {+32=51-15}
                    3. ... Nf6  {+31=47-13}
                    3. d4 exd4  {+32=62-18}
                    3. Nc3 Nf6  {+17=48-13}
          2. f4 exf4  {+12=11-6}
          2. Nc3 Nf6  {+8=24-4}
1. ... c5 2. Nf3 e6 3. d4 cxd4  {+213=337-108}
                    3. c3 d5  {+2=27-4}
                    3. Nc3 a6  {+8=13-6}
                    3. ... Nc6  {+6=19-5}
                    3. d3 Nc6  {+12=16-2}
          2. ... Nc6 3. d4 cxd4  {+176=302-88}
                    3. Bb5 g6  {+18=32-9}
                    3. ... e6  {+15=15-10}
                    3. Nc3  {+8=20-8}
          2. ... d6 3. d4 cxd4  {+466=736-314}
                    3. ... Nf6  {+23=25-14}
                    3. c3 Nf6  {+11=20-4}
                    3. Bb5+ Bd7  {+19=83-14}
                    3. ... Nc6  {+6=9-11}
                    3. ... Nd7  {+5=11-7}
                    3. Nc3  {+7=14-10}
          2. Nc3 e6 3. Nf3  {+8=16-7}
          2. ... d6 3. g3 Nc6  {+5=12-3}
                    3. f4  {+6=20-4}
          2. ... Nc6 3. g3 g6  {+18=35-15}
                    3. Nf3  {+6=16-10}
                    3. Nge2  {+12=13-2}
                    3. f4  {+7=7-6}
          2. c3 e6 3. d4 d5  {+5=14-4}
          2. ... d5 3. exd5 Qxd5  {+15=26-7}
          2. ... Nf6 3. e5 Nd5  {+10=38-10}
1. ... c6 2. d4 d5 3. Nd2 dxe4  {+62=127-34}
                    3. Nc3 dxe4  {+43=95-25}
                    3. e5 Bf5  {+58=83-31}
                    3. exd5 cxd5  {+40=72-21}
          2. c4 d5 3. exd5 cxd5  {+3=20-3}
          2. Nc3 d5 3. Nf3 Bg4  {+4=17-6}
          2. d3 d5 3. Nd2  {+8=18-8}
1. ... g6 2. d4 Bg7 3. Nc3 c6  {+16=11-13}
                    3. ... d6  {+18=15-4}
                    3. Nf3 d6  {+9=21-5}
1. ... d6 2. d4 Nf6 3. Nc3 g6  {+66=104-31}
          2. ... g6 3. Nc3 Bg7  {+15=19-8}
1. ... Nf6 2. e5 Nd5 3. d4 d6  {+39=39-18}
1. ... d5 2. exd5 Qxd5 3. Nc3 Qa5  {+30=16-10}
1. ... Nc6  {+12=12-3}
1. d4 Nf6 2. c4 e6 3. Nf3 d5  {+142=357-91}
                    3. ... b6  {+333=743-177}
                    3. ... Bb4+  {+84=198-44}
                    3. ... c5  {+42=52-25}
                    3. Nc3 Bb4  {+375=721-258}
                    3. ... d5  {+51=99-22}
                    3. ... c5  {+14=10-5}
                    3. g3 c5  {+8=22-10}
                    3. ... d5  {+28=108-22}
                    3. ... Bb4+  {+23=36-14}
          2. ... g6 3. Nc3 d5  {+171=292-110}
                    3. ... Bg7  {+274=384-173}
                    3. g3 c6  {+5=25-3}
                    3. ... Bg7  {+31=53-14}
                    3. Nf3 Bg7  {+55=111-27}
          2. ... c5 3. d5 b5  {+47=70-37}
                    3. ... g6  {+17=26-13}
                    3. ... e6  {+21=24-12}
                    3. ... e5  {+14=7-5}
                    3. ... d6  {+9=15-8}
                    3. Nf3 cxd4  {+13=10-10}
          2. ... c6 3. Nc3 d5  {+15=21-5}
          2. ... d6 3. Nc3 Nbd7  {+12=21-4}
          2. ... e5 3. dxe5 Ng4  {+5=14-2}
          2. Nf3 g6 3. Bf4 Bg7  {+4=16-12}
                    3. c4 Bg7  {+69=136-53}
                    3. g3 Bg7  {+24=58-11}
                    3. ... d5  {+4=16-0}
                    3. Bg5 Bg7  {+10=53-23}
                    3. c3 Bg7  {+4=14-3}
          2. ... e6 3. c4 b6  {+50=156-39}
                    3. ... Bb4+  {+13=39-11}
                    3. ... c5  {+17=22-13}
                    3. ... d5  {+11=36-6}
                    3. e3 c5  {+3=16-3}
                    3. ... b6  {+4=14-5}
                    3. Bg5 h6  {+5=17-6}
                    3. ... c5  {+11=37-9}
                    3. g3 b6  {+9=17-8}
                    3. ... b5  {+10=29-6}
          2. ... d5 3. c4 e6  {+24=81-14}
                    3. ... c6  {+12=19-5}
          2. ... c5 3. d5 b5  {+10=9-4}
                    3. ... g6  {+10=12-3}
          2. ... b6  {+4=23-1}
          2. ... d6  {+11=12-3}
          2. Bg5 Ne4 3. Bf4  {+9=18-7}
          2. ... e6  {+11=11-9}
1. ... d6 2. c4 e5 3. Nf3 e4  {+8=16-3}
          2. Nf3 Bg4 3. c4 Nd7  {+9=15-3}
          2. ... g6 3. c4 Bg7  {+7=10-6}
          2. e4 Nf6 3. f3  {+5=10-5}
                    3. Nc3 g6  {+17=25-12}
          2. ... g6 3. Nc3  {+7=12-2}
1. ... d5 2. c4 e6 3. Nc3 Be7  {+52=113-14}
                    3. ... c5  {+10=28-8}
                    3. ... c6  {+14=30-9}
                    3. ... Nf6  {+37=78-18}
                    3. ... Bb4  {+6=11-4}
                    3. Nf3 c6  {+5=16-2}
                    3. ... Nf6  {+29=73-18}
                    3. ... c5  {+14=13-2}
          2. ... dxc4 3. e3 Nf6  {+15=28-11}
                    3. Nf3 a6  {+16=35-8}
                    3. ... Nf6  {+25=79-23}
                    3. e4 Nf6  {+18=36-15}
                    3. ... c5  {+8=5-8}
                    3. ... Nc6  {+9=11-4}
                    3. ... e5  {+16=32-3}
          2. ... c6 3. e3 Nf6  {+11=35-7}
                    3. Nc3 Nf6  {+100=228-73}
                    3. ... e5  {+8=8-6}
                    3. Nf3 Nf6  {+118=281-85}
                    3. cxd5 cxd5  {+8=30-6}
          2. Nf3 Nf6 3. c4 c6  {+21=43-14}
                    3. ... dxc4  {+13=48-3}
                    3. ... e6  {+4=23-5}
          2. ... c6 3. c4  {+7=18-3}
          2. ... e6 3. c4 dxc4  {+5=14-2}
          2. ... c5  {+4=14-4}
          2. Bg5  {+11=17-7}
1. ... e6 2. c4 b6  {+10=16-9}
          2. ... Bb4+ 3. Bd2  {+10=20-2}
          2. ... Nf6 3. Nf3 b6  {+10=18-4}
                    3. Nc3 Bb4  {+8=19-7}
          2. ... d5 3. Nc3  {+9=8-4}
          2. ... f5 3. g3 Nf6  {+22=13-7}
          2. Nf3 Nf6  {+7=13-4}
          2. ... f5  {+7=11-3}
          2. e4 d5 3. Nd2  {+5=15-0}
                    3. Nc3  {+2=16-6}
1. ... f5 2. Nc3  {+8=11-5}
          2. g3 Nf6 3. Bg2 g6  {+19=30-14}
          2. c4 Nf6  {+13=12-6}
          2. Nf3 Nf6  {+3=20-8}
1. ... g6 2. e4 Bg7  {+9=17-6}
          2. c4 Bg7  {+9=12-6}
1. ... c5 2. d5  {+6=10-4}
1. c4 Nf6 2. Nc3 g6 3. g3 Bg7  {+9=15-5}
                    3. e4 d6  {+16=14-12}
          2. ... e5 3. Nf3 Nc6  {+25=51-25}
          2. ... c5 3. Nf3 d5  {+11=7-4}
                    3. ... e6  {+11=25-6}
                    3. ... Nc6  {+7=10-3}
                    3. g3 e6  {+10=15-3}
          2. ... d5 3. cxd5 Nxd5  {+14=20-4}
          2. ... e6 3. Nf3 b6  {+16=27-6}
                    3. ... d5  {+18=32-6}
                    3. ... c5  {+7=15-3}
                    3. e4  {+9=21-3}
                    3. d4 Bb4  {+8=12-2}
          2. Nf3 g6  {+7=17-4}
          2. ... c6  {+3=16-1}
          2. ... c5 3. Nc3  {+6=11-4}
          2. ... e6 3. g3  {+5=20-2}
          2. ... b6 3. g3 Bb7  {+2=16-2}
          2. g3  {+16=25-7}
          2. d4 e6  {+4=15-8}
1. ... c6 2. e4 d5 3. exd5 cxd5  {+5=19-6}
          2. Nf3 d5  {+6=17-2}
          2. d4 d5 3. Nf3 Nf6  {+7=13-2}
                    3. Nc3  {+7=12-4}
1. ... e5 2. g3 Nf6 3. Bg2 d5  {+7=12-7}
          2. ... Nc6 3. Bg2 g6  {+7=18-8}
          2. Nc3 Nc6 3. g3 g6  {+15=55-12}
                    3. Nf3 Nf6  {+5=20-9}
          2. ... Bb4 3. Nd5 Be7  {+10=6-5}
          2. ... d6 3. Nf3  {+9=11-4}
                    3. g3  {+12=13-2}
          2. ... Nf6 3. Nf3 Nc6  {+46=119-37}
                    3. g3 Bb4  {+4=16-4}
                    3. ... d5  {+10=5-5}
1. ... c5 2. Nf3 Nf6 3. g3  {+3=17-5}
                    3. Nc3 Nc6  {+19=41-5}
                    3. ... e6  {+19=41-9}
                    3. ... d5  {+9=19-4}
          2. ... Nc6 3. d4 cxd4  {+7=16-4}
                    3. Nc3 Nf6  {+6=13-2}
          2. ... g6  {+13=13-3}
          2. g3 g6 3. Bg2 Bg7  {+11=31-6}
          2. Nc3 g6  {+2=16-5}
          2. ... Nc6  {+4=14-3}
1. ... e6 2. Nf3 d5 3. d4 Nf6  {+7=15-3}
          2. ... Nf6 3. Nc3  {+4=12-4}
                    3. g3  {+3=17-3}
          2. g3 d5 3. Bg2 Nf6  {+10=22-6}
          2. Nc3 d5 3. d4 Be7  {+20=38-11}
                    3. ... Nf6  {+24=45-11}
          2. d4 d5 3. Nc3  {+7=13-3}
1. ... g6 2. d4 Bg7 3. Nc3  {+5=11-4}
          2. ... Nf6  {+13=11-2}
          2. Nc3 Bg7 3. g3  {+3=23-11}
          2. e4 Bg7 3. d4 d6  {+7=16-7}
1. ... f5  {+12=16-2}
1. ... b6  {+12=13-4}
1. Nf3 d5 2. d4 Nf6 3. c4 e6  {+33=96-14}
                    3. ... dxc4  {+6=55-5}
                    3. ... c6  {+26=52-7}
          2. ... e6 3. c4  {+11=16-1}
          2. ... c6 3. c4 Nf6  {+9=9-4}
          2. ... Bf5 3. c4 e6  {+6=13-3}
          2. c4 e6 3. g3  {+7=11-3}
          2. ... d4  {+8=16-9}
          2. ... c6 3. d4 Nf6  {+5=17-3}
                    3. e3  {+3=15-3}
          2. g3 Nf6 3. Bg2 c6  {+4=12-4}
          2. ... Bg4 3. Bg2  {+3=13-7}
          2. ... c6 3. Bg2 Bg4  {+12=24-6}
1. ... Nf6 2. c4 g6 3. Nc3 Bg7  {+54=83-21}
                    3. ... d5  {+13=46-5}
                    3. g3 Bg7  {+31=69-9}
          2. ... e6 3. Nc3 Bb4  {+44=75-14}
                    3. ... d5  {+22=71-8}
                    3. g3 d5  {+26=69-16}
                    3. ... b6  {+5=29-4}
                    3. d4 b6  {+12=18-6}
          2. ... c5 3. Nc3 Nc6  {+28=43-7}
                    3. ... d5  {+4=30-5}
                    3. ... e6  {+11=38-8}
                    3. g3 b6  {+6=24-4}
                    3. ... d5  {+6=14-0}
          2. ... b6 3. g3 Bb7  {+19=63-11}
                    3. ... c5  {+9=26-12}
                    3. d4 e6  {+5=14-1}
                    3. Nc3 Bb7  {+11=13-1}
          2. ... c6 3. Nc3 d5  {+8=16-4}
          2. d4 g6  {+8=31-4}
          2. ... e6 3. c4  {+7=13-5}
          2. ... d5  {+3=17-2}
          2. g3 b6 3. Bg2 Bb7  {+2=15-6}
          2. ... d5 3. Bg2 c6  {+12=31-13}
          2. ... g6 3. Bg2 Bg7  {+13=28-9}
                    3. b3 Bg7  {+5=14-2}
1. ... c5 2. c4 Nc6 3. Nc3 Nf6  {+9=12-3}
                    3. d4 cxd4  {+6=10-5}
          2. ... Nf6 3. Nc3 e6  {+5=25-4}
                    3. ... Nc6  {+6=16-0}
                    3. g3 b6  {+6=12-3}
          2. ... g6 3. d4  {+8=11-4}
          2. g3 Nc6  {+4=14-4}
          2. e4  {+12=11-3}
          2. b3  {+5=8-8}
1. ... e6  {+6=23-7}
1. ... d6 2. d4 Bg4  {+7=16-8}
1. ... g6 2. d4 Bg7  {+14=15-7}
          2. e4 Bg7 3. d4 d6  {+8=7-9}
          2. c4 Bg7  {+8=12-6}
1. ... f5 2. g3 Nf6 3. Bg2  {+11=19-2}
1. b3 e5 2. Bb2  {+7=7-6}
1. g3 d5 2. Bg2  {+8=23-10}
          2. Nf3  {+4=16-3}
1. ... g6 2. Bg2 Bg7  {+15=11-6}
1. ... e5  {+7=9-7}
Harald
Top
Dave_N
Posts: 153
Joined: Fri Sep 30, 2011 7:48 am

Re: Database storage methods

Post by Dave_N »

Perhaps, however how can this method handle very large Databases (>10million games) ?
Top
Dave_N
Posts: 153
Joined: Fri Sep 30, 2011 7:48 am

Re: Database storage methods

Post by Dave_N »

Harald wrote:The discussion would not be complete without this link:
http://www.gotw.ca/gotw/072.htm
"Data Formats and Efficiency. How good are you at choosing highly
compact and memory-efficient data formats? How good are you at writing
bit-twiddling code? This GotW gives you ample opportunity to exercise
both skills, as we consider efficient representations of chess games and a
BitBuffer to hold them."

And just for fun I add this:

This is a 'game' that is merged from all 27202 games in the database gm2600.pgn.
The +win=draw-loss numbers are written in comments.
I reduced this opening database 'game' to variants
with a maximum depth of 6 half moves and at least 20
played games with the help of some filter functions.

Code: Select all

1. e4 {+2725=4855-1579} (1. d4 {+3228=6480-2014} Nf6 {+2223=4463-1406} (1... d6 
{+108=156-51} 2. c4 {+20=29-9} (2. Nf3 {+39=64-18} Bg4 {+16=33-7} (2... g6 
{+15=24-10} 3. c4 {+8=11-6} Bg7 {+7=10-6}) 3. c4 {+13=21-3} Nd7 {+9=15-3}) (2. 
e4 {+42=60-23} Nf6 {+27=43-19} (2... g6 {+14=17-4} 3. Nc3 {+7=12-2}) 3. f3 
{+5=10-5} (3. Nc3 {+20=30-13} g6 {+17=25-12})) 2... e5 {+16=24-5} 3. Nf3 
{+14=19-5} e4 {+8=16-3}) (1... d5 {+658=1464-402} 2. c4 {+578=1247-351} (2. Nf3 
{+66=194-41} Nf6 {+42=121-22} (2... c6 {+8=23-8} 3. c4 {+7=18-3}) (2... e6 
{+7=27-5} 3. c4 {+6=21-4} dxc4 {+5=14-2}) (2... c5 {+4=14-4}) 3. c4 
{+39=114-22} c6 {+21=43-14} (3... dxc4 {+13=48-3}) (3... e6 {+4=23-5})) (2. Bg5 
{+11=17-7}) 2... e6 {+171=370-76} (2... dxc4 {+130=257-78} 3. e3 {+27=44-12} 
(3. Nf3 {+51=122-34} a6 {+16=35-8} (3... Nf6 {+25=79-23})) (3. e4 {+51=84-30} 
Nf6 {+18=36-15} (3... c5 {+8=5-8}) (3... Nc6 {+9=11-4}) (3... e5 {+16=32-3})) 
3... Nf6 {+15=28-11}) (2... c6 {+264=607-187} 3. e3 {+13=42-8} (3. Nc3 
{+120=248-83} Nf6 {+100=228-73} (3... e5 {+8=8-6})) (3. Nf3 {+121=285-89} Nf6 
{+118=281-85}) (3. cxd5 {+8=30-6} cxd5 {+8=30-6}) 3... Nf6 {+11=35-7}) 3. Nc3 
{+120=263-53} (3. Nf3 {+49=105-23} c6 {+5=16-2} (3... Nf6 {+29=73-18}) (3... c5 
{+14=13-2})) 3... Be7 {+52=113-14} (3... c5 {+10=28-8}) (3... c6 {+14=30-9}) 
(3... Nf6 {+37=78-18}) (3... Bb4 {+6=11-4})) (1... e6 {+137=225-81} 2. c4 
{+101=131-55} (2. Nf3 {+20=46-12} Nf6 {+7=13-4} (2... f5 {+7=11-3})) (2. e4 
{+14=44-12} d5 {+14=38-10} 3. Nd2 {+5=15-0} (3. Nc3 {+2=16-6})) 2... b6 
{+10=16-9} (2... Bb4+ {+14=28-7} 3. Bd2 {+10=20-2}) (2... Nf6 {+30=54-21} 3. 
Nf3 {+18=34-12} (3. Nc3 {+10=20-8} Bb4 {+8=19-7}) 3... b6 {+10=18-4}) (2... d5 
{+16=11-7} 3. Nc3 {+9=8-4}) (2... f5 {+28=22-11} 3. g3 {+22=13-7} Nf6 
{+22=13-7})) (1... f5 {+57=107-50} 2. Nc3 {+8=11-5} (2. g3 {+31=51-28} Nf6 
{+27=48-26} 3. Bg2 {+27=47-26} g6 {+19=30-14}) (2. c4 {+13=14-6} Nf6 
{+13=12-6}) (2. Nf3 {+5=24-8} Nf6 {+3=20-8})) (1... g6 {+30=41-17} 2. e4 
{+15=23-7} (2. c4 {+9=13-7} Bg7 {+9=12-6}) 2... Bg7 {+9=17-6}) (1... c5 
{+7=14-4} 2. d5 {+6=10-4}) 2. c4 {+1832=3482-1113} (2. Nf3 {+360=911-253} g6 
{+121=309-108} (2... e6 {+151=414-111} 3. c4 {+94=255-69} (3. e3 {+7=31-8} c5 
{+3=16-3} (3... b6 {+4=14-5})) (3. Bg5 {+20=61-16} h6 {+5=17-6} (3... c5 
{+11=37-9})) (3. g3 {+28=64-18} b6 {+9=17-8} (3... b5 {+10=29-6})) 3... b6 
{+50=156-39} (3... Bb4+ {+13=39-11}) (3... c5 {+17=22-13}) (3... d5 
{+11=36-6})) (2... d5 {+42=114-21} 3. c4 {+41=109-19} e6 {+24=81-14} (3... c6 
{+12=19-5})) (2... c5 {+31=35-8} 3. d5 {+28=28-8} b5 {+10=9-4} (3... g6 
{+10=12-3})) (2... b6 {+4=23-1}) (2... d6 {+11=12-3}) 3. Bf4 {+4=16-12} (3. c4 
{+72=142-53} Bg7 {+69=136-53}) (3. g3 {+31=77-12} Bg7 {+24=58-11} (3... d5 
{+4=16-0})) (3. Bg5 {+10=55-23} Bg7 {+10=53-23}) (3. c3 {+4=14-3} Bg7 
{+4=14-3}) 3... Bg7 {+4=16-12}) (2. Bg5 {+26=54-35} Ne4 {+12=24-14} (2... e6 
{+11=11-9}) 3. Bf4 {+9=18-7}) 2... e6 {+1101=2352-669} (2... g6 {+543=881-334} 
3. Nc3 {+446=678-284} (3. g3 {+38=89-18} c6 {+5=25-3} (3... Bg7 {+31=53-14})) 
(3. Nf3 {+55=111-27} Bg7 {+55=111-27}) 3... d5 {+171=292-110} (3... Bg7 
{+274=384-173})) (2... c5 {+128=157-86} 3. d5 {+110=143-75} (3. Nf3 {+14=13-10} 
cxd4 {+13=10-10}) 3... b5 {+47=70-37} (3... g6 {+17=26-13}) (3... e6 
{+21=24-12}) (3... e5 {+14=7-5}) (3... d6 {+9=15-8})) (2... c6 {+24=29-7} 3. 
Nc3 {+16=22-5} d5 {+15=21-5}) (2... d6 {+28=46-14} 3. Nc3 {+25=36-10} Nd7 
{+12=21-4}) (2... e5 {+5=15-2} 3. dxe5 {+5=14-2} Ng4 {+5=14-2}) 3. Nf3 
{+601=1350-338} (3. Nc3 {+440=831-285} Bb4 {+375=721-258} (3... d5 {+51=99-22}) 
(3... c5 {+14=10-5})) (3. g3 {+59=168-46} c5 {+8=22-10} (3... d5 {+28=108-22}) 
(3... Bb4+ {+23=36-14})) 3... d5 {+142=357-91} (3... b6 {+333=743-177}) (3... 
Bb4+ {+84=198-44}) (3... c5 {+42=52-25})) (1. c4 {+789=1644-463} Nf6 
{+252=492-132} (1... c6 {+35=90-28} 2. e4 {+10=28-13} (2. Nf3 {+8=17-2} d5 
{+6=17-2}) (2. d4 {+17=33-8} d5 {+16=33-8} 3. Nf3 {+7=14-2} (3. Nc3 {+7=12-4}) 
3... Nf6 {+7=13-2}) 2... d5 {+8=25-12} 3. exd5 {+6=23-9} cxd5 {+5=19-6}) (1... 
e5 {+183=367-123} 2. g3 {+30=68-26} (2. Nc3 {+149=295-97} Nc6 {+35=94-29} (2... 
Bb4 {+19=20-9} 3. Ncd5 {+16=16-6} Be7 {+10=6-5}) (2... d6 {+29=27-10} 3. Nf3 
{+9=11-4} (3. g3 {+12=13-2})) (2... Nf6 {+65=153-48} 3. Nf3 {+47=121-38} (3. g3 
{+18=30-10} Bb4 {+4=16-4} (3... d5 {+10=5-5})) 3... Nc6 {+46=119-37}) 3. g3 
{+20=58-13} (3. Nf3 {+14=31-12} Nf6 {+5=20-9}) 3... g6 {+15=55-12}) 2... Nf6 
{+12=32-12} (2... Nc6 {+8=26-10} 3. Bg2 {+7=25-10} g6 {+7=18-8}) 3. Bg2 
{+12=32-12} d5 {+7=12-7}) (1... c5 {+117=277-63} 2. Nf3 {+86=188-36} (2. g3 
{+19=49-10} g6 {+12=33-6} 3. Bg2 {+11=31-6} Bg7 {+11=31-6}) (2. Nc3 {+11=38-15} 
g6 {+2=16-5} (2... Nc6 {+4=14-3})) 2... Nf6 {+52=133-24} (2... Nc6 {+19=38-7} 
3. d4 {+7=16-4} (3. Nc3 {+10=21-3} Nf6 {+6=13-2}) 3... cxd4 {+7=16-4}) (2... g6 
{+13=13-3}) 3. g3 {+3=17-5} (3. Nc3 {+48=108-18} Nc6 {+19=41-5} (3... e6 
{+19=41-9}) (3... d5 {+9=19-4}))) (1... e6 {+120=270-70} 2. Nf3 {+21=63-18} (2. 
g3 {+12=47-16} d5 {+11=39-14} 3. Bg2 {+11=32-13} Nf6 {+10=22-6}) (2. Nc3 
{+76=128-33} d5 {+55=98-25} 3. d4 {+55=97-24} Be7 {+20=38-11} (3... Nf6 
{+24=45-11})) (2. d4 {+10=32-3} d5 {+8=22-3} 3. Nc3 {+7=13-3}) 2... d5 
{+13=30-10} (2... Nf6 {+7=33-8} 3. Nc3 {+4=12-4} (3. g3 {+3=17-3})) 3. d4 
{+7=17-6} Nf6 {+7=15-3}) (1... g6 {+56=117-40} 2. d4 {+24=30-6} (2. Nc3 
{+14=43-18} Bg7 {+12=32-14} 3. g3 {+3=23-11}) (2. e4 {+13=21-11} Bg7 {+7=16-7} 
3. d4 {+7=16-7} d6 {+7=16-7}) 2... Bg7 {+11=18-4} (2... Nf6 {+13=11-2}) 3. Nc3 
{+5=11-4}) (1... f5 {+12=16-2}) (1... b6 {+12=13-4}) 2. Nc3 {+195=323-101} (2. 
Nf3 {+31=122-15} g6 {+7=17-4} (2... c6 {+3=16-1}) (2... c5 {+7=20-4} 3. Nc3 
{+6=11-4}) (2... e6 {+11=46-3} 3. g3 {+5=20-2}) (2... b6 {+3=23-3} 3. g3 
{+3=16-2} Bb7 {+2=16-2})) (2. g3 {+16=25-7}) (2. d4 {+9=22-9} e6 {+4=15-8}) 
2... g6 {+31=40-21} (2... e5 {+26=61-28} 3. Nf3 {+25=51-25} Nc6 {+25=51-25}) 
(2... c5 {+48=73-22} 3. Nf3 {+34=44-13} (3. g3 {+14=29-9} e6 {+10=15-3}) 3... 
d5 {+11=7-4} (3... e6 {+11=25-6}) (3... Nc6 {+7=10-3})) (2... d5 {+16=21-4} 3. 
cxd5 {+14=20-4} Nxd5 {+14=20-4}) (2... e6 {+66=118-26} 3. Nf3 {+49=81-19} (3. 
e4 {+9=21-3}) (3. d4 {+8=16-3} Bb4 {+8=12-2}) 3... b6 {+16=27-6} (3... d5 
{+18=32-6}) (3... c5 {+7=15-3})) 3. g3 {+9=17-6} (3. e4 {+16=14-12} d6 
{+16=14-12}) 3... Bg7 {+9=15-5}) (1. Nf3 {+800=1946-451} d5 {+179=465-93} (1... 
Nf6 {+440=1115-241} 2. c4 {+367=896-180} (2. d4 {+21=74-18} g6 {+8=31-4} (2... 
e6 {+9=20-8} 3. c4 {+7=13-5}) (2... d5 {+3=17-2})) (2. g3 {+51=136-39} b6 
{+2=17-6} (2... d5 {+20=50-15} 3. Bg2 {+19=49-15} c6 {+12=31-13}) (2... g6 
{+21=57-12} 3. Bg2 {+13=30-9} (3. b3 {+5=15-2} Bg7 {+5=14-2}) 3... Bg7 
{+13=28-9}) 3. Bg2 {+2=15-6} Bb7 {+2=15-6}) 2... g6 {+106=223-39} (2... e6 
{+126=321-63} 3. Nc3 {+77=170-22} (3. g3 {+34=108-26} d5 {+26=69-16} (3... b6 
{+5=29-4})) (3. d4 {+15=35-13} b6 {+12=18-6}) 3... Bb4 {+44=75-14} (3... d5 
{+22=71-8})) (2... c5 {+68=177-34} 3. Nc3 {+49=118-22} (3. g3 {+15=55-7} b6 
{+6=24-4} (3... d5 {+6=14-0})) 3... Nc6 {+28=43-7} (3... d5 {+4=30-5}) (3... e6 
{+11=38-8})) (2... b6 {+49=132-33} 3. g3 {+32=94-29} (3. d4 {+5=16-2} e6 
{+5=14-1}) (3. Nc3 {+12=18-1} Bb7 {+11=13-1}) 3... Bb7 {+19=63-11} (3... c5 
{+9=26-12})) (2... c6 {+12=34-7} 3. Nc3 {+8=16-4} d5 {+8=16-4}) 3. Nc3 
{+67=130-26} (3. g3 {+32=73-9} Bg7 {+31=69-9}) 3... Bg7 {+54=83-21} (3... d5 
{+13=46-5})) (1... c5 {+93=197-62} 2. c4 {+66=146-39} (2. g3 {+10=32-11} Nc6 
{+4=14-4}) (2. e4 {+12=11-3}) (2. b3 {+5=8-8}) 2... Nc6 {+22=41-20} (2... Nf6 
{+27=79-14} 3. Nc3 {+16=55-8} (3. g3 {+10=20-5} b6 {+6=12-3}) 3... e6 {+5=25-4} 
(3... Nc6 {+6=16-0})) (2... g6 {+13=23-4} 3. d4 {+8=11-4}) 3. Nc3 {+14=26-10} 
(3. d4 {+6=10-5} cxd4 {+6=10-5}) 3... Nf6 {+9=12-3}) (1... e6 {+6=23-7}) (1... 
d6 {+17=28-17} 2. d4 {+10=23-13} Bg4 {+7=16-8}) (1... g6 {+46=67-26} 2. d4 
{+20=28-10} (2. e4 {+17=19-10} Bg7 {+8=8-9} 3. d4 {+8=8-9} d6 {+8=7-9}) (2. c4 
{+8=15-6} Bg7 {+8=12-6}) 2... Bg7 {+14=15-7}) (1... f5 {+12=38-5} 2. g3 
{+11=24-2} Nf6 {+11=20-2} 3. Bg2 {+11=19-2}) 2. d4 {+107=262-39} (2. c4 
{+30=90-25} e6 {+9=27-6} (2... d4 {+8=16-9}) (2... c6 {+8=36-7} 3. d4 {+5=17-3} 
(3. e3 {+3=15-3}) 3... Nf6 {+5=17-3}) 3. g3 {+7=11-3}) (2. g3 {+37=102-23} Nf6 
{+8=32-7} (2... Bg4 {+3=14-7} 3. Bg2 {+3=13-7}) (2... c6 {+15=30-6} 3. Bg2 
{+14=30-6} Bg4 {+12=24-6}) 3. Bg2 {+8=32-7} c6 {+4=12-4}) 2... Nf6 {+66=206-26} 
(2... e6 {+12=19-1} 3. c4 {+11=16-1}) (2... c6 {+15=16-5} 3. c4 {+15=14-5} Nf6 
{+9=9-4}) (2... Bf5 {+7=14-3} 3. c4 {+6=13-3} e6 {+6=13-3}) 3. c4 {+65=203-26} 
e6 {+33=96-14} (3... dxc4 {+6=55-5}) (3... c6 {+26=52-7})) (1. b3 {+11=16-13} 
e5 {+7=7-6} 2. Bb2 {+7=7-6}) (1. g3 {+38=75-36} d5 {+12=39-13} (1... g6 
{+16=13-6} 2. Bg2 {+15=12-6} Bg7 {+15=11-6}) (1... e5 {+7=9-7}) 2. Bg2 
{+8=23-10} (2. Nf3 {+4=16-3})) 1... e6 {+376=704-213} (1... e5 {+653=1337-361} 
2. Bc4 {+16=30-9} (2. Nf3 {+609=1258-336} Nf6 {+88=229-29} (2... Nc6 
{+517=1021-306} 3. Bb5 {+396=801-243} (3. Bc4 {+65=103-28} Bc5 {+32=51-15} 
(3... Nf6 {+31=47-13})) (3. d4 {+32=62-18} exd4 {+32=62-18}) (3. Nc3 
{+22=49-14} Nf6 {+17=48-13}) 3... Nf6 {+47=66-27} (3... a6 {+314=664-194}) 
(3... Bc5 {+4=11-5}) (3... g6 {+12=31-13}) (3... Nd4 {+5=13-2})) 3. Nxe5 
{+40=151-20} (3. Nc3 {+10=21-4} Nc6 {+8=15-3}) (3. d4 {+37=57-5} Nxe4 
{+34=43-5}) 3... d6 {+40=151-20}) (2. f4 {+14=14-6} exf4 {+12=11-6}) (2. Nc3 
{+12=30-7} Nf6 {+8=24-4}) 2... Nf6 {+13=29-8} 3. d3 {+12=25-8} Nc6 {+3=13-5}) 
(1... c5 {+1178=2016-741} 2. Nf3 {+1044=1744-638} (2. Nc3 {+76=154-64} e6 
{+13=31-11} (2... d6 {+20=45-14} 3. g3 {+8=13-5} (3. f4 {+6=20-4}) 3... Nc6 
{+5=12-3}) (2... Nc6 {+43=75-36} 3. g3 {+18=36-16} (3. Nf3 {+6=16-10}) (3. Ne2 
{+12=13-2}) (3. f4 {+7=7-6}) 3... g6 {+18=35-15}) 3. Nf3 {+8=16-7}) (2. c3 
{+38=88-26} e6 {+7=14-4} (2... d5 {+15=29-8} 3. exd5 {+15=26-7} Qxd5 
{+15=26-7}) (2... Nf6 {+11=38-11} 3. e5 {+10=38-10} Nd5 {+10=38-10}) 3. d4 
{+5=14-4} d5 {+5=14-4}) 2... e6 {+264=441-130} (2... Nc6 {+229=384-124} 3. d4 
{+176=302-88} (3. Bb5 {+41=61-26} g6 {+18=32-9} (3... e6 {+15=15-10})) (3. Nc3 
{+8=20-8}) 3... cxd4 {+176=302-88}) (2... d6 {+546=904-379} 3. d4 
{+489=761-328} (3. c3 {+11=20-4} Nf6 {+11=20-4}) (3. Bb5+ {+30=103-32} Bd7 
{+19=83-14} (3... Nc6 {+6=9-11}) (3... Nd7 {+5=11-7})) (3. Nc3 {+7=14-10}) 3... 
cxd4 {+466=736-314} (3... Nf6 {+23=25-14})) 3. d4 {+213=337-108} (3. c3 
{+6=28-4} d5 {+2=27-4}) (3. Nc3 {+22=39-12} a6 {+8=13-6} (3... Nc6 {+6=19-5})) 
(3. d3 {+14=20-3} Nc6 {+12=16-2}) 3... cxd4 {+213=337-108}) (1... c6 
{+250=488-140} 2. d4 {+210=390-114} (2. c4 {+15=43-6} d5 {+11=33-5} 3. exd5 
{+6=23-3} cxd5 {+3=20-3}) (2. Nc3 {+10=28-8} d5 {+10=27-8} 3. Nf3 {+8=21-6} Bg4 
{+4=17-6}) (2. d3 {+11=23-11} d5 {+8=18-8} 3. Nd2 {+8=18-8}) 2... d5 
{+210=388-114} 3. Nd2 {+63=131-34} (3. Nc3 {+44=97-25} dxe4 {+43=95-25}) (3. e5 
{+61=85-32} Bf5 {+58=83-31}) (3. exd5 {+40=72-21} cxd5 {+40=72-21}) 3... dxe4 
{+62=127-34}) (1... g6 {+55=63-29} 2. d4 {+55=61-29} Bg7 {+48=52-25} 3. Nc3 
{+34=26-17} (3. Nf3 {+10=21-5} d6 {+9=21-5}) 3... c6 {+16=11-13} (3... d6 
{+18=15-4})) (1... d6 {+119=164-53} 2. d4 {+113=163-50} Nf6 {+90=127-36} (2... 
g6 {+23=34-13} 3. Nc3 {+17=20-9} Bg7 {+15=19-8}) 3. Nc3 {+75=112-35} g6 
{+66=104-31}) (1... Nf6 {+44=48-22} 2. e5 {+42=43-19} Nfd5 {+42=43-19} 3. d4 
{+39=39-18} d6 {+39=39-18}) (1... d5 {+37=21-16} 2. exd5 {+36=21-16} Qxd5 
{+34=17-11} 3. Nc3 {+31=16-10} Qa5 {+30=16-10}) (1... Nc6 {+12=12-3}) 2. d3 
{+17=36-7} (2. d4 {+356=659-201} d5 {+356=658-201} 3. Nd2 {+109=268-75} (3. Nc3 
{+217=326-107} Nf6 {+74=129-40} (3... dxe4 {+17=40-1}) (3... Bb4 
{+121=146-60})) (3. exd5 {+8=31-8} exd5 {+8=31-8}) (3. e5 {+22=33-11} c5 
{+20=30-10}) 3... c5 {+56=189-45} (3... Nf6 {+19=26-15}) (3... a6 {+11=27-8}) 
(3... Nc6 {+7=9-4})) 2... d5 {+11=24-4} 3. Nd2 {+9=20-3} Nf6 {+6=14-3}
Another output format is easier to read.

Code: Select all

1. e4 e6 2. d3 d5 3. Nd2 Nf6  {+6=14-3}
          2. d4 d5 3. Nd2 c5  {+56=189-45}
                    3. ... Nf6  {+19=26-15}
                    3. ... a6  {+11=27-8}
                    3. ... Nc6  {+7=9-4}
                    3. Nc3 Nf6  {+74=129-40}
                    3. ... dxe4  {+17=40-1}
                    3. ... Bb4  {+121=146-60}
                    3. exd5 exd5  {+8=31-8}
                    3. e5 c5  {+20=30-10}
1. ... e5 2. Bc4 Nf6 3. d3 Nc6  {+3=13-5}
          2. Nf3 Nf6 3. Nxe5 d6  {+40=151-20}
                    3. Nc3 Nc6  {+8=15-3}
                    3. d4 Nxe4  {+34=43-5}
          2. ... Nc6 3. Bb5 Nf6  {+47=66-27}
                    3. ... a6  {+314=664-194}
                    3. ... Bc5  {+4=11-5}
                    3. ... g6  {+12=31-13}
                    3. ... Nd4  {+5=13-2}
                    3. Bc4 Bc5  {+32=51-15}
                    3. ... Nf6  {+31=47-13}
                    3. d4 exd4  {+32=62-18}
                    3. Nc3 Nf6  {+17=48-13}
          2. f4 exf4  {+12=11-6}
          2. Nc3 Nf6  {+8=24-4}
1. ... c5 2. Nf3 e6 3. d4 cxd4  {+213=337-108}
                    3. c3 d5  {+2=27-4}
                    3. Nc3 a6  {+8=13-6}
                    3. ... Nc6  {+6=19-5}
                    3. d3 Nc6  {+12=16-2}
          2. ... Nc6 3. d4 cxd4  {+176=302-88}
                    3. Bb5 g6  {+18=32-9}
                    3. ... e6  {+15=15-10}
                    3. Nc3  {+8=20-8}
          2. ... d6 3. d4 cxd4  {+466=736-314}
                    3. ... Nf6  {+23=25-14}
                    3. c3 Nf6  {+11=20-4}
                    3. Bb5+ Bd7  {+19=83-14}
                    3. ... Nc6  {+6=9-11}
                    3. ... Nd7  {+5=11-7}
                    3. Nc3  {+7=14-10}
          2. Nc3 e6 3. Nf3  {+8=16-7}
          2. ... d6 3. g3 Nc6  {+5=12-3}
                    3. f4  {+6=20-4}
          2. ... Nc6 3. g3 g6  {+18=35-15}
                    3. Nf3  {+6=16-10}
                    3. Nge2  {+12=13-2}
                    3. f4  {+7=7-6}
          2. c3 e6 3. d4 d5  {+5=14-4}
          2. ... d5 3. exd5 Qxd5  {+15=26-7}
          2. ... Nf6 3. e5 Nd5  {+10=38-10}
1. ... c6 2. d4 d5 3. Nd2 dxe4  {+62=127-34}
                    3. Nc3 dxe4  {+43=95-25}
                    3. e5 Bf5  {+58=83-31}
                    3. exd5 cxd5  {+40=72-21}
          2. c4 d5 3. exd5 cxd5  {+3=20-3}
          2. Nc3 d5 3. Nf3 Bg4  {+4=17-6}
          2. d3 d5 3. Nd2  {+8=18-8}
1. ... g6 2. d4 Bg7 3. Nc3 c6  {+16=11-13}
                    3. ... d6  {+18=15-4}
                    3. Nf3 d6  {+9=21-5}
1. ... d6 2. d4 Nf6 3. Nc3 g6  {+66=104-31}
          2. ... g6 3. Nc3 Bg7  {+15=19-8}
1. ... Nf6 2. e5 Nd5 3. d4 d6  {+39=39-18}
1. ... d5 2. exd5 Qxd5 3. Nc3 Qa5  {+30=16-10}
1. ... Nc6  {+12=12-3}
1. d4 Nf6 2. c4 e6 3. Nf3 d5  {+142=357-91}
                    3. ... b6  {+333=743-177}
                    3. ... Bb4+  {+84=198-44}
                    3. ... c5  {+42=52-25}
                    3. Nc3 Bb4  {+375=721-258}
                    3. ... d5  {+51=99-22}
                    3. ... c5  {+14=10-5}
                    3. g3 c5  {+8=22-10}
                    3. ... d5  {+28=108-22}
                    3. ... Bb4+  {+23=36-14}
          2. ... g6 3. Nc3 d5  {+171=292-110}
                    3. ... Bg7  {+274=384-173}
                    3. g3 c6  {+5=25-3}
                    3. ... Bg7  {+31=53-14}
                    3. Nf3 Bg7  {+55=111-27}
          2. ... c5 3. d5 b5  {+47=70-37}
                    3. ... g6  {+17=26-13}
                    3. ... e6  {+21=24-12}
                    3. ... e5  {+14=7-5}
                    3. ... d6  {+9=15-8}
                    3. Nf3 cxd4  {+13=10-10}
          2. ... c6 3. Nc3 d5  {+15=21-5}
          2. ... d6 3. Nc3 Nbd7  {+12=21-4}
          2. ... e5 3. dxe5 Ng4  {+5=14-2}
          2. Nf3 g6 3. Bf4 Bg7  {+4=16-12}
                    3. c4 Bg7  {+69=136-53}
                    3. g3 Bg7  {+24=58-11}
                    3. ... d5  {+4=16-0}
                    3. Bg5 Bg7  {+10=53-23}
                    3. c3 Bg7  {+4=14-3}
          2. ... e6 3. c4 b6  {+50=156-39}
                    3. ... Bb4+  {+13=39-11}
                    3. ... c5  {+17=22-13}
                    3. ... d5  {+11=36-6}
                    3. e3 c5  {+3=16-3}
                    3. ... b6  {+4=14-5}
                    3. Bg5 h6  {+5=17-6}
                    3. ... c5  {+11=37-9}
                    3. g3 b6  {+9=17-8}
                    3. ... b5  {+10=29-6}
          2. ... d5 3. c4 e6  {+24=81-14}
                    3. ... c6  {+12=19-5}
          2. ... c5 3. d5 b5  {+10=9-4}
                    3. ... g6  {+10=12-3}
          2. ... b6  {+4=23-1}
          2. ... d6  {+11=12-3}
          2. Bg5 Ne4 3. Bf4  {+9=18-7}
          2. ... e6  {+11=11-9}
1. ... d6 2. c4 e5 3. Nf3 e4  {+8=16-3}
          2. Nf3 Bg4 3. c4 Nd7  {+9=15-3}
          2. ... g6 3. c4 Bg7  {+7=10-6}
          2. e4 Nf6 3. f3  {+5=10-5}
                    3. Nc3 g6  {+17=25-12}
          2. ... g6 3. Nc3  {+7=12-2}
1. ... d5 2. c4 e6 3. Nc3 Be7  {+52=113-14}
                    3. ... c5  {+10=28-8}
                    3. ... c6  {+14=30-9}
                    3. ... Nf6  {+37=78-18}
                    3. ... Bb4  {+6=11-4}
                    3. Nf3 c6  {+5=16-2}
                    3. ... Nf6  {+29=73-18}
                    3. ... c5  {+14=13-2}
          2. ... dxc4 3. e3 Nf6  {+15=28-11}
                    3. Nf3 a6  {+16=35-8}
                    3. ... Nf6  {+25=79-23}
                    3. e4 Nf6  {+18=36-15}
                    3. ... c5  {+8=5-8}
                    3. ... Nc6  {+9=11-4}
                    3. ... e5  {+16=32-3}
          2. ... c6 3. e3 Nf6  {+11=35-7}
                    3. Nc3 Nf6  {+100=228-73}
                    3. ... e5  {+8=8-6}
                    3. Nf3 Nf6  {+118=281-85}
                    3. cxd5 cxd5  {+8=30-6}
          2. Nf3 Nf6 3. c4 c6  {+21=43-14}
                    3. ... dxc4  {+13=48-3}
                    3. ... e6  {+4=23-5}
          2. ... c6 3. c4  {+7=18-3}
          2. ... e6 3. c4 dxc4  {+5=14-2}
          2. ... c5  {+4=14-4}
          2. Bg5  {+11=17-7}
1. ... e6 2. c4 b6  {+10=16-9}
          2. ... Bb4+ 3. Bd2  {+10=20-2}
          2. ... Nf6 3. Nf3 b6  {+10=18-4}
                    3. Nc3 Bb4  {+8=19-7}
          2. ... d5 3. Nc3  {+9=8-4}
          2. ... f5 3. g3 Nf6  {+22=13-7}
          2. Nf3 Nf6  {+7=13-4}
          2. ... f5  {+7=11-3}
          2. e4 d5 3. Nd2  {+5=15-0}
                    3. Nc3  {+2=16-6}
1. ... f5 2. Nc3  {+8=11-5}
          2. g3 Nf6 3. Bg2 g6  {+19=30-14}
          2. c4 Nf6  {+13=12-6}
          2. Nf3 Nf6  {+3=20-8}
1. ... g6 2. e4 Bg7  {+9=17-6}
          2. c4 Bg7  {+9=12-6}
1. ... c5 2. d5  {+6=10-4}
1. c4 Nf6 2. Nc3 g6 3. g3 Bg7  {+9=15-5}
                    3. e4 d6  {+16=14-12}
          2. ... e5 3. Nf3 Nc6  {+25=51-25}
          2. ... c5 3. Nf3 d5  {+11=7-4}
                    3. ... e6  {+11=25-6}
                    3. ... Nc6  {+7=10-3}
                    3. g3 e6  {+10=15-3}
          2. ... d5 3. cxd5 Nxd5  {+14=20-4}
          2. ... e6 3. Nf3 b6  {+16=27-6}
                    3. ... d5  {+18=32-6}
                    3. ... c5  {+7=15-3}
                    3. e4  {+9=21-3}
                    3. d4 Bb4  {+8=12-2}
          2. Nf3 g6  {+7=17-4}
          2. ... c6  {+3=16-1}
          2. ... c5 3. Nc3  {+6=11-4}
          2. ... e6 3. g3  {+5=20-2}
          2. ... b6 3. g3 Bb7  {+2=16-2}
          2. g3  {+16=25-7}
          2. d4 e6  {+4=15-8}
1. ... c6 2. e4 d5 3. exd5 cxd5  {+5=19-6}
          2. Nf3 d5  {+6=17-2}
          2. d4 d5 3. Nf3 Nf6  {+7=13-2}
                    3. Nc3  {+7=12-4}
1. ... e5 2. g3 Nf6 3. Bg2 d5  {+7=12-7}
          2. ... Nc6 3. Bg2 g6  {+7=18-8}
          2. Nc3 Nc6 3. g3 g6  {+15=55-12}
                    3. Nf3 Nf6  {+5=20-9}
          2. ... Bb4 3. Nd5 Be7  {+10=6-5}
          2. ... d6 3. Nf3  {+9=11-4}
                    3. g3  {+12=13-2}
          2. ... Nf6 3. Nf3 Nc6  {+46=119-37}
                    3. g3 Bb4  {+4=16-4}
                    3. ... d5  {+10=5-5}
1. ... c5 2. Nf3 Nf6 3. g3  {+3=17-5}
                    3. Nc3 Nc6  {+19=41-5}
                    3. ... e6  {+19=41-9}
                    3. ... d5  {+9=19-4}
          2. ... Nc6 3. d4 cxd4  {+7=16-4}
                    3. Nc3 Nf6  {+6=13-2}
          2. ... g6  {+13=13-3}
          2. g3 g6 3. Bg2 Bg7  {+11=31-6}
          2. Nc3 g6  {+2=16-5}
          2. ... Nc6  {+4=14-3}
1. ... e6 2. Nf3 d5 3. d4 Nf6  {+7=15-3}
          2. ... Nf6 3. Nc3  {+4=12-4}
                    3. g3  {+3=17-3}
          2. g3 d5 3. Bg2 Nf6  {+10=22-6}
          2. Nc3 d5 3. d4 Be7  {+20=38-11}
                    3. ... Nf6  {+24=45-11}
          2. d4 d5 3. Nc3  {+7=13-3}
1. ... g6 2. d4 Bg7 3. Nc3  {+5=11-4}
          2. ... Nf6  {+13=11-2}
          2. Nc3 Bg7 3. g3  {+3=23-11}
          2. e4 Bg7 3. d4 d6  {+7=16-7}
1. ... f5  {+12=16-2}
1. ... b6  {+12=13-4}
1. Nf3 d5 2. d4 Nf6 3. c4 e6  {+33=96-14}
                    3. ... dxc4  {+6=55-5}
                    3. ... c6  {+26=52-7}
          2. ... e6 3. c4  {+11=16-1}
          2. ... c6 3. c4 Nf6  {+9=9-4}
          2. ... Bf5 3. c4 e6  {+6=13-3}
          2. c4 e6 3. g3  {+7=11-3}
          2. ... d4  {+8=16-9}
          2. ... c6 3. d4 Nf6  {+5=17-3}
                    3. e3  {+3=15-3}
          2. g3 Nf6 3. Bg2 c6  {+4=12-4}
          2. ... Bg4 3. Bg2  {+3=13-7}
          2. ... c6 3. Bg2 Bg4  {+12=24-6}
1. ... Nf6 2. c4 g6 3. Nc3 Bg7  {+54=83-21}
                    3. ... d5  {+13=46-5}
                    3. g3 Bg7  {+31=69-9}
          2. ... e6 3. Nc3 Bb4  {+44=75-14}
                    3. ... d5  {+22=71-8}
                    3. g3 d5  {+26=69-16}
                    3. ... b6  {+5=29-4}
                    3. d4 b6  {+12=18-6}
          2. ... c5 3. Nc3 Nc6  {+28=43-7}
                    3. ... d5  {+4=30-5}
                    3. ... e6  {+11=38-8}
                    3. g3 b6  {+6=24-4}
                    3. ... d5  {+6=14-0}
          2. ... b6 3. g3 Bb7  {+19=63-11}
                    3. ... c5  {+9=26-12}
                    3. d4 e6  {+5=14-1}
                    3. Nc3 Bb7  {+11=13-1}
          2. ... c6 3. Nc3 d5  {+8=16-4}
          2. d4 g6  {+8=31-4}
          2. ... e6 3. c4  {+7=13-5}
          2. ... d5  {+3=17-2}
          2. g3 b6 3. Bg2 Bb7  {+2=15-6}
          2. ... d5 3. Bg2 c6  {+12=31-13}
          2. ... g6 3. Bg2 Bg7  {+13=28-9}
                    3. b3 Bg7  {+5=14-2}
1. ... c5 2. c4 Nc6 3. Nc3 Nf6  {+9=12-3}
                    3. d4 cxd4  {+6=10-5}
          2. ... Nf6 3. Nc3 e6  {+5=25-4}
                    3. ... Nc6  {+6=16-0}
                    3. g3 b6  {+6=12-3}
          2. ... g6 3. d4  {+8=11-4}
          2. g3 Nc6  {+4=14-4}
          2. e4  {+12=11-3}
          2. b3  {+5=8-8}
1. ... e6  {+6=23-7}
1. ... d6 2. d4 Bg4  {+7=16-8}
1. ... g6 2. d4 Bg7  {+14=15-7}
          2. e4 Bg7 3. d4 d6  {+8=7-9}
          2. c4 Bg7  {+8=12-6}
1. ... f5 2. g3 Nf6 3. Bg2  {+11=19-2}
1. b3 e5 2. Bb2  {+7=7-6}
1. g3 d5 2. Bg2  {+8=23-10}
          2. Nf3  {+4=16-3}
1. ... g6 2. Bg2 Bg7  {+15=11-6}
1. ... e5  {+7=9-7}
Harald
Thanks, I remember your other post, this is one of the points that helped me in writing trees into a file without using RAM, because I realized I might need 2GB for a large enough DB. I am taking the bit-twiddling test atm :)
Top
User avatar
phhnguyen
Posts: 1434
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Database storage methods

Post by phhnguyen »

I am not very sure what you really want to archive here: a new theory or a practical solution?

1) For theory, I think it should be OK for any new idea

2) For practical solution, you may consider some traditional or trick methods first.

For example, I can easily save half of my database size (which stores moves as "normal" ways) by using compression: first divide data into chunks and then compress them.

Note that once you replace moves by hash values, typical compressors won't work well because of those random-like values so you can not get good ratio as before. It means doing extra work to compress may gain almost nothing.

The "traditional" way can also easily save you from headache, time, space, memory as well as computing (it may run faster than one with hash keys) :))

Just my 50c :)
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Database storage methods

Post by bob »

JuLieN wrote:
Rebel wrote:One compression idea is to store a move (usually 2 bytes, or 2x6=12 bits) as an 8-bit number representing the number in the pseudo-legal move generation list. Takes a lot of extra processor time but saves disk space.
Right. In ICCA's January 1983 Newsletter, Kathe Spracklen (co-author of Sargon) writes a "Tutorial: Representation of an Opening Book Tree".

She discusses various methods and the one she finally chose was described to her by Ken Thompson (author of Belle).

As Ed said, each move in the tree is coded in a single byte: 6 bits are the index in the moves generation list, and the remaining two bits are coded "(" and ")" and help describe the tree.

To quote Kathe:
One bit, designated '(', indicates that there is another move choice available in this position. The other bit, designated ')', indicates that we have reached the end of that line.
(Actually, when you think of it, you only need 7 bits: six for displacement and one for the '(/)': 0='(', 1=')'.)

For instance, the following tree:

Code: Select all

e4 -- e5 -- Nf3 -- Nc6 -- Bb5 -- a6
 |       |        |       |        |
 |       |       f4     Nf6     Bc4
 |      c5 -- Nf3 -- d6 -- d4
 |       |               |
 |      e6            Nc6
d4 -- Nf6 -- c4 -- g6 -- Nc3
 |       |                |
 |       |               e6 -- Nc3 -- Bb4
 |       |                        |
 |       |                      Nf3
 |      d5 -- c4 -- c6 -- Nf3
 |       |       |      |
etc.   f5     Nf3   e6 -- Nc3
 |                      |
 |                     dxc4
Would translate as:

Code: Select all

(e4  (e5  (Nf3  (Nc6  (Bb5  a6)
                              Bc4)
                       Nf6)
               f4)
       (c5  Nf3  (d6  d4)
                     Nc6)
        e6)
(d4  (Nf6  c4  (g6  Nc3)
                     e6  (Nc3  Bb4)
                           Nf3)
       (d5  (c4  (c6  Nf3)
                    (e6  Nc3)
                     dxc4)
              Nf3)
        f5)
etc.
Or, when stored:

Code: Select all

(e4(e5(Nf3(Nc6(Bb5 a6)Bc4)Nf6)f4)(c5 Nf3)(d6 d4)Nc6)e6)(d4(Nf6 c4(g6 Nc3)e6(Nc3 Bb4)Nf3)(d5(c4(c6 Nf3)(e6 Nc3)dxc4)Nf3)f5) etc.
Hope that helps. :)
Couple of points.

First, you need the full 8 bits for the index. There are positions with > 128 moves, which means 7 bits is not enough. The record is something like 230 legal moves.

Second, for chess engines, I don't think anyone stores a book in the way you describe, nor have they for many years. Problem is that transpositions are difficult to detect. Most just store a huge file of zobrist hash signatures. If you make a move in any position, and can find the zobrist signature in the book file, you know that was a book move.
Top

Return to “Computer Chess Club: Programming and Technical Discussions”