search

PascalPons / connect4

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

Extending bitboards to 128-bits. #5

Closed TheTrustedComputer closed 5 years ago

TheTrustedComputer commented 6 years ago

The Fhourstones solver with an 8x8 opening book supports up to 128 bits using the __uint128_t keyword. I've changed the original Fhourstones code so that it can solve boards less than or equal to 128 bits instead of 64. I tested them both and one other Connect Four program that allows changing board sizes, and they're returning results just like the program is returning.

Since Fhourstones is a weak solver, it only gives me a win, draw, or loss result. This program on the other hand displays how many moves until a win or loss is reached, which what I want. For example, a win in 30 half-moves for the second player in a 13-ply position on 8x6 should return +3 by your solver. A drawn result is nothing special and is simply zero.

As I highly doubt you're going to support more than 64 bits, I want to do this myself. So far, I replaced uint64_t for <= 64 bits and __uint128_t for <= 128 bits with typedef and macros in position.hpp, and used the aliases in solver.cpp and MoveSorter.hpp (similar approach to Fhourstones's code). Then I got stuck on what to replace in TranspositionTable.hpp. What do I need to replace in TranspositionTable.hpp to store the 128-bit key/value pair?

PascalPons commented 6 years ago

Hi, supporting 128bits bitboard is in fact something I wanted to do it someday, but currently I'm not working much on that project.

One of the issue is the C++ standard does not define 128bits integer type. __uint128_t is a non standard GCC extension, probably other compiler also provide the same kind of extension but it is not (yet?) in the C++ standard.

That being said, I haven't looked yet at the implication of supporting 128bits boards in TranspositionTable.hpp.

TheTrustedComputer commented 6 years ago

The GNU G++ compiler is what makes solving 128-bit bitboards possible as shown on 8x8 (requires 72 bits). I don't think it's possible on other compilers though as it's not guaranteed. I tested the same code with Visual Studio, and it failed to compile.

With 128-bit bitboards, however, the board size can go as large as 11x10 (121 bits) compared to 8x7 (64 bits) in 64-bit bitboards. If I were to solve it on move one, it'll likely take years before a result comes to whom which side wins. But it's a good test to ensure the functions are working with already played positions using this method.

PascalPons commented 5 years ago

Hello, I pushed a commit to support 128bits boards using g++ non-portable __128 type.