#nd chess

Guess who's working on chess again? Partially due to revived interest, i'm gonna take a crack at getting this thing up to a reasonable speed. Starting with one of the neatest trick from 2D chess

Magic bit boards babyyyyyyyyy. Basically in 2D chess we take advantage of the fact that a 64 bit integer holds just enough individual bits to correspond one-to-one (and onto) occupancy of a chess board. You should read about them if you want i'm not explaining magic bitboards here lol It does require multiple bit boards to use, usually requiring one for rooks, for bishops, white, probably ghost pawns, stuff like that. The beauty of this though is we can represent essentially an entire board state with just a couple unsigned long ints. So here's where our journey start.... how uh... so fir... you may have noticed... uh....

yeah there's more than 64 squares there. This is where our trouble first starts. We need ways of dealing with larger boards. Now ya' girl went ahead and cracked this pretty quickly. Too bad its the wrong fucking thing.

Basically its as simple as reserving the outer lines of bits for data used to outright skip over that entire section, though it does come at the cost of only being able to represent 6x6 boards. So just apply that to.... I... actually only have like 2 boards that need this. This doesnt help at all, maybe i'll revisit it for the donuts.

(second ones a tiger btw, a 4D analog to a torus) Now lets revisit these magic bitboards again rq

Now astute readers may have noticed something horrifying about this. Notice how the left most grids are defined not only by the piece, but also the pieces positions. More generally, we can say that its defined by its n-agonals (monagonals, diagonals, triagonals, quadragonals, pentagonals)

It'd be good to know how many of these there are in total so we can get a rough idea of the number of magic bitboards we need. Luckily this is an easily solved problem. The number of monagonals in 5D space are 5 Choose 1. diagonals 5 choose 2. The total number of nagonals in 5D would then be the sum of these. We technically want to skip 5 choose 0 but for estimating memory usage the number being 32 instead of 31 wont make a difference, we kinda care about order of magnitude

Now you could add that up... ooooooooor you could use pascal's triangle. Well, there are some number theory theorems i dont remember but pascal's triangle is cute.

Now if you punch in all of the choose expressions above, you'll find they correspond to the bottom row of the pascals triangle here. And there's a neat trick about the sum of that row we can utilize.

The sums of the nth row of binomial coefficients is simply 2^n. So if we wanted to be exact we'd remove the 0-agonal, (5 choose 0) but for now, we'll settle into *about* 32 n-agonals. So for each square thats 32 n-agonals. on the 5x5x5x5x5 board we have 1024 squares. So thats like, 32k magic numbers right? Noooooot quite because that would assume we have access to 1024 bit integers. We do not have that kind of access. Each bit board can only represent a very small section of the board at once. For the 5D board we're lucky that it fits perfectly into a 3D slice. So a pretty solid approach would be to simply break it down into 4x4x4 3D slices

Upon inspection we see there are 16 3D slices which makes sense. Now there are a few ways to actually make those slices as well. This is a very similar problem to generating bishop moves. See, when we say a "3D slice" what we really mean is we're going to choose 3 dimensions to variables, and hold the other two fixed. 5 choose 3 is 10 so we get 10 different orientations of slices, meaning 160 3D slices in total with some transposition math.

A naive calculation would be to simply multiply this all together. 32 n-agonals * 1024 squares * 10 slice orientations * 16 slices * 8 btytes per 64 bit integer gives uuuuuuus....

Holy fuck, 40 MB of magic numbers, just for this board. *However* there was a naive thrown in there. This isn't entirely accurate, and i dont know in which direction. I think its better as far as memory goes, but time complexity is looking a bit worse. Basically the thing is, we're already taking 3D slices right? So hypothetically for any given board we only need the magic numbers for whatever subset of a board we can take. We can take an 8x8 section of a 2D slice, or a 4x4x4 section of a 3D slice. If you had a 64 squares long board you could take a single strip of that but like who would be crazy enough to do such a weird board like that, a 16x64 2D board? imagine. But anyway, the idea will be to take these bit boards that are solved for smaller slices, and use them to bulk process larger boards with fewer magic bit boards. This also somewhat solve the problem regarding user generated boards when that eventually does happen, but it does give us a new, at least... slightly easier one. Given some arbitrary board, how do you best subdivide it into bit boards and what can we do to speed things up. Oh yeah, and the fact Dragons wont move in 3D slices... But that's actually not as bad as it seems. Basically instead of taking a flat slice

We can sheer the slice across another direction. After that within the sheered slice the dragon would move like a unicorn. A devil (personal name for pentagonal rider) would move like a unicorn if we sheered across a second dimension as well. The combinatorics for this are actually much more forgiving in 5D than it would seem. Basically we need some extra bitboards for quadragonals and pentagonals, but we didnt have that many to begin with. There are 5 quadragonals, and with only one direction left to sheer we have to sheer that direction. Then we throw in an extra bitboard for the pentagonal sheer as well.