Timothy's Blog

Back in the summer 2019, May specifically, I went on a boat trip with my Mom and Dad. I had a lot of time on my hands, and as boat trips can be kind of monotonous sometimes, I decided to tackle a project I had been hoping to do for a while: writing a chess program.

My initial effort consisted of finding an article on how to write a chess program in Javascript, and trying to duplicate what he had done in Javascript. I eventually got his program to work, but was unsatisfied with just copying someone else. Nevertheless I got good experience which I invested in my next iteration of the project which was a chess program written from scratch, completely in C++.

Why C++? Isn’t writing in C++ a lot harder to do because of its strongly-typed nature and unforgiving compile-time errors? True, but I already had some experience in C++ and felt I could give it a go. I spent 85 hours from the 20^th of May, 2019, to the 3^rd of July, 2019, and was able to get it in a mostly finished state. However, at this point I ran into a bug I could not figure out which was with how the values were propagated through the tree (a common feature of the MiniMax algorithm), and so put the project aside until I had more experience to be able to finish it.

To talk about the details of how the program works, it is mostly based on a tutorial I found on move generation for a chess game written in C (C is the predecessor to C++ and is very similar) using a from scratch implementation of the Minimax algorithm. Most of my code consists of move generation and the Minimax function. I’m glad I found the tutorial on move generation for a chess game as it was a real life saver (I had no idea how to begin), but the real fun was in implementing the Minimax algorithm.

The MiniMax Algorithm

So how does the Minimax algorithm work? Well, most chess programs use a a version of the Minimax algorithm, with move generation, combined with special tricks to make their program a better than just basic chess program. The Minimax algorithm is basically an algorithm which generates a tree of all the possible moves the opposing player can make, up to a certain point, from a given starting point. All chess games only go to a certain number of levels and mine is no exception (though you can change it when you start the program). This is because you can’t generate too large of a list of possible moves or you’ll run out of time and memory.

By the way, an algorithm is a computational method or formula, but more specifically can be defined as the list of steps needed to arrive a certain result given a certain set of inputs. Algorithms also are used to solve a single class of problems. A algorithm is needed for just about any computation task, big or small.

The tree made by the Minimax algorithm takes time to construct and the deeper you make the tree (and hence harder to beat) the longer it takes to make the computation. My program is single-threaded and takes about 60 seconds to compute a 5-level tree (which is a decent number of levels), but I usually set it to 4 levels to give it a faster turnaround time for testing the program (closer to < 10 seconds). 5 levels means the program can see 5 moves ahead when making decisions on what its next move will be. This isn’t much, but it’s enough to beat most amateur players.

Lets Get A Little Technical

So what does this tree consist of? Well say you have 20 possible moves for a given game layout (the exact number of moves possible from the starting layout in the game of chess is actually 20). The program has to generate all the legal moves for that layout and then decide the best move to make out of those moves. This is where the Minimax algorithm comes in. In the Minimax algorithm, each move is given a certain score, which is based on the values propagated up from the lower level of the tree (assuming the first move is at the top). This score actually comes from the lowest level of the tree where each move (also called a node) is given a static evaluation based on a set of criteria.

The biggest factor in this criteria is the sum of the value of the pieces on the board, but there can be many other factors as well depending on the game (Deep Blue used special end-game tricks, and used a massively parallel supercomputer to do its computations among other things). Basically, each piece on the board gets a value that is assigned to it and never changes throughout the game. Only when that piece is removed from the board does the sum of the value of the pieces on the board change. The Minimax algorithm (or at least the most simple implementation of it) is based on the static evaluation of layout of the pieces on the board at the bottom of the tree (Five moves ahead in this case). This gives you the score for that possibility.

Basically, the Minimax algorithm tries to see as many moves ahead in an effort to defeat human intuition and our superior pattern matching skills (given the neural-network-like nature of our brains). It uses brute force, evaluating anywhere from thousands to millions of possibilities each turn. My version set at level five only uses hundreds of thousands of evaluations, but that’s a lot compared to what the human brain can do which is only a few moves at a time and just a few moves ahead (for your average Joe).

Minimizer and Maximizer

The Minimax algorithm uses a recursive implementation of a single function (in my case named miniMax()) to successively go deeper and deeper down the tree until it has gone as many levels as it needs to. Each time the function is called, it generates a list of moves and then calls itself on each of those 20+ moves (or nodes).

When it reaches the bottom of the tree (or goes down as far as I want it to), it calls another function which does a static evaluation on each of the nodes in the list of nodes (in my case this function is called staticEval()). This static evaluation returns a score for that move and passes it up to the Minimax function. The Minimax function takes the value of each of these static evaluations and either takes the maximum or minimum value, depending on whether the level it’s on is for black or white. Black is called the Minimizer, and White is called the Maximizer.

The reason black and white take the minimum and maximum is because the values of the pieces on the board (remember?) are assigned static values at the start of the game which range from some predetermined negative number (for black in my case) or some predetermined positive number (for white in my case). So say a queen for example is given the value 900 or -900, depending on which color it is. Other piece values range from 100 or -100 for a pawn, to 20000 or -20000 for the king (just an arbitrarily high value).

It’s All About The Score

So the reason the Minimax function takes the maximum or minimum value is because the minimizer (black) is always trying to get the lowest score (more of its pieces on the board), and the maximizer is trying to get a maximum score (the most of its pieces on the board). Remember, the cumulative score for any board position reflects who is in control of the board. In my case it directly relates to how many pieces are on the board, but that’s just because my program is a work in progress and I haven’t added any other factors to my evaluation yet. So the maximum score possible is actually the score for the safest move to take for the maximizer and the minimum score is the score for the safest move for the minimizer.

