How to Turn Left with Math
I made some math today, and I really need to talk about it!
The background is a chess program I’m working on. I want to create chess as a programming exercise, only I want it to be a generalized chess. I want to make a chess that can grow into more than chess. Or less. A game that can be chess, checkers, tic tac toe, or something else, all on the same simple engine. For this reason, and for what I hope will make for more elegant code, I make decisions like representing the board with a one dimensional array of spaces.
You might recognize the image above as something resembling a chess board. You might also notice that it is two dimensions. Often, chess boards are described with row and column labels, and it wouldn’t be hard to represent them the same way in a computer program. But I’m stubborn, and computers tend to think in one dimension, so I made my chess board in one dimension too.
Nice for storing on a computer, but awfully abstract for a friendly game of chess. I need a bridge between human players and the computer managing the game. I’ve done this simply with a bit of integer division and modular arithmetic: if I know the width of a chess board is 8, then I can figure out that space 28 is in row 28 / 8 = 3 and column 28 % 8 = 4. (Remember, computers like to count starting with zero.)
This simple arithmetic helps considerably, especially when figuring out where a piece can move. A lot has been written on how chess piece movements can be described mathematically using numbered rows and columns. The computer can have a nice, neat array of numbers 0–63 and I can easily transform those numbers into x and y axes at the drop of a remainder.
Yesterday, I stumbled upon a different problem. I mentioned above that I wanted this game to be extensible beyond traditional chess. One example of this could be four person chess on a larger board. Conceptually, pretty straight forward. You make an array, and define a larger x dimension. If x and y were both 16, you’d have 256 spaces and plenty of room for multiple players. I’ve been allowing for this abstraction from the beginning. Teams are defined simply by two integers. The first is both a label and their place in the rotation. Team 0 goes before team 1, which is before team 2 and so on. The second is what direction is forward.
This second integer is another example of my unreasonable obsession with how the computer sees things. I could have defined a north, south, east and west, and stored them as strings or simply character abbreviations, but then I’d have to create a bunch of if-then cases to convert those directions into something meaningful for the computer, and every time I tried to add some functionality to the game, I would have to consider carefully how to incorporate my clunky, translated system of direction. Instead, I stuck to math. If I want to move up, or north, one space on the board, how would I write a general formula to do that? Well, if I’m starting on space S, then I just need to add the width of the board, the x dimension. So S + x = one space north. Likewise, to get south, east and west, I just need S - x, S + 1 and S - 1, respectively. You can see on the board above that this is true for any space, provided you guard against wrap around or falling off the board. These cardinal directions can serve as integer representations of what way is forward for a given team. If a team is moving from south to north, their direction is 8. If they are moving from east to west, it’s -1.
So far so good for the cardinal directions, but what of the relative directions? What if I don’t want up or down, but rather left and right, forward and back? Forward and back are easy. Forward we have saved with the team information, and backwards is just the additive inverse. Left and right got tricky, though. How do I say that when the forward direction is the magnitude of the width, the magnitude of left and right needs to be one, and vice versa? It would be simple with some if statements, but I said I was going to be stubborn, damn it! How could I get 1 to return 8 and 8 to return 1? I could divide the input by 8, so 8 / 8 = 1, and by flipping 1 / 8, I could get 8 / 1, which is 8. Great! Generally…
Do you see the problem? I didn’t until I checked the output of the formula. Let’s use our old friend space 28. If you’re on 28 and going north, the space in front of you is 36, behind you is 20, and, using this formula, we get 1, which we subtract from 28 for left and add to 28 for right. But, if you’re on 28 and forward is east, that formula will give me eight, but I need to add it for left and subtract it for right. Again, a simple if statement would be the easy fix, but I refuse to even acknowledge an easy way. Math or bust. I needed another formula that would flip signs when the piece’s forward direction was horizontal, and not when vertical.
This is where we really get into what gets me excited about math. After a chat with my dad on the phone, who is much better at math than I am, but also had no way of really knowing what I was talking about over the phone, I recalled certain oscillating series that jump back and forth between negative and positive. They do this because any negative number with an odd exponent will have a negative result, and with an even exponent will have a positive result. I could use this. If I could just make an input of one always return a negative, and the width of the board always return a positive. Easy, one is odd and eight is even! Except… Generalization is a demanding mistress. What if I wanted to create a modified chess game with a board width of nine? What a terrible error that would be to find later on. Only when you have a board with an odd width will you observe piece occasionally moving in unexpected ways. I guarantee I won’t remember any of this in a month from now, and I don’t want to have to go troubleshooting it a year down the road. The width, whether even or odd, had to resolve to an even number. So I came up with…
Now, I get the feeling there are a lot more elegant solutions, but I was tired at this point and it achieved my goal. With an input of 1, the numerator will be zero, and the fraction will then resolve to zero. If the input is the width, the numerator will equal the denominator and the fraction will resolve to one. Just tack a plus one on and you have an odd number for an input of one and an even for an input of the width. Of course, it outputs a bunch of nonsense for virtually any other input, but if that happens I made a mistake somewhere else in the program. Either way, the whole factor ends up looking like this:
Back to me getting excited about math! Remember how I said I could have easily done this with an if statement? Well that’s exactly what I ended up doing. The above is simply math for “if a = 1 or -1, then return -1. if a = x or -x, then return 1.” (With a quiet “if a = anything besides 1 or x you’re going to get back some nonsense that will break your brain or your program.”) The same idea was at work in the earlier, simpler 1/(a/x). It transformed the inputs I had into the outputs I needed, as any formula should, as any method in a program should. I just did it all before touching the c++ code.
A caveat here. At this point I can’t really claim that I’m writing in the computer’s native tongue by coding with math. In order to have the computer do this, I have to use exponent functions, absolute value functions, floating point operations, rounding, and more. A simple if statement would likely yield far better performance. Nevertheless, having chosen a paradigm where the board is represented as a single array of sequential numbers, maintaining an adherence to representing and solving problems with math keeps things consistent and avoids problems that could arise from constantly translating between modes. At least that’s what I tell myself.
So putting it all together, we get one equation that always tells you how to turn left, no matter what direction you’re facing. Switch the sign in the first half and you can turn right. Outstanding! Was it worth it? Well, it gave me something to talk about for far longer than anyone will be willing to read, so yes. Yes it was.
Errata: in the heat of the mathematical moment, I totally forgot that 1/(a/x) = x/a, so while it was technically not correct, it was an inelegant extra step.
