Timothy's Blog

A day in the life of a creative filmmaker

Adventures with Minimax

May 14th, 2020 by

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 20th of May, 2019, to the 3rd 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.

The Immovable Line

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.

Note Taking Pieces

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.

King Avoidance Success

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.

Checkmate?

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.

Bits and Qubits

November 4th, 2019 by

I’ve been thinking about quantum computers a bit and I think quantum computers could really change the world. The quantum computers of the future will make the supercomputers of today look like calculators. And a lot of people believe this. I think in this article I linked to it said a 300 qubit quantum computer would be equal to about 2*10^90 bits on a classical computer (that’s 2 with 90 zeros after it).

The reason this is so is because quantum computers harness the quantum nature of the atom in a way classical computers do not. Whereas classical computers calculate by simple bits, quantum computers use an entirely new thing called a qubit. Qubits aren’t really binary bits because they don’t represent a single on or off state but really a superposition of the two states that particular particle can be in and is a product of its wave function (the math behind this superposition). It’s really powerful if you think about it (and understand the physics behind it). Quantum computers basically rely on the computing power of the atom to make their calculations.

So though quantum computers will never replace classical computers because quantum computers are not good at most of what classical computers do, and though the quantum computers of today are not as powerful as we can envision they will get better and better till they surpass our expectations just like classical computers did.

IBM Q computer. Credit: Pierre Metivier

The reason quantum computers have been held back is that the quantum qubits in quantum computers are very fragile. The reason for that is that when you interact with a qubit in any way a measurement is made and the superposition of the states of the qubit collapse to just 1 or 0. Destroying the quantum information. Scientists try to get around this problem by cooling their quantum computers to a fraction of a degree above absolute zero to isolate qubits from their environments so they don’t get jostled. Unfortunately they still have a problem getting those qubits to stay that way for more than a few tens of microseconds. But there advances being made (for example using graphene as a superconducting material).

For now quantum computers remain giant super-cooled machines in researchers laboratories but some day they may become as common as your cell phone. If you remember the same thing happened with computers (think of ENIAC) and I think the same thing will probably happen with quantum computers given enough time.

I’ve linked an article I read that goes into more detail on this. Read that if your more interested in learning more. Or just google “quantum computers”. There’s a whole world out there waiting for you to explore it.

As for me, I’m thinking of studying quantum mechanics (on my own) and maybe getting a book on it. I have a recommendation from somebody I found on YouTube that will probably be good. I’ve been reading articles on Quantum Mechanics and am fascinated by the science and would like to learn more.

Timothy’s 10 Laws of Computing

May 14th, 2019 by

I made up this list last night just for fun so I could post it on this blog. It’s not really a list of real “laws” but is rather some things that I thought were funny. I guess you’d have to be a computer nerd to understand them.

  1. Never start a process or ask a computer to do something that you don’t want it to do.
  2. Never stop a process or something that you do not want to stop.
  3. Never start multiple processes when your utilities are not sufficient.
  4. Never hit a button just because you don’t know what it does.
  5. Always buy a faster computer than you need now.
  6. More RAM is always better.
  7. Wait, you thought 8K was going to be enough? (In my humble opinion 4K is enough for small screens)
  8. Old computers make great boat anchors.
  9. Moore’s law is not a law.
  10. Computers are the new kid on the block. Use a pencil and paper when your computer isn’t available.