This C++ source code is published under AGPL v3 license.
Read the associated step by step tutorial to build a perfect Connect 4 AI for explanations.
Connect 4 Solver
License: GNU Affero General Public License v3.0
This C++ source code is published under AGPL v3 license.
Read the associated step by step tutorial to build a perfect Connect 4 AI for explanations.
Hi,
I tried these positions: 55466554422442623[1-9] in the c++ solver and it is printing only positive scrores. But it should be all negative scores as in the online solver.
Is this a Bug?
Hi. I cloned your repository, digit "make" and "./c4solver", the program start but nothing is happening. Please tell me about my error to compile or run the program.
Thank you so much
Here is how I can reproduce the timing benchmarks (sort of), e.g. the Middle-Medium
:
$ wget https://blog.gamesolver.org/data/Test_L2_R2
$ cat Test_L2_R2 | cut -d " " -f 1 | time ./c4solver -w
...
1.74user 0.02system 0:01.76elapsed 99%CPU (0avgtext+0avgdata 84720maxresident)k
0inputs+0outputs (0major+20617minor)pagefaults 0swaps
So it prints 1.76s per 1000 benchmarks, which gives 1.76ms per benchmark on average. That is close to your benchmarks which give 1.717 ms median for the "weak solver".
How do you compute median and print the number of positions?
Lines 45 to 47 in d6ba50d
The score being computed here seems incorrect. It is calculating the score of the current node, but since we're effectively looking 2 moves ahead, the actual value of the score should be as if it were calculated two nodes down, which means it should be -(Position::WIDTH * Position::HEIGHT - 2 - P.nbMoves()) / 2
. This seems to significantly increase the performance of the algorithm.
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?
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?
Can u help me where can I delete this cout?
Hi,
I'm working on a JavaScript port of your Connect4 solver and I'm a bit confused by one line of code. Line 69 in the solver.cpp, inside the negamax algorithm code:
...
Position P2(P);
...
seems to be creating an instance of the Position class. What I don't get is that it looks like you are passing the parameter P
to the constructor and P
is itself an instance of the Position class. What's more, the default constructor function for the Position class does not seem to accept parameters. I'm not proficient in C++ and this maybe why I don't get what is going on here. Could you help. Thanks.
Hi, is it possible to generate such a book with the given code? I think I could use the generator somehow but I don´t know what I need as input.
When i try to download the opening books here https://github.com/MarkusThill/Connect-Four/tree/master/CFour/src/openingBook
I get .bat files with weird characters. Can someone help me sort this? This is urgent.
Hello,
I followed the tutorial on gamesolver.org,
but I didn't really understand how to implement that in order to play against the AI like on https://connect4.gamesolver.org/.
Someone has an implementation of this Solver ?
Thanks for your time :)
The current logic to compute position keys guarantees uniqueness but board positions that are a single move away have keys with poor locality. The transposition table access is thus all over the place and leads to large cache misses.
I ran a benchmark on the source code with valgrind and the results are in agreement with the observation.
On test set L2_R2, ~37.5 million calls to TranspositionTable::get
function with 99% read miss in data cache!!
Note: I did a build in RelWithDebInfo
configuration using CMake and the get
and put
functions were inlined in my case. Had to force compiler to not inline during benchmarking using __attribute__((noinline))
Posting this here if anyone can come up with a more cache friendly transposition table implementation.
Is there a way to assign a score from an empty position to the opening book? I couldn't find any ways to do it. The solver gives a zero score to it, but every other position is fine.
Pop-out is a variation of Connect 4 where you can in addition "pop" your own discs along with the normal drops. To pop, remove a disc from the bottom of the board, and the remaining discs in that column fall one by one.
Enough said, I recently created a function in position.hpp that make pop moves described above. Here's a sample on what I wrote so far:
void pop(int col) {
board col_mask = column_mask(col), botcol_mask = bottom_mask_col(col);
if (current_position & botcol_mask) {
if (!canPlay(col)) {
mask &= mask - (col_mask >> 1);
}
else {
mask ^= ((mask + botcol_mask) & col_mask) >> 1;
}
current_position ^= botcol_mask;
current_position = (current_position & (col_mask ^ board_mask)) ^ (current_position & col_mask) >> 1;
}
}
While it's not the most optimized, this code gets the job done. Yet I'm lost on how I can use this in the negamax function. Well, how can I use this function so that your solver searches the pop moves as well? There's a possibility that it may need a rewrite, since I'm not fluent on using bitwise operators.
I needed to generate a dataset of connect 4 positions from python. The quickest way to do so seemed to be to just call the main.cpp with subprocess. That worked alright, but was slow.
Long story short: solver.reset() triggers the transposition table to be reset. That means writing 80mb of zeros to memory. Even when you try to multi thread and run multiple solvers in parallel you won't see any speed ups, as the program is memory bandwidth bound, that had me quite confused for a few hours.
It might be prudent to remove the transposition table reset from the main, it might save somebody else some time debugging performance issues :)
Apart from this nasty trap: Great work on this solver, it really helps my current project a lot.
I was happy to see a beta solver link on the "old" site, but soon disappointed and troubled by the proposed changes. For me and my use case the beta is worse in almost every aspect, except the game board looks nice and modern at first glance.
Current solver: https://connect4.gamesolver.org/
Beta solver: https://ludolab.net/
Finally, what's lacking in the wild is an AI that plays like a human, in other words, one that plays at different levels or knows some strategies but not others. Two games are never the same.
I hope these issues can be remedied. Thank you for all your work.
To reproduce the bug you have to use Linux env.
Use 8x8 boards in Position class, so position_t is of type __int128, then try to print results like that
Position pos1, pos2; pos1.play("4848"); pos2.play("5151");; std::cout << "Key3 for sequence 4848: " << pos1.key3() << std::endl; std::cout << "Key3 for sequence 5151: " << pos2.key3() << std::endl;
The result is:
Key3 for sequence 4848: 974 Key3 for sequence 5151: 2924
I'm removed (commented) the possibly unnecessary code in Position.compute_winning_position:
//horizontal
position_t p = (position << (HEIGHT + 1)) & (position << 2 * (HEIGHT + 1));
r |= p & (position << 3 * (HEIGHT + 1));
// r |= p & (position >> (HEIGHT + 1));
p = (position >> (HEIGHT + 1)) & (position >> 2 * (HEIGHT + 1));
// r |= p & (position << (HEIGHT + 1));
r |= p & (position >> 3 * (HEIGHT + 1));
//diagonal 1
p = (position << HEIGHT) & (position << 2 * HEIGHT);
r |= p & (position << 3 * HEIGHT);
// r |= p & (position >> HEIGHT);
p = (position >> HEIGHT) & (position >> 2 * HEIGHT);
// r |= p & (position << HEIGHT);
r |= p & (position >> 3 * HEIGHT);
//diagonal 2
p = (position << (HEIGHT + 2)) & (position << 2 * (HEIGHT + 2));
r |= p & (position << 3 * (HEIGHT + 2));
// r |= p & (position >> (HEIGHT + 2));
p = (position >> (HEIGHT + 2)) & (position >> 2 * (HEIGHT + 2));
// r |= p & (position << (HEIGHT + 2));
r |= p & (position >> 3 * (HEIGHT + 2));
Hi! Can somebody help me how can I predict who will win?
Hi, could you explain what I have to enter in the command prompt? I always get "Invalid move".
Would it be possible to expand the online api to have another parameter "width" and height in order to have a game with 9 rows?
Hey, is there an efficient way to return the scores of next possible moves just the way it's done on the website under "Show Solution"?
One way is to call the entire program 7 times with the updated strings but that's making it slower.
What I believe is that we can return that in a single call but I'm not able to figure it out how since I'm not very familiar with the bitmap.
Any help would be highly appreciated!
Thanks!
UPDATE:
I am able to figure out how the bit masking is working, thanks to your blog post. I can now modify the code to return all possible moves with their scores but it's still going to be quite slow for initial moves specifically.
I read that you precomputed the opening data for the standard 6X7 board on the server which is why you're able to return results that fast. Can you please provide some information regarding how I could do the same on my system?
Thanks!
I apologize in advance because I'm a c++ novice, but I was hoping you could help me understand what '.depend' is in the make file. When I try running make, I get the following problem:
Also, when I try running ./c4solver, what kind of command line arguments are expected? Are board positions that I want to be evaluated supposed to be in '7x6.book' or are they entered directly into the command line? Can you please give an example of what '7x6.book' should look like or what the command line arguments should look like?
Thank you!
Hello, this is my first introduction to C++, so apologies in advance for asking obvious questions. I'm confused on putting it all together. Makefiles, terminal commands, etc.
I'm not looking for all the answers, though that would be nice too. Any good resources or primers on what to do after I've downloaded all the code from Git?
Trying to run make c4solver
or make generator
throws lots of c++ errors.
Also, out of interest, how did you intergrate this with connect4.gamesolver.org?
I'm not a c/c++ expert so there might be something I overlooked while trying to compile it but i cannot manage to make a compile the solver.
I tried : - using changing the flag to g++-8 but it did not made any difference.
- running the installer multiple times but it did not make a difference either.
- The CMakeList in a branch
Error seems to be linked to position_t
in the solver and more. cf images
I want to use this to try build a solver for an 8 by 8 board but I'm having a little trouble creating the opening book for it. Even how the opening book works in general I don't really understand.
How did you generate your opening book?
The bigger is only 32MB, dose it enough?
What are the rules for selecting positions?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.