Efficiently crushing an array

Programming Questions

asimes

Efficiently crushing an array

in Programming Questions • 1 years ago

(I'm not sure if there is a more technical term than crushing). I am making a chess environment and I am trying to speed optimize the generation of possible moves an AI could make. Right now I have a function that correctly finds every possible move the pieces could make on any given turn. Then next step is removing the moves that leave the King in check from the list (it is considered an illegal move to leave your King in check). For example:

int numPossibleMoves = 0;

getNumberOfPossibleMoves(); // Now numPossibleMoves is set to the correct number

int[] possibleMoves = new int[numPossibleMoves];

boolean[] illegalMove = new boolean[numPossibleMoves];

for (int i = 0; i < numPossibleMoves; i++) {

make the move

if (the move leaves the King in check) illegalMove[i] = true;

undo the move I tested

}

int keptMoves = 0;

int[] movesToKeep = new int[numPossibleMoves];

for (int i = 0; i < numPossibleMoves; i++) {

if (illegalMove[i] == false) {

movesToKeep[keptMoves] = possibleMoves[i];

keptMoves++;

}

for (int i = 0; i < keptMoves; i++) {

possibleMoves[i] = keptMoves[i];

}

numPossibleMoves = keptMoves;

And now my list of possible moves only has the moves that are legal up to the variable marker. The rest of the array beyond the marker is ignored. The problem is that this seems like a very long winded and slow method of removing illegal moves. There must be a better way of removing illegal moves that is faster, any ideas?

Replies(4)

asimes

Re: Efficiently crushing an array

1 years ago

I just realized I that the condition that checks if the move leaves the King in check can instead be used to test if the King is not in check. I still have the problem of making a temporary array and then setting possibleMoves to it. New example:

int numPossibleMoves = 0;

getNumberOfPossibleMoves(); // Now numPossibleMoves is set to the correct number

int[] possibleMoves = new int[numPossibleMoves];

int keptMoves = 0;

int[] movesToKeep = new int[numPossibleMoves];

for (int i = 0; i < numPossibleMoves; i++) {

make the move

if (the move DOES NOT LEAVE the King in check) {

movesToKeep[keptMoves] = possibleMoves[i];

keptMoves++;

}

undo the move I tested

}

for (int i = 0; i < keptMoves; i++) {

possibleMoves[i] = keptMoves[i];

}

numPossibleMoves = keptMoves;

jbum

Re: Efficiently crushing an array

1 years ago

Two methods:

If you use an ArrayList, instead of an array, you can kill the items in place, doing something like this:

for (int i = 0; i < possibleMoves.size(); ++i) {

if (/* move is bad */) {

possibleMoves.remove(i);

--i;

}

This allows you to use a single array structure, instead of two.

* * *

Another way I used to do it in C was to swap the bad moves to the end of the array, and then resize the array. This will work with a regular array, but you'll still have to resize it at the end. It is slightly more efficient, memory-wise, if less readable. I'm assuming you have a class called Move.

int numPossibleMoves = possibleMoves.length;

for (int i = 0; i < numPossibleMoves; ++i) {

if (/* move is bad */) {

// swap with end move

Move tmp = possibleMoves[i];

possibleMoves[i] = possibleMoves[numPossibleMoves-1];

possibleMoves[numPossibleMoves-1] = tmp;

--i;

--numPossibleMoves;

}

int numKeptMoves = numPossibleMoves;

keptMoves = new Move[numPossibleMoves];

System.arraycopy(possibleMoves,0,keptMoves,0, numKeptMoves);

asimes

Re: Efficiently crushing an array

1 years ago

@jbum The swap method should work, thanks. Someone else just posted a very similar problem:

http://forum.processing.org/topic/what-is-the-best-strategy-to-eliminate-objects-that-pass-a-certain-condition-in-an-array

I'm going to point them this way.

jbum

Re: Efficiently crushing an array

1 years ago

Cool. Note: I did not test my code, the way I usually do on this forum, so check for "off by 1" errors, which are common in this type of loop.