1
\$\begingroup\$

I'm making a chess engine that is going to run the function containing this loop many times a second, so I want it to be well optimized.

Which of these two implementations would perform faster?

This:

for(var j = idx-8, ji = 0; ji < 2; j-=8, ji++) {
    if(b[j] != 0) break;
    m[m.length] = [idx,j];
}

Or this:

for(var j = idx-8; j > idx-24; j-=8) {
    if(b[j] != 0) break;
    m[m.length] = [idx,j];
}

One does an extra calculation, the other defines another variable.

A working function containing the code (some of the variable names are slightly different due to me rewriting the program):

The parameter b is an array with 64 ints that describe a chess board. c is either -1 or 1. Whether or not the function is to find moves for black or white, -1 is black, 1 is white.

function possibleMoves(b,c) {

    pMoves = [];
    for (i = 0; i < 64; i++) {
        pieceNum = b[i];
        if (pieceNum*c > 0) {
            //Pawn
            if (pieceNum*c == 1) {
                if (c == 1 && i > 47 && i < 56) {                       
                    for (j = i - 8; j > i-24; j -= 8) {
                        if (b[j] != 0) break;
                        pMoves[pMoves.length] = [i,j];
                    }
                }
                else if (c == -1 && i > 7 && i < 16) {
                    for (j = i + 8; j < i+24; j += 8) {
                        if (b[j] != 0) break;
                        pMoves[pMoves.length] = [i,j];
                    }
                }
                else if (b[i-(c*8)] == 0) pMoves[pMoves.length] = [i,i-(c*8)];
                if (i%8 > 0 && b[i-(c*(8+c))]*c < 0) pMoves[pMoves.length] = [i,i-(c*(8+c))];
                if (i%8 < 7 && b[i-(c*(8-c))]*c < 0) pMoves[pMoves.length] = [i,i-(c*(8-c))];
            }
            //Knight
            else if (pieceNum*c == 2) {
                if (i < 48) {
                    if (i%8 < 7 && b[i+17]*c <= 0) pMoves[pMoves.length] = [i,i+17];
                    if (i%8 > 0 && b[i+15]*c <= 0) pMoves[pMoves.length] = [i,i+15];
                    if (i%8 < 6 && b[i+10]*c <= 0) pMoves[pMoves.length] = [i,i+10];
                    if (i%8 > 1 && b[i+6]*c <= 0) pMoves[pMoves.length] = [i,i+6];
                }
                else if (i < 56) {
                    if (i%8 < 6 && b[i+10]*c <= 0) pMoves[pMoves.length] = [i,i+10];
                    if (i%8 > 1 && b[i+6]*c <= 0) pMoves[pMoves.length] = [i,i+6];
                }
                if (i > 15) {
                    if (i%8 > 0 && b[i-17]*c <= 0) pMoves[pMoves.length] = [i,i-17];
                    if (i%8 < 7 && b[i-15]*c <= 0) pMoves[pMoves.length] = [i,i-15];
                    if (i%8 > 1 && b[i-10]*c <= 0) pMoves[pMoves.length] = [i,i-10];
                    if (i%8 < 6 && b[i-6]*c <= 0) pMoves[pMoves.length] = [i,i-6];
                }
                else if (i > 7) {
                    if (i%8 > 1 && b[i-10]*c <= 0) pMoves[pMoves.length] = [i,i-10];
                    if (i%8 < 6 && b[i-6]*c <= 0) pMoves[pMoves.length] = [i,i-6];
                }
            }
            //Bishop
            else if (pieceNum*c == 3) {
                for (j = i + 7; (j-7)%8 > 0 && j < 64; j += 7) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i + 9; (j-9)%8 < 7 && j < 64; j += 9) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 7; (j+7)%8 < 7 && j > -1; j -= 7) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 9; (j+9)%8 > 0 && j > -1; j -= 9) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
            }
            //Rook
            else if (pieceNum*c == 4) {
                for (j = i + 8; j < 64; j += 8) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 8; j > -1; j -= 8) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i + 1; (j+1) % 8 != 1; j++) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 1; (j+8) % 8 != 7; j--) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
            }
            //Queen
            else if (pieceNum*c == 5) {
                for (j = i + 8; j < 64; j += 8) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 8; j > -1; j -= 8) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i + 1; (j+1) % 8 != 1; j++) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 1; (j+8) % 8 != 7; j--) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i + 7; (j-7)%8 > 0 && j < 64; j += 7) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i + 9; (j-9)%8 < 7 && j < 64; j += 9) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 7; (j+7)%8 < 7 && j > -1; j -= 7) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
                for (j = i - 9; (j+9)%8 > 0 && j > -1; j -= 9) {
                    if (b[j] * c > 0) break;
                    pMoves[pMoves.length] = [i,j];
                    if (b[j] * c < 0) break;
                }
            }
            //King
            else if (pieceNum*c == 6) {
                if (b[i+8]*c <= 0) pMoves[pMoves.length] = [i,i+8];
                if (i%8 < 7 && b[i+1]*c <= 0) pMoves[pMoves.length] = [i,i+1];
                if (b[i-8]*c <= 0) pMoves[pMoves.length] = [i,i-8];
                if (i%8 > 0 && b[i-1]*c <= 0) pMoves[pMoves.length] = [i,i-1];
                if (i%8 > 0 && b[i+7]*c <= 0) pMoves[pMoves.length] = [i,i+7];
                if (i%8 < 7 && b[i+9]*c <= 0) pMoves[pMoves.length] = [i,i+9];
                if (i%8 < 7 && b[i-7]*c <= 0) pMoves[pMoves.length] = [i,i-7];
                if (i%8 > 0 && b[i-9]*c <= 0) pMoves[pMoves.length] = [i,i-9];
            }
        }
    }
    return pMoves;

}
\$\endgroup\$
  • 1
    \$\begingroup\$ To be on-topic here you have to provide a full functional code, not just a snippet. Why you didn't test it your own? And if you did, why not share your results? \$\endgroup\$ – Mario Santini Aug 28 '16 at 15:35
  • \$\begingroup\$ Not quite sure how to test it. Edit: also if this isn't the right place to post, where would that be? \$\endgroup\$ – Lasse Møldrup Aug 28 '16 at 15:36
  • 1
    \$\begingroup\$ So, please provide a working code of your for loop. \$\endgroup\$ – Mario Santini Aug 28 '16 at 15:38
  • 2
    \$\begingroup\$ We provide reviews for working, real-life implemention code, because questions asking "what is better, a or b?" almost always must be answered with "depends on the context". More often than not, there is a solution c too that is either more readable or performs better. The real-world implementation provides context. The person asking the question may define an area in which they are specifically interested, but answers on this site may review any aspect of the code. \$\endgroup\$ – Sumurai8 Aug 28 '16 at 15:57
  • 1
    \$\begingroup\$ @Sumurai8 You have the start of an answer here, you might want to start with better naming of symbols. \$\endgroup\$ – pacmaninbw Aug 28 '16 at 16:40
