Recursive Checkers AI

[Insectoid]

Since I haven't got access to any programming language other than Turing at the moment, and little enough computer time to bother using it, I've been thinking about a recursive checkers AI in my head (purely conceptual until I have time to actually code it). I have it mostly figured out except for one end-game result; two or more kings (typically few) of opposing sides are all that is left on the board, so in theory the game will never end as one king can always run away from the others. This has the potential to completely hang the game until it crashes with a stack overflow (I think). What's the best way to handle this?

[jcollins1991]

There's probably a better way to do it, but the easiest thing to do would probably just have a count of how many turns it's been since a piece has been captured, and when you go over a set limit just break the program... Something like 20 or 30 turns should be a reasonable point to stop at... Other than that it'd be a pain to try and figure out and would probably start getting into stuff like decidability and the halting problem >.<

[TheGuardian001]

It is still technically possible to win, if you can reduce the enemy kings down to one and then box it in a corner (if both teams get down to only 1 king remaining, I don't think there's a solution.) But that would be really difficult behavior to program, so I'm going to ignore that as an option.

Expanding on jcollins, you could have it so that the turn counter only kicks in if there are no pieces other than kings remaining.

So each turn, check through each piece on the board until you come to one that is not a king. If you don't find one, increment the counter. If the counter gets over a reasonable number, call it a stalemate.