search

PascalPons / connect4

Connect 4 Solver
GNU Affero General Public License v3.0
273 stars 50 forks source link

Wrong scores on sizes using close to 64 bits, CPU limitation? #2

Closed TheTrustedComputer closed 7 years ago

TheTrustedComputer commented 7 years ago

I was messing around with the solver program quite a lot, and I seem to reach a minor bug.

In the position 44444442222222655656666646552711111137735771 of size 7x8, I get a score of 2. This is not the correct score because the first player can win immediately with 5. However, the solver doesn't catch that, which the expected score would have been 6.

Could this be a limitation of the x64 CPU architecture?

PascalPons commented 7 years ago

Thanks for spotting the issue,

a 7x8 board will need 63 bits to encode and is stored in 64 bits integers. It is indeed highly possible that there is a bug somewhere that is not visible with a 7x6 board (using 49 bits).

I'll have a look at it, but so far the code has only been extensively tested on 6x7 board.

2017-09-12 22:19 GMT-07:00 TheTrustedComputer notifications@github.com:

I was messing around with the solver program quite a lot, and I seem to reach a minor bug.

In the position 44444442222222655656666646552711111137735771 of size 7x8, I get a score of 2. This is not the correct score because the first player can win immediately with 5. However, the solver doesn't catch that, which the expected score would have been 6.

Could this be a limitation of the x64 CPU architecture?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/PascalPons/connect4/issues/2, or mute the thread https://github.com/notifications/unsubscribe-auth/AF_Lgx6Jy5CprRv-zQ5fXa_PlpkrGw7Aks5sh2XQgaJpZM4PVl8O .

PascalPons commented 7 years ago

There was indeed a bug in compute_winning_position() function overflowing the 64bit bitboard for large boards. I updated the code to avoid overflow, it is a little less efficient but should be working on any board fitting into the 64bits. Now fixed in the last commit.

The last commit also fixes another bug that was always initializing the Transposition key/value sizes for a 6x7 board.

Tell me if you find other bugs on non-standard boards.