Checkers?

[jaroslav.tavgen]

Hi! Do you know any good canonical tutorial on how to build working checkers engine? By "working" I mean that it would CORRECTLY (!) generate moves. I don't need an AI (I want to implement it by myself), just working engine.

Unfortunately what I have found on the Internet is complete garbage. YouTube is pulling down your throat a "Tech with Tim" tutorial which is a complete disaster (not only the so-called "engine" is buggy but even the jumps are not mandatory there). Google search is showing me some JavaScript "engine" where pieces cannot turn into kings or do multiple jumps. In my opinion those "tutorials" are worse than if we didn't have any.

Is there anything that is actually working? For chess we have Bluefever which can teach a complete beginner how to build an engine for scratch. Anything similar for checkers?

Thank you!

[towforce]

If the available open source checkers projects and checkers tutorials don't meet your needs, why not write your own?

Here's a draft plan for you:

* draw board

* set the standard checkers starting position

* enable position set up

* enable the user to move a piece

* check the user's move is legal

* generate a list of legal moves to respond with

* build a search tree (limit the depth!): send a position to the tree generator, generate the legal moves in this position, send each generated position back to the tree generator as a recursive call

* write a simple evaluation function to determine how good a position is

* implement alpha beta pruning

* do some testing

By the time you've done all that, you'll have an engine that plays a decent game of checkers.

[jaroslav.tavgen]

If the available open source checkers projects and checkers tutorials don't meet your needs, why not write your own?

Here's a draft plan for you:

* draw board

* set the standard checkers starting position

* enable position set up

* enable the user to move a piece

* check the user's move is legal

* generate a list of legal moves to respond with

* build a search tree (limit the depth!): send a position to the tree generator, generate the legal moves in this position, send each generated position back to the tree generator as a recursive call

* write a simple evaluation function to determine how good a position is

* implement alpha beta pruning

* do some testing

By the time you've done all that, you'll have an engine that plays a decent game of checkers.

And this is exatcly what I am doing!

Here you go: https://jaroslavtavgen.com/
https://github.com/jaroslavtavgen/Perso ... e/checkers

Engine that allows you to play (i.e. make moves, no AI). I am not sure it is doing everything correctly but at the first glance it seems so.

Thank you very much for the check list!

[towforce]

Thank you very much for the check list!

My absolute pleasure!

[hgm]

If you are able to program such an engine yourself, why would you need a tutorial? Checkers seems a pretty simple game, (rulewise; perhaps not strategy-wise), and it should not be very hard to write a move generator for it that complies with the rules. If you know the rules, that is. I don't, as I was raised in a part of the world where we play International Draughts instead. And I understood the rules for Checkers are somewhat different.

I did program a very general engine for Chess variants, though. And one of the concepts it supports that was borrowed from Draughts-like games was 'prioritized moves'. Generated moves are assigned to a priority class, and imoves that are not in the highest non-empty class will be discarded after generation. This can be applied both at the global and the per-piece level: each piece can be assigned a 'fall-back' move set, and would only be allowed to make those when no moves from the primary set are available. But the moves from the primary set would not be mandatory; it would be allowed to move another piece even when such a move is available.

I used this to configure an AI for a chess variant I designed especially to demonstrate this feature: 'Siren Chess'. This has a piece (the Siren) which you must capture when you can capture it. And a piece (the Maniac) that cannot make a non-capture move when it can capture something.

[jaroslav.tavgen]

If you are able to program such an engine yourself, why would you need a tutorial? Checkers seems a pretty simple game, (rulewise; perhaps not strategy-wise), and it should not be very hard to write a move generator for it that complies with the rules. If you know the rules, that is. I don't, as I was raised in a part of the world where we play International Draughts instead. And I understood the rules for Checkers are somewhat different.

It's an illusion. I also started programming the checkers engine thinking that it would be easy-peasy. It wasn't.

The main issue are jumps. Since they are mandatory, and there are multiple jumps possible, you need to account for that. And it's not easy. Especially if you are then planning to also implement Minimax and you need to account for that as well.

I have chosen the approach where each jump is treated like a different move where the side was not switched. Not sure it is the right approach but it seems to be working so far. And I've copied the move system from Bluevefer 2013 guide for JavaScript chess engine (with variables "moves", "move_list_start" and piece lists). Once again, not sure it's the best approach but seems to be working so far.

I would suggest programming International Draughts would be even harder since the king is move powerful there.

[hgm]

I never wrote a Draughts program. But I think the rules of International Draughts are such that it is mandatory to capture the most stones you can. The move generator would have to keep track of the number of captured stones by each moves anyway; even the location of these captured stones should be part of the move description. So the move format must include a variable number of victims, and how many there actually are.

During the search you would extract the move with the largest number of victims, and search that first. This is not different from a Chess engine, where there is at most one victim, but you extract the move with the victim of the highest value. But where in Chess you then continue with extraction of the next-highest victim if you run out of captures on the most-valuable one, in Draughts the rules would not allow that. After you search the first extracted capture you can only continue until you run out of moves with that same number of victims, and then you are done.

In Chess you would sort the moves using the value of the attacker as a secondary sort key. In Draughts I would use the number of Kings amongst the victims as the secondary sort key, as I suppose that it is usually more profitable to capture Kings than ordinary stones. So the sort key could be something like 16 times the total number of victims plus the number of King victims. After having seen the highest sort key you should only accept sort keys with value >= that first sort key rounded down to the next-lower multiple of 16.

