Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm currently working on a minimax implementation for a game of checkers in C#. The minimax itself works fine if you ignore a few bugs I've yet to fix, but I'm having some problems finding a way I can properly create lists of 'Chain' moves, or moves with multiple jumps.

I've made several attempts at building a function which would take an attacking move and run it through some recursion to find all the possible branches, but so far the main result is that no attack move at all has been working.

Anyhow I'd appreciate some pointers on how to go about generating all the attack moves that could follow as a result of an attack. I'm guessing some form of recursion is going to be necessary at the very least.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

each time you find a jump check on the resulting board if that piece can jump again

this is easiest if you can clone a board state (or restore it again after the recursion)

basic code to find longest jump chain (easily adapted to find all jumps)

maxjumps;
foreach(piece: board){
    if piece.color = currentplayer
        jumps = canAttack(piece,board)
        if jumps.count>maxjump.count
            maxjump = jumps
}

and canAttack will be:

maxjumps;
foreach(move: piece.attackingMoves){
    if board.isValid(move)
        tmpboard = board.clone
        tmpboard.domove(move)
        jumps = move.concatJumps(canattack(move.resultpiece,tmpboard))
        if jumps.count>maxjump.count
            maxjump = jumps
}
return maxjumps

if you don't want to clone the board you do a undomove on the board right after the canattack call

share|improve this answer
    
Thanks. That seems to have done the trick, though there are still some issues because I'm retarded. Also I'll advise against cloning since last time I tried that it took up nearly all the memory on the computer storing the board. –  Noamyoungerm Apr 16 '13 at 21:33
    
unless you have a good pooling or garbage collection undoing is indeed better –  ratchet freak Apr 16 '13 at 22:04
    
Undoing always gives you a lot better performance, as it can use the L1 cache of the CPU (or maybe C# even uses registers in some cases?). I implemented a chess engine, which was -really- slow because of "cloning". A do/undo strategy is much faster... but for checkers this might be less an issue. It depends much on how you store your game state. If you just use a bitfield (e.g. use the class "BitArray"), cloning should be quite fast. But what ever you do, try to keep your board on the stack (=local variables, not initialized via "new Classname()"). –  Stefan K. May 14 '13 at 16:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.