pascalpons / connect4 Goto Github PK

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, 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.

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.

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.

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?

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.

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?

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

How did you generate your opening book?
The bigger is only 32MB, dose it enough?
What are the rules for selecting positions?

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.

Hi! Can somebody help me how can I predict who will win?

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!

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.

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?

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.

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 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!

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.

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

Can u help me where can I delete this cout?

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.

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?

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, 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?

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?