As far as generating the captures itself: I would do this recursively, with a routine that tries all possible jumps from a given starting location, and for each of those then calls itself with the position after the jump as new starting position, to see if it can make any more jumps. The rules for jumps might be tricky; I don't know the details for Checkers. In International Draughts the complication is that you cannot jump twice over the same stone, but it is also not like the captured stones already disappear partway during the move: already jumped-over stones remain on the board, and will block you.

Code: Select all

void IssueMove(int origin, int destination, int nrOfVictims, int victimArray[]) {
  ...
}

int JumpGen(int start, int square, int count, int victims[])
{
  int n = 0;
  for(step = ....) { // loop through all directions the piece is allowed to jump in
    if(board[square+step] == OPPONENT && board[square+2*step] == EMPTY) {
      n++; // count number of allowed jumps
      victims[count] = square + step; // record victim
      board[square+step] = FRIEND; // trick to make unpassable
      JumpGen(start, square+2*step, count+1, move);
      board[square+step] = OPPONENT;
    }
  }
  if(n == 0) IssueMove(start, square, count, victims); // cannot jump any further: move complete
}

[PK]

I wrote a bad commercial checkers/draughts engine for phones. It used large move struct, containing all the data needed to take back the move (list of captured pieces with locations and whether it is a man or a king). It necessitated recursive move generation. Once I was there, I could as well add several switches catering for different rules, even Turkish, where the movement is horizontal and vertical and not diagonal.

One funny property of checkers/draughts game family is that some moves may look different on the board and yet yield the same result. So the engine calculated move hash based on from square, to square and captured men in order to prune moves which repeated the same hash. This is the advantage of not splitting the move into several jumps.

Your approach (each jump trated as a move) was used in the oldest British draughts programs. Different paths with the same result appear in the game extremely rarely (for example capturing three men with the king and returning to the initial square).

Since the captures are forced, basic engine do not need quiescence search. More advanced engines, like Fabien's Scan, can use "quiescence search" that analyses moves putting pieces en prise.

[hgm]

Well, you would need to extend captures at the horizon to not get meaningless evaluations. Which is quiescence search. The only difference with a conventional Chess QS is that there is no stand-pat if there are any captures.

Your approach (each jump trated as a move) was used...

I am not sure to which 'you' you refer, but this was not my approach at al. (And I don't really see any other approach explained.) I don't treat jumps as complete moves, and only the location of the victims finally ends up tin the move descriptor next to the origin and destination of the moved piece. None of the squares where the moving piece jumped to.

The issue of duplicat moves happened to occur just now in the other discussion I am active in. In engines that use a TT I never saw this as a problem. In micro-Max I completely ignore it; it just searches the hash move first, and then all other moves from the move generation, which would also generate the hash move again. There isn't much cost in that, and a lot of simplicity. The point is that when you search the duplicat, you get an immediate hash cutoff in the daughter. On an entry you very recently used, so it will be in cache, and won't involve any memory delay.

So the cost of ignoring the duplicat is just the make/unmake and a low-latency hash probe. What I like about that is that it is a fixed cost. If you have to loop through the move list to find and remove the duplicat, the cost will scale with the length of the move list. So for complex chess variants with large boards and many pieces, doing it the 'proper way' probably is slower. Especially when you apply it to the hash move: the first search of that should cause a beta cutoff in >90% of the cases. And then you would never even encounter the duplicat.

The fixed overhead can be reduced by restructuring MakeMove() such that it first calculates the new hash key, without actually performing any of the move in the game state. And then does the hash probe. If you get a hash cutoff that would save you the trouble of actually making and unmaking the move. You could make actual Search and UnMake dependent on what MakeMove returns:

Code: Select all

if((score = MakeMove()) == INVALID) {
  score = -Search(...);
  UnMake();
}

Engines that do legality testing in MakeMove use similar code. When you detect an illegal move you can return -INFINITY.

For killer moves it is more tricky, as these might not be (pseudo-)legal in the current position. So you would either have to do elaborate testing to verify that from first principles, or you would have to find it in the move list (after which you could also easily remove the duplicat). It would be nice to have a way to speed up that search. But since you would be searching only two killers, and attempt that would require you to do something for every move in the list easily costs more than just fetching the move from the list and comparing it. When the move generator generates the moves per piece, however, so that at least the non-captures will initially be contiguous in the move list, you could store the move-list index of the first non-capture of every piece, on an auxiliary board or in the piece list. For vetting a killer you could then start at that move, and only run through the list until you reach a move with another from-square.

[chrisw]

Hi! Do you know any good canonical tutorial on how to build working checkers engine? By "working" I mean that it would CORRECTLY (!) generate moves. I don't need an AI (I want to implement it by myself), just working engine.

Unfortunately what I have found on the Internet is complete garbage. YouTube is pulling down your throat a "Tech with Tim" tutorial which is a complete disaster (not only the so-called "engine" is buggy but even the jumps are not mandatory there). Google search is showing me some JavaScript "engine" where pieces cannot turn into kings or do multiple jumps. In my opinion those "tutorials" are worse than if we didn't have any.

Is there anything that is actually working? For chess we have Bluefever which can teach a complete beginner how to build an engine for scratch. Anything similar for checkers?

Thank you!

Yes. I wrote the first Draughts program for Sinclair Spectrum back in 1982, it was basically the chess program hacked for draughts rules and written in asm. Sources lost in the mists of time.
If you try ChatGPT (or better, Grok3) it will virtually write a draughts engine for you. Prompt with C++ draughts move generator using bitboards. And then prompt with: thanks, pvs (or alpha beta) search, please.