How to use bitboards in gdscript

Godot Version

4.2.1

Question

I was checking this video from Sebastian Lague and he was implementing bitboards for his chess game.

It looks he uses a ulong type of data, but gdscript only has int. But int can’t store a value like this (the initial white pawn positions):

0000000000000000000000000000000000000000000000001111111100000000

I can use a String to store this, but then I can’t use bitwise operators like << and >>. How can I use bitboards in gdscript?

this might need yourself making a method to convert the binaries string to value in decimal, then compare or shift it like usual with >> or <<, then convert it back to binaries string for storing
also this looks like an array of 0 and 1, if you store it like an array, then you will need to figure out the method for bit shifting in an array

int in GDScript is a 64 bit integer and you can write binary literals like 0b000000000000000000000000000000000000000000000001111111100000000 and you can even use _ separators to see groups of 8 easily. But GDScript doesn’t have an unsigned version of int so you’ll only have the lower 63 bits to work with using the bitshift operators. it wont allow you to bitshift negative values (with the most significant bit set). and you can’t write the 64th bit in the literal so you’d have to 2s compliment it yourself.

It’s just a coincidence that a chess board has 64 places though, if the board was bigger you’d need a bigger bit board anyway, you can also use more than one value to store the bitboard it takes some extra work though.

2 Likes

I tried to write a binary like that:

white_pawn_bitboard = 0000000000000000000000000000000000000000000000001111111100000000

But the output is this:

1111111100000000

As an int, it is ignoring the zeroes in the left.

EDIT: ok, I can use the suffix 0b for literal binary representation, and the print will show the decimal value. How can I then use the bitwise operators to shift the positions?

1 Like

Just for fun these functions recreate shifting but work for all 64 bits

const MAXINT = 9223372036854775807
const MININT = -9223372036854775808

# only pass in 0 or 1 for msb, no negative numbers for bitfield
func make_bitfield(msb: int, bitfield: int) -> int:
	return bitfield | (msb * MININT)

func shift_right(bitfield: int, amount: int) -> int:
	if amount == 0:
		return bitfield
	if amount < 1 or amount > 63: # sanity check
		print("stop")
		return 0
	
	if amount == 0:
		return bitfield
	if bitfield >= 0:
		return bitfield >> amount
	
	return ((bitfield & MAXINT) >> amount) | (1 << (63 - amount))

func shift_left(bitfield: int, amount: int) -> int:
	if amount == 0:
		return bitfield
	if amount < 1 or amount > 63: # sanity check
		print("stop")
		return 0
	
	return (bitfield & MAXINT) << amount

you can make a bitfield with the top bit set like

var bitfield: = make_bitfield(1, 0b1111111_00000000_11111111_00000000_11111111_00000000_11111111_00000000)print(bitfield)
print("%x" % (0b1111111_00000000_11111111_00000000_11111111_00000000_11111111_00000000 >> 8))
print("%x" % shift_right(bitfield, 8))
2 Likes

Thank you for the code example. To understand: I would need to pass a long binary number to that method, which returns a hexadecimal value. I think I should use the binary stored as a hexadecimal because I can’t pass the long binary value hard-coded. Is that right?

And how do I know which bit am I shifting? Let’s say I want to move a pawn from b2 to c2. What’s the operation here?

1 Like

The value is not stored any differently, the only difference is in how the value is displayed. Using "%x" % value I formatted the value as a hexadecimal string for printing to the log.

writing a value in binary notation in your code also makes no difference, it’s still just an int value. The purpose is to be able to read the individual bits in the source code easily, but for example 0b110 and 6 produce the exact same value.

The reason I needed a function to create a bitfield for all 64 bits manually, is because the top bit in a signed int (one that can store negative values) is treated differently, and Gdscript doesn’t already provide a way to treat an int as a unsigned value, where the top bit isn’t special.

The function I wrote takes an int value of 1 or 0 for the highest bit, and a positive int value for the rest. (negative values have the top bit set) And it creates an int value that combines the top bit and the other 63 bits from the second argument. This is not useful for using the number as a signed value, it is specifically to create a number with certain bits set, since you can write all 64 bits out using binary notation. like (1 bit, the other 63).

The shift operation works on all the bits at once. if you want a single bit moved you must shift a value that only has that single bit set.

You could then combine it with other bits using the “bitwise or” operator |. Look up how bitwise operations work if you need more help understanding.

2 Likes

I totally failed to understand how to deal with single bits, and how to do this operation. Since there is no gdscript reference to bitboards, it’s kinda complicated to understand any material in other languages.

I’m not sure I’m getting how the OR operation works in this context. It’s frustrating…

1 Like
1 Like

Thank you, it doesn’t help, unfortunately. I just don’t how to use the information how to perform these operations, maybe it’s too complicated for me right now.

1 Like

In the Coding Adventure video he explains exactly how to do this


He’s using the bitwise XOR

bitwise operators do logical operations on every bit of a value individually instead of as a whole
These are logic operations:

if you have 2 values 0110 and 1010 a bitwise operation would work like this

number 1:  0 1 1 0

           | | | |
           v v v v

number 2:  1 0 1 0

           | | | |
           v v v v

result  :  D C B A

Where A only depends on the result of the logic operation on the first bit of both numbers, B only depends on the second bit from both numbers, etc.

2 Likes

So for a logical AND which is the & operator

number 1:  0 1 1 0

&          v v v v

number 2:  1 0 1 0

=          v v v v

result  :  0 0 1 0

and here’s the same numbers with the bitwise OR | operation

number 1:  0 1 1 0

|          v v v v

number 2:  1 0 1 0

=          v v v v

result  :  1 1 1 0

If there’s only 1 bit set in one of the numbers, number 2 1000
then the result of the logical or will be the same as number 1, except the bit from number 2 will also be set, if it wasn’t already:

number 1:  0 0 1 1

|          v v v v

number 2:  1 0 0 0

=          v v v v

result  :  1 0 1 1

So that’s how you use OR to combine multiple bitfields

XOR ^ on the other hand toggles a bit from the other number

number 1:  1 1 1 1     0 0 0 0
|          v v v v     v v v v

number 2:  1 0 0 0     0 1 0 0
=          v v v v     v v v v

result  :  0 1 1 1     0 1 0 0

So in the chess Coding Adventure he’s combining a single bit at the position where the piece came from with a single bit at the position the piece is going to, into a single bitfield

Then he’s using XOR ^ to toggle both positions. so the empty position (destination) becomes full, and the full position (starting point) becomes empty.
That’s what the code he’s showing does

2 Likes
var starting: = shift_left(1, start_square)
var ending: = shift_left(1, end_square)
var both: = starting | ending

bitboard ^= both
# x ^= y : is the same as : x = x ^ y 
#bitboard = bitboard ^ both
# now all on one line
bitboard ^= shift_left(1, start_square) | shift_left(1, end_square)
2 Likes

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.