Checkers Algorithm

[chrome palm]

I am trying to define an algorithm to calculate legal moves for any given board state of checkers. For a players turn, I need to determine which pieces can take enemy pieces. And of the pieces which can take, I need to determine which path through the board can lead to the highest number of enemy pieces taken. For a normal piece, this process is not difficult to cyclically check every single space. But for kings, the number of potential routes through the board grows exponentially.

I'm not quite sure where to begin with this problem.

[rare inlet]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[empty lily]

I would hardly call this something that grows exponentially.
For algorithms dealing with small numbers (like 20 pieces), the naiive approach can often be the best. More "fancy" algorithms tend to have overhead in exchange for better performance for large data.

[chrome palm]

I was fighting with an AI trying to create a fully fledged algorithm for this and it gave me this and then gave up: "The essence of the challenge revolves around the combinatorial explosion of possible capture paths a king can take."

[empty lily]

What you should do first is write an algorithm for non kings.
Even if it something that you will have to discard later, getting an idea of what an algorithm could look like will be key

Second, for the kings example, your algorithm should take into account that any sub-path that ends in the same location and captured the same pieces are fundamentally equivalent, as a way to cut down on redundant calculations

[chrome palm]

I already have a naive approach for non-kings, I've implemented in code a version that only checks the first jump, and it wouldn't be hard to adapt it to check each possible jump

but it does become exponentially more difficult for kings. The issue is, they can move any number of spaces before they capture, which isn't too difficult to manage its still only 4 possible choices, but AFTER they capture, they can move ANY NUMBER of spaces after they capture too. This leads to them needing to check first the same direction after they jump, and second two directions for every empty space after they jump. And each and every time there is a possible capture, there is an entire potential tree behind that jump that could lead to an entirely separate number of captures

[empty lily]

Well actually, after the first jump, there are only 3 possible jumps a king can make, because it can't retreat to recaputre the same piece

[chrome palm]

yes, but there are any number empty spaces after a capture that they can stop at, and for each one of those empty spaces, they need to check two additional directions.

This is international checkers, not american checkers. Its a 10x10 board, normal peices can capture backwards, and kings move like bishops, only they can jump over a peice to take it and continue to move after.

"The King can capture an opponent's checker or King by jumping over it. The King can jump any distance along a diagonal as long as the following conditions are met:

• The piece that will be captured must be on the same diagonal as the King.
• The King can not jump over a piece of its own color.
• The King can only jump over one piece at a time.
• There must be at least one empty square just beyond the piece that will be captured.

The King does not have to land in the first empty space beyond the piece it has jumped over. The King can choose what space it will land in, unless multiple jumps are available. In that case, the King must land in a space from which it can make the next jump.

Multiple jumps with the King can be complicated. When the King makes its first jump in a turn, it must land on a square that will allow it to make another jump, if another jump is possible. After landing, the King can turn and jump on a different diagonal, or it can jump on the same diagonal. The King must make its multiple jumps in a way that gives it the most jumps."

just for that picture up there alone, there are 4 separate paths the king could take that lead to various numbers of captures. by moving a single piece I can increase the number from 4 to 10

[empty lily]

What the fuck type of checkers is this

[chrome palm]

international checkers

https://www.itsyourturn.com/t_helptopic2130.html

[empty lily]

okay now I see the issue

Fuck that is hard

[chrome palm]

yeah, and I could brute force it and probably get it to function in most if not all cases, and even be only barely noticably slow. but I want to find a better way

like idk, a variation of the a* search algorithm

[chrome palm]

if anyone can help here im struggling

[rare inlet]

This question is being automatically marked as stale.
If your question has been answered, type !solved.
If your question is not answered feel free to bump the post or re-ask.
Take a look at !howto ask for tips on improving your question.

[stray nest]

Yooooo

[chrome palm]

you whats up

[sharp shore]

recursive search. with a passed state marking whether something was taken or not? + keeping the longest sequence of jumps