2
\$\begingroup\$

Naming of your variables

Don't use single-character variable names. If other people read your code, or you after 2 days, you have trouble figuring out what each variable meant. Space does not come at a premium, so use something discriptive, such as board and colour.

Array.prototype.push

You are using pMoves[pMoves.length] = ... a lot. You can (and should) write pMoves[pMoves.length] = 1; as pMoves.push(1);. To add multiple values, you can use Array.prototype.push.apply(pMoves, newMoves);.

2D arrays are not scary

You are using a one-dimensional array to describe a two-dimensional environment. The result is that you have a lot of code dealing with that conversion. Instead use a data structure that is already 2-dimensional, so the rest of the code is more clear.

Avoid for-loops

For loops are not expressive in what they are actually used for. For a lot of things an equivalent exists that is a lot more expressive. For example, the following for-loop can be replaced with the one below it.

for (i = 0; i < 64; i++) {
    pieceNum = b[i];

    //...
}
b.forEach(function(pieceNum, i, origArray) {
  //...
});

In javascript, you only need to define parameters up until the one you are using. For example, if you only need pieceNum, you can do this:

b.forEach(function(pieceNum) {
  //...
});

I wrote the part above assuming that the code would be run once per turn. .forEach with a callback is more expressive, but comes at the cost of a 25 slower execution time. It's not something to worry about if you run it once every so often, but it is a concern if you write an AI.

I don't understand why you are using for-loops for the moves for various pieces at all. For example, there are 6 possible places a pawn can move to, and in the fast majority of cases there are at most 3. Why do you have a for-loop, or even want one?

Dropping variables into the global namespace

You do not declare i and j (and possibly more). This means that the first time you use them, they are created in the global namespace. Consider using strict mode ("use strict";) to catch such errors and generate a SyntaxError instead of having this problem.

Nested if's

You have an outer if (pieceNum*c > 0) { and inner if (pieceNum*c == ...) {. Simply remove the outer if, as it does not seem to serve a purpose.

Code duplication

I notice some code duplication for the Knight piece. Code duplication causes unnecessary complexity, and makes correcting the code harder.

Usage of == (abstract equality)

In javascript it is usually safer to use strict equality ===, unless you have a very good reason to use abstract equality. Abstract equality is not transitive, which can cause odd bugs and unexpected behaviour. Reading material is available on Stackoverflow.


Edit: I didn't have time just now to finish the answer, but one of the things you should do is storing the position of each of each of the 16 pieces of each colour. From that point on you don't have to scan each 64 squares, but instead perform your magic on the known positions only.

Look into adding comments to some of the necessary loops. For example, if two loops check if a rook may move horizontally, add a comment above it.

//Horizontal movement

It would help finding relevant parts.

When using 2D arrays, you can use loops with offsets. Doing that instead of calculating raw coordinates each times would result in cleaner code. The impact on performance is up to you to test.

Last but not least, it seems that your King may do a lot more than is possible in the actual game. The King may not move into squares where it can be captured. I suspect you remove such new boards when evaluating that board, but it is something you should keep in mind.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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