CODEWITHSUNDEEP
javarecursiontree
jackthehipster
jackthehipster

Reputation: 1018

What's wrong with this recursion for checkers move generation?

I'm writing a simple checkers game in Java. The hard part so far is to generate a list of possible jumps for a piece, especially when there are several paths to jump. I have this recursion to find all possible paths to do a series of jumps. Here's some code:

/*
 * possibleJumps(Square pos, Board b, Move jump, ArrayList<Move> moves)
 * Add all possible jumps from the position b on board b to movelist moves. 
 */
void possibleJumps(Square pos, Board b, Move jump, ArrayList<Move> moves) {

    ArrayList<Move> simpleJ = this.simpleJumps(pos, b);

    //jump.addJumpSquare(pos);
    //System.out.println("check jump " + pos + " so far:" + jump);

    if (simpleJ.isEmpty()) {
        // no more jumps -> end this jump and add it to the list
        jump.endJump(pos);
        moves.add(jump);
        System.out.println("found jump" + jump);
        return;
    }

    for(Move j:simpleJ) {
        jump.addJumpSquare(j.jumped.get(0));    // add the jumped square to the jump path
        possibleJumps(j.to, b.doMove(j), new Move(jump), moves);
    }
}

Just to explain: simpleJumps generates a list of possible jumps over one square (so basically all attack moves). That works fine.

Here's the test board:

    A   B   C   D   E   F   G   H
  ---------------------------------
1 |   | o |   |   |   |   |   |   | 1 (0)
  ---------------------------------
2 |   |   |   |   |   |   |   |   | 2 (1)
  ---------------------------------
3 |   | o |   | o |   | o |   | o | 3 (2)
  ---------------------------------
4 |   |   |   |   |   |   |   |   | 4 (3)
  ---------------------------------
5 |   | o |   | o |   | o |   | o | 5 (4)
  ---------------------------------
6 |   |   |   |   |   |   |   |   | 6 (5)
  ---------------------------------
7 |   | o |   | O |   | o |   |   | 7 (6)
  ---------------------------------
8 | x |   |   |   |   |   |   |   | 8 (7)
  ---------------------------------

Here's the output I get:

found jumpa8c2 via b7-b5-b3-

found jumpa8c2 via b7-b5-d5-d3-

found jumpa8g2 via b7-b5-d5-d3-f3-

What it should be is:

found jumpa8c2 via b7-b5-b3-

found jumpa8c2 via b7-d5-d3-

found jumpa8g2 via b7-d5-f3-

This is, in principle, very similar to: Print all paths from root to leaf in a Binary tree which I read and used to get as far as I have gotten, but I'm missing something probably very simple...

Any ideas?

Upvotes: 0

Views: 1713

Answers (1)

piet.t
piet.t

Reputation: 11911

In this loop

for(Move j:simpleJ) {
    jump.addJumpSquare(j.jumped.get(0));    // add the jumped square to the jump path
    possibleJumps(j.to, b.doMove(j), new Move(jump), moves);
}

you are reusing the same jump for all possible moves - if you got 3 possible moves x,y,z you will end up with x, y and z added to the jump path.

So you either have to

  1. create a new jump-object (with appropriate state) at each iteration or
  2. remove the added square at the end of the iteration

Upvotes: 1

Related Questions