I've completed the backend logic for both Checkers and Reversi (Othello) in Java. I've only played a few test games so there could be bugs, but everything seems to work as intended so far. As one would expect, these games aren't very complicated so maybe there are no bugs, which would be nice for once.

I started with Checkers because I thought it would be the easiest project, but Reversi turned out to be much easier. The reason for this is the movement of pieces. Checkers pieces can move in two directions and they can jump in two directions. Implementing double/triple jump logic was also kind of a pain. King pieces can move in any direction while regular pieces can only move towards your opponent. In Reversi, pieces don't move at all. You simply play a piece and it says in that spot forever, making the programming for it much easier.

Another thing that made Reversi easier to program was that I did it second. I was extremely rusty from not programming for so long. The Checkers project got me back into the swing of things. Also, I made several organizational errors in the first project that I won't repeat in subsequent projects. I learned what the most important aspects of building a board game are.

The number one thing to keep track of when programming a board game, I learned, was cataloging every possible move for every turn. I learned this the hard way. Half way through developing Checkers I wondered, "Hm, how am I going to program the win condition." Turns out, when you dumb it down, the win condition for Checkers is simply the first player who can't move loses the game. In Reversi, the game ends when both players have no more moves. In Chess, the game is also over when a player can't move. Therefore, keeping track of what moves are possible is the #1 priority.

Reversi

Because I haven't programmed a front end for the games yet, this is what it looks like on the command line.

Recursion

Recursion is a technique of programming a function that calls itself, without going into an infinite loop. Normally, you'll program a bunch of stop conditions so the stack rewinds to accomplish a given task. It can be pretty hard to wrap your brain around. If you've ever played Magic The Gathering there is an order of operations called the stack. Actions go on the stack and they resolve in the opposite order that they were put down. Whatever is on the top of the stack gets resolved first and so on until the stack is empty. Recursion works exactly the same way.

I forced myself to write this sandwich() method recursively because it's been so long since I've used recursion. I thought I could use a refresher. I almost gave up on it because it was taking me so long to remember how to do it. However, I think it was worth the effort. I was surprised when I realized that these two methods are pretty much the bulk of the entire game. This is the logic used to figure out which pieces need to be flipped if the given piece (disc1) is actually played. If no pieces get flipped this move is illegal and not added to my list of legal moves.

Rules

I suppose assuming that everyone knows the rules of this game is foolish. In short, if you sandwich your opponents pieces in between your pieces they get flipped to your color. Whoever has the most of their color showing at the end of the game wins. Corners are very important because they are impossible to flip. As you connect sides to the corners they also become impossible to flip. The game is often about forcing your opponent to give you a corner.

I'm actually an expert at this game. I used to play it all the time on Windows XP. Whenever I would go against a Japanese player I would get CRUSHED. I finally got crushed so many times that I figured out the unintuitive strategy behind winning the game. It basically involves allowing yourself to be surrounded at the start of the game. You flip as few pieces as you can and you want the pieces that you do flip to not be exposed. It is in this way that you limit where your opponent can move while also giving yourself as many options as possible.

Here's how it works.

The sandwichAllSides() method simply calls the sandwich method eight times: one for each of the eight directions that pieces could get flipped. There's nothing very special about it and it has nothing to do with the recursion.

sandwich()

This method returns "false" for three different reasons:

1. If it goes off the edge of the board
2. If the piece it's checking is empty (null)
3. If the piece it's checking is the same color and also adjacent (right next to it)

This method only returns true on one condition:

1. If the piece found is the same color and also NOT adjacent.

Because the same (not adjacent) color was found we can safely assume that all the pieces in between this piece and the main piece are the opposite color and need to be flipped. The recursion happens when we find a piece of the opposite color.

Example

Say it's black's turn and he wants to move at the marked square. On my game this location would be board[6][4] (board[x][y] where the range of x and y are 0-7 in a two dimensional array using Cartesian coordinates).

