Pointing at a specific long in an array without testing each

Programming Questions

asimes

Pointing at a specific long in an array without testing each

in Programming Questions • 1 year ago

I'm starting a new project for a Chess AI and am just doing the drag and drop selection for human players at the moment. The code I have below works fine, but when I start doing move generation it is going to be really important that the code is as fast as possible.

Right now more than one piece can be on a square (haven't coded a condition to prevent it yet) but later that will never happen. What I would like to be able to do is pick a square on the board (right now with the mouse) and know which long I should be doing my bitwise operations on (there is a long for white pawns, another for white rooks, another for white knights, ect). Right now I just test all of the longs in my array with a bitmask to see if they intersect the square I have selected (with the mouse). It would be ideal not to test all of the longs in an array and just point to the right element somehow, help would be greatly appreciated.

EDIT: I put in comments to help and highlighted the code I was talking about in red.

boolean somethingSelected, wTurn;
long mSelect;
long[] pieces = new long[12];
PImage[] pieceImgs = new PImage[12];
void setup() {
size(801, 801);
stroke(128);
pieceImgs[0] = loadImage("WhitePawn.png");
pieceImgs[1] = loadImage("WhiteRook.png");
pieceImgs[2] = loadImage("WhiteKnight.png");
pieceImgs[3] = loadImage("WhiteBishop.png");
pieceImgs[4] = loadImage("WhiteQueen.png");
pieceImgs[5] = loadImage("WhiteKing.png");
pieceImgs[6] = loadImage("BlackPawn.png");
pieceImgs[7] = loadImage("BlackRook.png");
pieceImgs[8] = loadImage("BlackKnight.png");
pieceImgs[9] = loadImage("BlackBishop.png");
pieceImgs[10] = loadImage("BlackQueen.png");
pieceImgs[11] = loadImage("BlackKing.png");
initialize();
}
void draw() {
display();
}
void mousePressed() {
somethingSelected = false;
mSelect = 1L<<(7-mouseX/100+(7-mouseY/100)*8);
if (wTurn) { // If it is White's turn...
for (int i = 0; i < 6; i++) { // Test elements corresponding to White pieces
if ((mSelect&pieces[i]) != 0) {
somethingSelected = true;
break;
}
}
}
else { // If it is Black's turn...
for (int i = 6; i < 12; i++) { // Test elements corresponding to Black pieces
if ((mSelect&pieces[i]) != 0) {
somethingSelected = true;
break;
}
}
}
}
void mouseReleased() {
boolean execute = true;
if (mouseX <= 0 || mouseX >= width || mouseY <= 0 || mouseY >= height) execute = false;
if (execute) {
long newLoc = 1L<<(7-mouseX/100+(7-mouseY/100)*8);
if (wTurn) { // If it is White's turn...
for (int i = 0; i < 6; i++) { // Test elements corresponding to White pieces
if ((mSelect&pieces[i]) != 0) {
pieces[i] ^= mSelect;
pieces[i] |= newLoc;
wTurn = false;
break;
}
}
}
else { // If it is Black's turn...
for (int i = 6; i < 12; i++) { // Test elements corresponding to Black pieces
if ((mSelect&pieces[i]) != 0) {
pieces[i] ^= mSelect;
pieces[i] |= newLoc;
wTurn = true;
break;
}
}
}
}
somethingSelected = false;
}
void display() {
int mouseLoc = 7-mouseX/100+(7-mouseY/100)*8;
boolean showTargetLoc = true;
if (mouseX <= 0 || mouseX >= width || mouseY <= 0 || mouseY >= height) showTargetLoc = false;
for (int i = 0; i < 64; i++) {
int x = (7-i%8)*100;
int y = (7-i/8)*100;
if (somethingSelected && 1L<<i == mSelect) fill(128, 0, 0);
else if (somethingSelected && showTargetLoc && mouseLoc == i) fill(128, 0, 0);
else if ((i%2 == 0 && i/8%2 == 0) || (i%2 == 1 && i/8%2 == 1)) fill(204);
else fill(51);
rect(x, y, 100, 100);
long bitMask = 1L<<i;
for (int j = 0; j < 12; j++) {
if ((bitMask&pieces[j]) != 0) {
image(pieceImgs[j], x, y); // Show appropriate image for corresponding piece
break;
}
}
}
}
void initialize() {
wTurn = true;
pieces[0] = 0x000000000000ff00L; // White Pawns
pieces[1] = 0x0000000000000081L; // White Rooks
pieces[2] = 0x0000000000000042L; // White Knights
pieces[3] = 0x0000000000000024L; // White Bishops
pieces[4] = 0x0000000000000010L; // White Queens
pieces[5] = 0x0000000000000008L; // White King
pieces[6] = 0x00ff000000000000L; // Black Pawns
pieces[7] = 0x8100000000000000L; // Black Rooks
pieces[8] = 0x4200000000000000L; // Black Knights
pieces[9] = 0x2400000000000000L; // Black Bishops
pieces[10] = 0x1000000000000000L; // Black Queens
pieces[11] = 0x0800000000000000L; // Black King
}

Replies(10)

PhiLho

Re: Pointing at a specific long in an array without testing each

1 year ago

Honestly, I wouldn't worry for avoiding a loop of 6 (or 12) iterations. The fact it takes 2 or 4 nanoseconds (made up numbers, but that's the spirit) isn't that important, unless you do that millions of times, of course. But in code in interaction with the user, it is invisible.
Note: I am not too sure to have understood your algorithm, surely very smart.

