filtering games

The search is recognizing move transpositions.

I cannot reproduce your problem, if I try your example 7...b6 will be shown. Probably it's only a mistake, please be sure that the database containing the game "1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.e5 Ne7 5.a3 Bxc3+ 6.bxc3 0-0 7.Qg4 b6 8.Bd3" is selected, probably you did select the empty Clipbase?

Thanks for sending the database, now I can explain what happens:

Play the moves 1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.a3 Bxc3 5.bxc3 Ne7 6.Qg4 0-0 7.e5. In the opening tree now you will see all the games containing this position, divided by next move in this position: 10 games with ...c5, and so on. If you play 7...b6, then more games will be shown. Look into the first one, this has the line 1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.e5 b6 5. 5.a3 ... You cannot see this game before playing 7...b6, because in this game Black has played b6 in fourth move, so the position search cannot find before b6 has been played.

The opening tree is doing an exact position search, anything else is not useful here. For example: if you show the game 1.c4 e5 2.d3 Nf6 3.e4 for a position after 1.e4 is played, this means if you show all games where White has played e2-e4 in any move number, you don't have a useful information for position 1.e4. After playing 1.e4 only the games with this position will be shown, but divided into sections related to the following move. Any chess database in working in this way: ChessBase, Scid, and so on.

In a future version it is planned to integrate a variation tree window, which will show all the games belonging to derived lines/variations, this will give a different view. Example: after playing 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 it will show all games divided into the following variations:

C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 "Exchange Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.d4 "Lasker Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.d4 exd4 6.Qxd4 Qxd4 7.Nxd4 Bd7
"Alekhine Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.Nc3 "Keres Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.Nc3 f6 6.d3 "Romanovsky Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.O-O "Barendregt-Fischer Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.O-O Bd6 "Classical Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.O-O Bg4 "Alapin Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.O-O Bg4 6.h3 h5 "Alapin Gambit"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.O-O Bg4 6.h3 h5 7.d3 Qf6 8.Be3 Ne7
9.Nbd2 Ng6 10.hxg4 hxg4 11.Ng5 Nf4 12.Qxg4 Qxg5 "Hernández Trap"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.O-O Qd6 "Bronstein Variation"
C68 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 bxc6 "Lutikov Variation"
C69 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Bxc6 dxc6 5.O-O f6 "Gligoric Variation"

In a given position there is always a limited
(and quite small) number of legal moves.

I think you're speaking about the next move in current position.

Wouldn't it be possible to search through these moves and
see if the arising position is present in the database?

And the opening tree is exactly doing this. Example: current position is 1.e4 e5 2.Nf3 Nc6. The opening tree now will find all games with

1.e4 e5 2.Nf3 Nc6 3.d4
1.e4 e5 2.Nf3 Nc6 3.Bb5
1.e4 e5 2.Nf3 Nc6 3.Bc4
...and so on

So probably I do not understand your question. Do you have an example?

Ok, I understand. The statistic is ok, even if the number of matches is lower. After ...b6 the number of moves is higher because it is now detecting some games where ...b6 has been played earlier, but the same position has been reached (with transposition), and before playing ...b6 these games couldn't be found. Due to the fact that the search is move transposition invariant, detecting more games when traversing forward is not seldom (in opening lines). I think you are confused if you think that the number of games must shrink with more moves.

After a second look I think I understand what your question is. The opening tree should show b6, but it doesn't. I have to proof this.

The move 6...b6 couldn't be found because there don't exists any game where b6 has been played in the position 1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.a3 Bxc3 5.bxc3 Ne7 6.Qg4 0-0 7.e5. This behavior is okay.

I understand that it would be fine if the search could even find all games after 7...b6, and the opening tree will show this move with a frequency of zero (because there is no game with this position and move b6). With current position search algorithm this is not possible (even ChessBase cannot find games with b6). I will proof whether the new position search algorithm, currently in development, will find these games, but this takes a while, because I cannot test before the algorithm is finished.

You're right that here is a hole. But this thing isn't easy, because this search depends on acceleration data, and it's likely that the computation of the acceleration data is forcing this hole. I will take a look at current algorithm, but I'm not optimistic, because for the compuation of the acceleration data I cannot do a search.

I'm more optmistic with my new algorthm, but I'm not yet clear about this, I have to do some analysis.

Because of the fact that the current algorithm is not erroneous, I will move this report to the feature requests.

Ticket moved from /p/scidb/bugs/91/

The current position search (for opening tree, which uses acceleration data) has a deficiency, it can only find a game A if any game exists with same position and a move (in this position) which will transpose to game A. Example, we have the following games in database:

(1) 1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.a3 Bxc3+ 5.bxc3 Ne7 6.Qg4 O-O 7.e5 f5

(2) 1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.e5 b6 5.a3 Bxc3+ 6.bxc3 Ne7 7.Qg4 O-O 8.Bd3

After playing 7.e5 in game (1) the move 7...b6, transposing into a position in game (2) after 7....O-O, will not be found, thus game (2) will not be found. This is a special transposition problem. It might be possible to enhance current algorithm, but it is not worth the effort.

With new position search algorithm (for opening tree; still in development) I will consider this special transposition problem. This will be a novelty, so far as I know any database application has this deficiency. But at the time of writing this I have not yet done a complete analysis whether this enhancement is indeed possible, this problem has a special complexity.

One thing has to be clarified: the current search algorithm is 100% correct, because it is searching for the current position. For example: the current position is

1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.a3 Bxc3+ 5.bxc3 Ne7 6.Qg4 O-O 7.e5

then it will find the game

1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.a3 Bxc3+ 5.bxc3 Ne7 6.Qg4 O-O 7.e5 f5

but it cannot find the game

1.e4 e6 2.d4 d5 3.Nc3 Bb4 4.e5 b6 5.a3 Bxc3+ 6.bxc3 Ne7 7.Qg4 O-O 8.Bd3

because in this game the search position does not occur. This means that this feature request is not a bugfix of the current algorithm, it's a request for a new feature: find all moves in current position, so that playing the move will find at least one game in database containing this position after playing the move. Furthermore all games belonging to the position after playing the move should be displayed.

We have two cases:

1. The search position is classified (this means it is a known opening position). With new opening tree algorithm it is expected that this feature can be realized without a significant loss in speed.

2. The search position is not classified (a middle game, or an end game position). Here the search is more complex, because we do not only test for the current position (like in original position search), we have also to test whether this game contains any position which will be reached after any possible move in search position.

The (current) position search algorithm is:

for all games in database do
    if this game contains current position then
       add this game and associate it with next move in game
    fi
od

The algorithm for new search is:

if our search position is classified then
   for all known moves in this position do
      for all games belonging to position after move do
         add this game and associate it with this move
      od
   od
fi

for all games not yet found do
   if position will be found in this game then
      add this game and associate it with next move in game
   else
      for each possible move in search position do
         if position after move will be found in this game then
            add this game and associate it with this move
         fi
      od
   fi
od