deepBookDist.dat contains 2 errors

[ddrhoadarmer]

I incorporated deepBookDist.dat into my AI. I believe I found two (and only two) states with incorrect values. My results match those from Pascal Pons's game solver, so the errors appear to be real.

Note: the values quoted below have been mapped from the book values to Pascal Pon's game values.

State 1 (3605375292):

. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. 2 1 2 1 . 2
2 1 2 1 1 1 2

The book returns a score of (75 - 69) / 2 = 3. The actual value is 7. Move values: -1, 0, 1, 7, 6, -2, 0 Confirmed by https://connect4.gamesolver.org/?pos=226744515337

State 2 (2101158888):

. . . . . . .
. . . . . . .
. 1 . . . . 1
. 1 . . . . 1
. 2 2 . . . 2
. 2 2 1 1 . 2

The book returns a score of (81 - 69) / 2 = 6. The actual value is 4. Move values: -14, 4, 4, 3, 3, -3, 4 Confirmed by https://connect4.gamesolver.org/?pos=475772722323

[MarkusThill]

Thanks for pointing out this interesting issue. I will take a look at it in the next days, if I find some time. How did you come to the conclusion that two (and only two) of the entries are wrong and not more?

[ddrhoadarmer]

I'm writing my AI in Swift and trying to get good performance on iPhones, attempting to keep all searches < 0.5 seconds, starting from a blank transposition table. Your code and documentation has been very helpful. Thank you!

To speed up move #13, I limit the alpha-beta window to the book value from the move12 database +/- 1 and return as soon as I find a move with a score that matches the book value. Something like this:

        if let bookValue = openingBookValue() {
            let alpha = bookValue - 1
            let beta = bookValue + 1

            for move in legalMoves {
                let value = moveValue(move: move, depth: d, alpha: alpha, beta: beta)

                if value == bookValue  {
                    return (move, value)
                }
            }

            fatalError()
        }

As a side-effect of my building a partial move13 database, the code above was run for every entry in the move12 database. Only two entries threw an error.

Looking at this again, I noticed that I'm only testing to make sure that I can find A move13 with the score indicated by the move12 database. I am NOT testing to make sure that the score from the move12 database is the best score achievable. I'll do some more testing...

[MarkusThill]

I see. That is a clever idea! I checked the two positions that you mentioned earlier with some other programs and their values seem to indeed be wrong in the 12-ply database. I currently cannot explain why that happend. I guess I had some bug in the code where I terminate the search at inner nodes of the search tree (e.g., if a double threat can be created) and somehow return the wrong distance to the win/loss. Unfortunately, I computed the database probably more than 10 years ago with some C-program and I do not find it at the moment to look for the bug. Maybe the bug is still apparent in the Java-program here on GitHub. However, I don't know if I will find time to check the program and look for this bug.

I also remember that I did some verification steps for the 12-ply database with distances. For example, I computed the 10-ply and 8-ply database again using only the 12-ply database and did not find any errors (the 8-ply database was mostly computed by John Tromp). However, I think I only checked the sign of the value (negative=loss, 0=draw, positive=win) and not the actual winning-distances. It might well be that something went wrong there.

If you gain any new insights (or find any other errors), I would be glad to hear from you. And if you want, you can correct these two errors in the database and send a pull request and I would add an attribution to my Readme.

[ddrhoadarmer]

I've finished validating the entire 12-ply database with distances -- without melting my 2011 MacBook Air!

I found a 3rd state with an incorrect value. I believe the remaining 4,200,896 entries are correct.

State 3 (1599634104):

        . 2 . . . . .
        . 1 . . . . .
        . 1 . . . . 1
        . 2 . . . . 2
        . 2 . . . 2 1
        . 1 . . . 2 1

The book returns a score of (71 - 69) / 2 = 1. The actual value is 2. Move values: -3, NA, 1, 0, 2, -2, -3 Confirmed by https://connect4.gamesolver.org/?pos=227677722622

A couple other things, in case someone else is looking at this years from now, these tips will save them a little time:

(1) The database excludes positions where player 1 can win on move 13. I don't think this is documented anywhere. So, I compute the value with something like this:

            openingBookValue_12(state: huffmanState(mirrored: false))
                ?? openingBookValue_12(state: huffmanState(mirrored: true))
                ?? 15

(2) The database entries are sorted by the position's Huffman code, treating it as an Int32 (signed integer). I resorted the database as a UInt32 (unsigned integer). This feels more natural to me.

[MarkusThill]

Nice Job! When I find some time inbetween, I will add your corrections to the database and your remarks to its description. I was anyways planning to clean up the code at some point and put the tree-search agent in an own GitHub repository.