asimes

Re: Pointing at a specific long in an array without testing each

1 year ago

I am somewhat worried about it though, my last Chess environment was not fast enough to be enjoyable to play with when it was searching to a depth of 3. It took about 2 minutes per turn when it was searching to depth 3 because it was checking 5 million possible future moves on the first turn! That actually is a very small number for depth 3, in the middle game that number could be much larger.

Just in case someone doesn't know what I mean by depth 3, depth 3 means:

- Consider every possible legal move (moves that don't break the rules of chess)

- Consider every legal response an opponent could make to that

- Consider every legal response to those responses

- Consider every legal response to that

This slight optimization is going to become important later because it will be run multiple millions of times per turn when I set up move generation along with future planning.

Chrisir

Re: Pointing at a specific long in an array without testing each

1 year ago

Well, in general have a class Fieldongameboard with pos Color and a Pointer to the figure (or empty field) in array 0..65 or so

Also have a class figure to store the Image, the value whether it's been moved already

in array 0..32 or so

Thus each clicked field soknows its figure

so nö need for line 92

Chrisir

Re: Pointing at a specific long in an array without testing each

1 year ago

http://www.openprocessing.org/sketch/31784

PhiLho

Re: Pointing at a specific long in an array without testing each

1 year ago

I think I have understood your method. The 64 bits of the long represent the chessboard, and the bits indicate where a piece of a given type is.
And you need to use your method outside pure display / interaction cases.
Perhaps you can use a BitSet but I don't know if it will be faster than your method, they might use loops behind the scene, too...

As long as you use an array, you will have to explore it each time.
Actually, I am not sure that you will gain speed with bits. Bit shifting / masking is relatively fast, but array access is probably faster: an array of 64 entries can be efficient too. Only benchmarking can tell for sure, and only in lot of loops (don't forget the Jit compiler!).

asimes

Re: Pointing at a specific long in an array without testing each

1 year ago

Chrisir, I don't think I understand what you wrote, could you explain it further please?

PhiLho, glad you got the algorithm :) Could you show me an example that uses BitSet please? It is not straightforward to me.

My last environment stored the board with an integer array where each element could be:

Black King = -6

Black Queen = -5

... (and so on)

No piece = 0

... (and so on)

White Queen = 5

White King = 6

This did mean that I didn't have to search for pieces. Unfortunately this was slow because this set up is not ideal for move generation. The advantage of using an array of longs is that I should be able to generate the moves of all the pieces at once (generate moves for all pawns at once, all rooks at once, ect).

asimes

Re: Pointing at a specific long in an array without testing each

1 year ago

I left this out of the original post because I thought it was too long already, but this is really helpful for visualizing what is happening with the long array:

void longBinary(long in) {
String bin = "";
for (int i = 63; i >= 0; i--) {
if ((1L<<i&in) != 0) bin += "1";
else bin += "0";
if (i%8 == 0) bin += ".";
}
println(bin);
}

Chrisir

Re: Pointing at a specific long in an array without testing each

1 year ago

@asimes: I think you are far ahead of me already.
My suggestion was what you did in your last environment:

store the board with an integer array where each element could be one chess piece of different kind.

Maybe you can mix both approaches and work with the board with an integer array (as in your last environment) and when it comes to move generation transfer the board in the long array, do the move generation and get it out again?

asimes

Re: Pointing at a specific long in an array without testing each

1 year ago

Chrisir, that's a good idea. I had already made new longs to represent "all White pieces" and "all Black pieces". It was enough to make this:

void mousePressed() {
somethingSelected = false;
mSelect = 1L<<(7-mouseX/100+(7-mouseY/100)*8);
if (wTurn) { // If it is White's turn...
for (int i = 0; i < 6; i++) { // Test elements corresponding to White pieces
if ((mSelect&pieces[i]) != 0) {
somethingSelected = true;
break;
}
}
}
else { // If it is Black's turn...
for (int i = 6; i < 12; i++) { // Test elements corresponding to Black pieces
if ((mSelect&pieces[i]) != 0) {
somethingSelected = true;
break;
}
}
}
}

into this:

void mousePressed() {
somethingSelected = false;
mLoc = 1L<<(7-mouseX/100+(7-mouseY/100)*8);
if (wTurn && (mLoc&allWhite) != 0) somethingSelected = true;
else if (!wTurn && (mLoc&allBlack) != 0) somethingSelected = true;
}

But it can't solve problems where I have to test for specific piece types. The only think I can think of that would be a problem with the mixing approach is that I would be updating pieces[], my new "All White / Black" longs, and the integer arrays but I think it would be faster than testing. Thanks for the suggestion

asimes

Re: Pointing at a specific long in an array without testing each

1 year ago

Wow, that mixing approach is actually extremely difficult to pull off. I think it requires no less than 2 integer board representations to work with the bitboard representations. It takes one that represents the board like:

Black King = -6

Black Queen = -5

... (and so on)

No piece = 0

... (and so on)

White Queen = 5

White King = 6

To do the ">= 0" test to see if a piece is White or the "<= 0" test for Black and another one that is like:

White Pawn = 0

White Knight = 1

... (and so on)

White King = 5

Black Pawn = 6

Black Knight = 7

... (and so on)

Black King = 11

But even with both I still have to further test the second integer array to avoid pointing with empty squares when assigning... I will keep experimenting but I might just end up going with a strictly bitboard representation just for simplicity at this point.