So you call the method sandwichAllSides() with this location in mind. It checks all eight directions. Seven of those directions return "false" because they are blank and have no pieces on them. The last direction returns true after several mental gymnastics. That direction is sandwich() where deltaX = -1 (because it's going backwards) and deltaY = 0 (because it's not going up or down)

First call of sandwich() (deltaX = -1)

The recursive function finds a white piece, which is exactly what it was looking for. The problem is we don't know if this white piece is actually sandwiched by a black piece. It could still run off the board or hit a blank space, in which case it should still return false;

This is where recursion comes in. You leave this current function open on credit (so to speak) and make a recursive call that will eventually return the correct answer. This is the first item on the stack. Now instead of calling the sandwich function with deltaX = -1; we call it with deltaX = -2;

if( sandwich(disc1, deltaX, deltaY, flip) ){

Recursion has begun. This method gets put on hold to be resolved later when we find the answer. Is sandwich() deltaX = -2 true or false?

Second call of sandwich() (deltaX = -2)

We found another white disc. Which means yet again we don't know the answer. Let's check the next one.

Third call of sandwich() (deltaX = -3)

Another white disc. Try again.

Forth call to sandwich() (deltaX = -4)

OMG a black disk. We can finally return true, but what happens then?

REWIND!

We've called the sandwich() method four times. There are four copies of this method on the stack waiting to be resolved. This fourth call resolves first and returns true immediately.

if( sandwich(disc1, deltaX, deltaY, flip) ){ // sandwiched piece found if(flip) disc2.flip(); return true; } The forth returns true to the 3rd method call. It flips the disk and returns true to the second method call, which flips the disk and returns true to the first method call, which flips the disk and returns true, signalling to the original call that at least one disk was flipped and this is a legal move.

Conclusion

Recursion is a complicated process that you really have to wrap your brain around to get a good understanding of it. However, once you add this tool to your programming toolbox it can make very difficult problems to solve seem trivial. I don't expect I've helped anyone by writing this. You're either not a programmer, or you are and you already know what recursion is. This is mostly just for me to cement my understanding of this useful technique.

So, why am I even bothering with programming these old school classic games in the first place? Well, first of all, if you want to program games (I do) there is no excuse to not take some times to create the most basic ones. Also, if I end up putting these games on the blockchain you'll be able to bet on the outcome, which could be fun. Obviously, you'd have to fully trust your partner and bet very small amounts because cheating is extremely easy. All of these games have been solved by AI. AI can destroy the best grand-masters so you have to be sure your opponent won't use AI to cheat.

I'm actually really surprised the basic games have not been put on the blockchain. No one in the world seems to have done it yet. I find this very odd. Whenever I look for reversi apps on Android or the web I have a very hard time finding ones that are two player; they are all against the computer (boring!). Blockchain tech provides me a way to bring these two-player games to the entire world without even having to pay for a server; while also being connected to ultra secure accounts and ultra secure cryptocurrencies.

Another big reason why I'd like to put these games on Steem is to show the Steem developers how flawed the current system is. Right now, you can only comment on the blockchain every 20 seconds, meaning that if I put these games directly on the chain you'd only be able to move at the fastest once every 20 seconds. This is unacceptable, which is why I wrote this post about upgrading the account @null to allow for text information to be posted to the blockchain on every block. This would allow bot's to post to the chain every three seconds while not allowing them to clutter the rest of the site.

I have to decide whether to do Chess or Go next. It probably doesn't matter much considering the speed at which I was able to complete the other two. However, a lot of people don't even know about Go because it's more of an Eastern game. It's pretty amazing though and is much more complicated than chess, even though the rules are simpler and there is only one type of piece.

Once I've completed the four games I'll create a frontend module to start connecting them to different blockchains. I'll either start with Tron or Steem. Tron claims to use Java as a main language, but Steem already has a built in community. With Steem, I'll likely use this project as a reason to learn JavaScript and Node.JS and transfer the logic over to those platforms. Eventually, I'll probably even make a simple Android app to play all four games. If you know of any other board games you'd like to see on the blockchain let me know. Settlers of Catan is definitely on the table.

Return from Programming Update (Checkers, Reversi, and Recursion) to edicted's Web3 Blog