Playing checkers with a computer

Hello,

I recently started playing chess with a computer , which has proven to be very popular - an average of over 300 games are played with the computer every day.

I now started to investigate what options there are to do the same in checkers (especially Russian checkers).
And it seems that it's not as easy (as with chess) - there is no program that runs on Linux and has an API where you can give the position and which gives the best counter move (like stockfish does).
My information about checkers programs comes from the fmjd page . It shows that there are no Russian checkers programs that run on Linux, for example.

So what are the options?
1.1 million Russian checkers games have been played in Vint. And we have recorded the moves of all of those games (over 70 million in total!).
It is possible to make a robot play the game using this database of moves.
The main challenge with this solution is to record the board state for each move and then find that state as quickly as possible during the game and then make the corresponding move. And if there is a completely new state, the first random/accidental move must be made.

All of this is probably doable (finding a quick fix among 70 million records is a bit questionable, but you can only find out if you try it) but it's a pretty serious and time-consuming project.

Perhaps someone interested in this topic is graduating from university in the near future with a degree in computer science? This project would be very suitable for a bachelor's/master's thesis.

You can already play Surrender on a computer, go try it! The computer is still in development (analyzing the games played).

Now a little about the solution and the numbers.
I came up with a solution similar to the one I described in the previous post: the computer plays through all the games, puts all the positions and the moves made from those positions into a database.
He skips forced moves (blows) and also tries to evaluate each move (depending on the final outcome of the game).

We have 150,000 surrender games in our database, and the computer analyzed 40,000 games in the first day and night. And the analysis is getting slower and slower (because the database of game positions and moves is constantly growing). We'll see how long it takes to process 150K games and how well the computer starts to play.
For example, after playing the first 20K game, the computer responded to White's gh4 move with bc5, which is a pretty losing move. But after playing the 40K game, it was doing better.
Theoretically, we can also create different levels of difficulty, but we'll see.

Now it's time for the handover. We have 8x more Russian checkers games, which according to the current forecast means that the server will be analyzing these games for several weeks. But we'll get there when the handover is done and some results are in hand.

On the positive side - this analysis takes up about 25% of the server resources and the rest of the portal continues to function normally.

I'll continue the story here.

Each move is scored: If the player who made that move ultimately wins the game (purely by play), the move gets 3 points, timeout/opponent leaving the game gives one point, and loss then -3 and -1 points respectively.

The points are then added together on the same moves.
In addition, the popularity of the move is recorded (how many times this move has been made from this position).

Currently, the computer chooses the move with the highest score.

And one thing started to bother me, I mentioned this in the previous post: at the moment the computer responds to White's gh4 with bc5, which is a very bad move.
I then looked at the scores of different moves after White's gh4 and saw an interesting result (picture attached). Namely, all scores (grades) from this position are negative. So statistically, White has already won. . And now a statistical anomaly: since very few very bad moves (such as bc5) have been made, their absolute score is the highest and therefore the computer is currently choosing them.

I thought for a long time what to do. And the solution is quite interesting: Namely, instead of the absolute score, I should take a weighted score (grade / popularity). This formula gives the best move as fg5, which is also the most reasonable move from this position.
I will implement this change by the end of the week, but the analysis of the moves is still ongoing.

It seems that the analysis is currently running at a pace of 10 games per minute. There are still 90,000 games to analyze, which means it will take another 9,000 minutes, or 6 days. This in turn means that the server will actually analyze Russian checkers moves for a few months. But let it analyze. At some point, I will set up a game of Russian checkers against the computer, at first the computer plays poorly, then it gets better.

Some numbers: 59,000 games have been analyzed, the database contains:

• 1.1 million unique positions
• 1.2 million unique moves

One more thing to keep in mind: White has a decent advantage in surrender, so I recommend playing micro matches !

No, the database was missing an index, I added it.

Whereas before, one game was analyzed in 7 seconds, now 5 games are analyzed per second. Things are 30-40 times faster!

From today, the computer plays a little better:

* I also added to the database all the positions from which you can score in multiple ways (they weren't in the database before).
* If there is no move in the base, the computer now analyzes all moves (recursively until the forced moves/attacks end) and counts the pieces at the end. 1 checker = 3 stones (maybe there should be some other value for the chapel)?

Now we have to do the same thing in the handoff. And in addition, I'll make the computer learn from its own moves. If it keeps losing along one line, maybe at some point it will start to prefer other moves.

From today, the computer also learns from its own moves (it stores information about its moves in a database).

I also removed the option to offer a draw when playing with the computer - yesterday I saw how a user, from a clear losing position, offered the computer a draw. And the computer accepts all offers. This slightly distorts the evaluation of moves.

But another thought came to mind - if all moves in the database have a negative score at some point (making these moves means losing), the computer could try moves that are not yet in the database - maybe there is still some winning option?

There is a certain logic to surrendering, perhaps the computer should first learn that all of the opponent's pieces can be surrendered to the 1st piece, this skill is crucial in future game practice.

I posted updates this week:

Now you can choose between three levels of difficulty in Russian checkers: easy, medium and hard.
I invite people to test - is there any difference between these levels of difficulty?

Another important innovation was the improvement of the algorithm itself.
As I mentioned earlier in this post, the bot learns from games played in Vind and looks for moves in the database. It is quite an interesting fact that although almost 1.5 million games of Russian checkers have been played in Vind, in each new game , on average, 20 positions arise that have never existed before. So the bot has no good moves to take from the database in these cases.
This means that the algorithm that calculates the best move on the fly becomes critical. And I have significantly improved this algorithm in recent days.

What next?

1. There are several parameters in this algorithm that need to be tuned. For example, "depth of thought". Currently, it is 3 - 6 levels on the difficult level. Maybe these numbers should be increased when there are fewer pieces on the board....
2. I should now take on the task of handing it over first and make it work with the improved algorithm. And also introduce the difficulty levels into it.
3. In the long term, I would also like to offer computer-based play in international checkers, using the same solution as in Russian checkers.

I'm writing down the developments here so that future generations can read how the checkerboard developed.

So - until last week, the bot used a database of moves, and if it couldn't find a move, it calculated the move itself.

Last week I made a breakthrough in calculating this move.

Now I did a test where I had two computers play - one used a database of moves and the other calculated each move. And the result: 50/50!

Then I did a test where both bots used the database, but when there were less than 15 pieces left on the board, Computer 2 calculated all the moves (stopped using the database). And there was already a clear difference in favor of Computer 2.

So, from today on, a bot will play checkers, which at the end of the game will only think for itself, will not use the database. And it will probably be possible to delete millions of moves from the database.