This score is passed up the tree until it reaches the top level which is where the list of the 20+ possible moves based on the original board position is. The Minimax function at this point simply takes the maximum or minimum depending on whose turn it is and chooses the best move based on the score.But In actuality it may need to make a random selection if many of the moves are equal.

Back to the Story

So about my program. It’s still a work in progress, but I recently got back to working on it this month and was able to make progress on fixing the bug, which I’ve isolated to being something about the way the score is returned by each successive iteration of the Minimax algorithm. You see, I don’t know how to return values for checkmate up the tree or what to do in the event of checkmate. Do you return the maximum or minimum value for your given data type? or do you just do a static evaluation on that node and not go any further down that branch of the tree?

So I’m working on figuring it out, but if you want to give me some advice or point me in the right direction I’d appreciate it! So I think I can figure it out soon, but I realize I need a better understanding of the Minimax algorithm or at least of how the results are passed up the tree in the event of checkmate.

That being said here are some screenshots from the program in its current state to give you an example of how well it does. I got move generation down and Minimax is mostly done, but we do have some odd behavior as you will see.

So this first picture is a game in progress. You can see I used a text-based interface as I wanted to get this up and running relatively quickly. I hadn’t yet implemented color coding for the pieces, so it’s a little confusing, but “black” at the top appears to be unwilling to moves it’s high-value pieces out into the danger zone. I think this might have to do with the number of levels I had the game set at (four as usual), because if it can’t see that far ahead, it might just play “safe”, and try to preserve the best score. But I think I need to add a little bit of bias mapping (based on how close a square is to the center of the board) to the static evaluation at the end of the game to make it work properly. Anyway, something is wrong with the way I’ve implemented it.

You can see in this next iteration of the game I had introduced color coding (very slight difference, but there nonetheless) which makes it a lot easier to see whose pieces are whose. You can see my white pawn is sitting there right in front of the black queen, and you will be surprised to hear the pawn was able to take the bishop to the left out as black just ignored him. Also, none of the pieces along the way from one side of the board to the other acted either, so I’m thinking there’s some reason the computer is not taking pieces it can, when it should.

So the king in this next game, in this later version of the program, was actually avoiding being captured as I had made a change to how the values were propagating up the tree. In this screenshot he had just avoided the white pawn right below him. What I changed was to return the max value for an int data type if the minimizer was checkmated, or the min value if the maximizer was. Makes sense, as the max/min value represents the worst score for the one being checkmated, but something’s wrong. The funny thing is, he would only avoid the danger if the danger was on the very next turn, which doesn’t work of course for a proper computer opponent.

So in this last slide of the game you can see I was able to easily checkmate the king by moving my queen in. So although the king would avoid check at the last moment, he would eventually lose because of his shortsighted behavior.

Reflection

So I gained a lot of experience from writing this game, and I wouldn’t trade it for very much, but I do have a few things to learn. Namely, how to implement Minimax properly and handle checkmate in a logical way. If any of you reading this have an idea of how to help me, give me a comment down below!

I found a video by an MIT professor which was really helpful in learning the Minimax algorithm which I would recommend if you really want to learn this stuff: Search: Games, Minimax, and Alpha-Beta. Also, if you really want to get into it you could watch this one too: Algorithms Explained: Minimax and alpha-beta pruning.

I think the future of social media is in distributed computing. If you think about it, Facebook is not going to let up on its privacy policy anytime soon and they don’t have a good reason to (government’s not going to make them). It makes sense that you wouldn’t want one corporation or government in charge of your social media feed. I don’t know of a good example of this kind of site right now that could replace Facebook but there are examples of this kind of technology out there. One example is a very Twitter-like distributed social media platform that is hosted on private servers, called Mastodon (after the elephant-like creature now extinct).

I used Mastodon for a while but the server I was on did not have people interested in the same stuff I was so I quit. But I’m getting back into and I think it could be a good platform to build on. It allows you to host your own server and not be dependent on any one company or organization to host the servers. It also has some interesting features such as 500 character “toots” (similar to tweets), local timelines (where everybody sees what everybody else on the same server posts), federated timelines (kinda like group following), and lots of little features that add up to a better whole.

If you’re interested in joining a Mastodon “instance” you can do so at https://joinmastodon.org/. The thing is to remember joining is like getting an email address – you are stuck with that instance unless you get a new account on another server.

But the point is I think distributed computing not run by any company or government is a great idea and may be what takes off in the next few years. And if you think about it, email is a distributed technology too because you can send an email from Yahoo to Gmail and it will work fine, but that’s not the case with most social networks these days. Also, Facebook and Twitter do have a pretty strong hold on their audiences right now. But that could change as they continue to ignore their users pleas for privacy.

For my part I’m going to give Mastodon another try and see where it leads. Nice thing about Mastodon is that you automatically have a built in user base that sees all your toots (called local timeline). I’ll get back to you and tell you how it goes.

By the way, if you’re into programming you can request to join my server at https://x0r.be and I’ll be able to see your toots! But of course, not everybody is interested in programming. But there’s a fair number of servers out there and there are some general purpose ones that cover every subject. The thing about starting with a new social network is that you got to be motivated because not everybody wants to switch.