Update

Since the last update I have:


Made it an awful let quicker, thanks to a great suggestion by an anonymous guy on an anonymous internet forum. The majority of the time taken for the AI to move was spent just copying chess board data structures (this had to be done about 500,000 times, and each board was an array of 120 items). The suggestion was to add a function that undoes a chess move, and then I could do the following in my recursive function:

recursive function:
     makeMove
     call recursive function again
     undoMove
end function

Because of the beauty of recursion, I only ever need one board to accomplish this, it's fantastic. This has sped up the time the AI takes on a very tricky configuration from a maximum of 13 seconds to 3 seconds.


I also made a few little petty optimisations, added an icon, and displayed where the AI last moved (because I found if I blinked when it moved, I couldn't work out where it had moved to/from).

Added a list of where the pieces are

The program has sped up considerably after I made this small change. Whereas before, it took 5-10 seconds to look 3 moves ahead, and took forever to look 4 moves ahead, now it can look 3 moves ahead instantly (pretty much), and 5-10 seconds to look 4 moves ahead.

Before, when generating all the moves from a board, I searched every square on the board, and then found the squares with pieces on them, from which I could generate moves. Now, I've "attached" two lists to each board, one with all the indexes containing white pieces, and one for black pieces. So when I look for all the pieces, I can just loop through all the pieces in one of the lists. Yay, optimisation!

So how can I improve this?

As mentioned in previous posts, the program works, but it can certainly be improved. And here are some possible ways how that can be done:

• Avoid searching for the pieces in every board: When the moves are generated for a board, every square on the board is checked to see if it contains a piece that can make a move. I imagine quite a bit of time could be saved if I attached to the board a list of all the squares containing the white pieces, and all the squares containing the black pieces.
• Move ordering: A core part of alpha-beta pruning is not following up a move if it isn't going to be better than previous ones. This works much better when the first moves checked are most likely to be the better moves.
• Opening moves library: This would put the AI in a much better position for the rest of the game; using tried and tested opening moves, because it certainly cannot look forward enough itself to work out good opening moves.
• Endgame moves library: Although it performs fairly well and quickly in the endgame phase (because there are a small number of moves to analyse), it would be made as close to unbeatable as possible if some sort of endgame library was introduced when there are, say, 5 or fewer pieces. This link gives an example of what I'm talking about.

What needs to be done

At present, my program plays completely bug-free (as far as I can tell). The problems now are the speed, and the number of moves it can look ahead at.

Speed:
The following image is a graph showing time taken against number of moves analysed. For a large amount of moves (generally during the mid-game phase), the maximum time taken is about 24 seconds. This is quite annoying when playing, and it would be nice if this time could be reduced.

Number of moves:
At present, the program looks 3 moves ahead (that is, a computer move, followed by a player move, followed by a computer move). While this works well in most situations, it makes the program rather useless at evading checkmate, in particular, it can't avoid Fool's Mate. I have programmed it to not actually detect check when looking forward (because testing whether every move leads to check would take far too long), instead it evaluates the boards, and if the king has been taken, the board will have a very low score (because the king is given a value much, much higher than any other piece), and it will infer from that, that there was check a move ago. So because of this, it can't look far enough ahead to avoid most checkmates. Silly thing.

IT IS GLORIOUS!

After an hour or so of persuading myself that I should start working on my Extended Project again, I started working on my Extended Project, and within a few minutes found a tiny oversight in the code (I put 119 where it should have been 121) which explains why the computer was playing so randomly when it was meant to be looking at least 2 moves ahead. So I fixed that, then tested it, and I've only played 1 game so far, but the program actually seems to be looking ahead for moves.

Anyway, I was in the middle of this game, and the most wonderful thing happened. The program forked me (see image, it moved the black knight). It made an intelligent move. It was magical. It's the cleverest thing that something I've made has done. This must be what it feels like to raise a child, and then watching that child grow up to be an astronaut, or a hotshot lawyer.

Check and checkmate implemented.

After a lot of bugs, I've finally implemented check and checkmate in to my program. So now, a player can't move in to check, a player has to move out of check, and checkmate can be detected, and will end the game.

I also tidied up the code a fair bit, it's very easy for subroutines to get out of hand on a project like this.

And pawn promotion is done. Although you can only promote a pawn to a queen, but it's just not worth implementing pawn promotion to any piece.

One strange little glitch I'm having is when a game is won and the board is reset, a seemingly random piece appears on the square shown in the picture. How peculiar.

Another bug

Because I've already established examiners love problem-solving abilities, I'll post another problem. I tried to add a function that will work out whether or not a player is in check after the opponent makes their move, but what it does is constantly tell everyone they're in check, after every single move. So I'll fix it and then edit this post to explain how I fixed it. I hate posting mundane stuff like this.

EDIT:
Well, here's what the problem was. As I might have explained somewhere else on the blog, each different chess piece is represented by a number, 1 being a pawn, 2 being a rook, etc. Positive number are white pieces, negative numbers are black pieces (-1 is a black pawn, 1 is a white pawn). To work out whether the king was in check, I traced outwards from the king, looking for certain pieces in certain directions (i.e. bishops or queens diagonally). In the check for these pieces, I compared the absolute value of the piece to the pieces I was looking for, because it required less thought than trying to work out the correct sign. That is, if I was looking for a bishop diagonally, I'd check in all diagonal directions whether the absolute value of the piece was 4 (the bishop's number). Stupidly enough, I didn't realise this would also include piece's that belonged to the player, along with the opponent's pieces. So basically, each player's queen kept putting that player in to check.

Glitches

Some strange glitches are occurring whilst I'm playing my chess game involving the computer's moves. The computer attempted to take my pawn with its bishop, but his bishop disappeared. Later, it attempted to move a queen, and the queen disappeared. I'm posting this because it will hopefully demonstrate my problem-solving abilities. Examiners love problem-solving abilities.

EDIT:
I fixed the problem. Turns out where I wrote 39 and 89 in two lines should have been 38 and 88. Obviously. Here's a picture, in case you're unsure as to what those numbers look like.

It plays!

I've gotten to the point where you can actually play against the computer now. It does, for now, pick its moves randomly, and there is, for now, no way of detecting check or checkmate, but at least it plays.

(Obligatory picture which looks the same as all previous pictures):

A flowchart

This is a flowchart that I have used to determine what to do when a square on the board is clicked by the user.

DISCLAIMER: This was not posted because I felt I really needed to post something soon because I haven't posted anything for a while. This is definitely actual work.

Claude Shannon Paper

I read the paper 'Programming a Computer for Playing Chess' by Claude Shannon (1949). I thought it would be difficult to read, but it was fine, and certainly very useful from a theory point of view. It's remarkable how relevant most of it is today, more than 60 years later.

Download link

Move Generation

Move generation is sorted, apart from special cases like castling, en passant and not allowing moves in to check. I have to be careful with them, they're rare cases so if I implement them badly, they'll slow the search down with next to no gain. Here are some pictures with green squares illustrated available moves for a certain piece:

New Pieces Icons

I've found some good looking icons to replace my horrible home made icons for the chess pieces.

Look how pretty they are:

Icons are from Clker, which are all public domain images.

First Version of Something

I finally got round to making an actual thing:

All it does so far is let the user place pieces and remove them ( all the pieces are included, not just white queens).

It can be quite difficult to make this, because you have to be very forward thinking. You don't want to implement a clumsy mechanism early on because it'll probably make things so much harder later on in the project.

The next thing to do is move generation, which I'll then test thoroughly for as many different configurations as I can be bothered to do. If I can implement it successfully, I may use Perft, which is an algorithm designed to test the move generation system.

After that, I'll make sure the whole thing is optimized as much as reasonably possible, and everything is done probably (as in, no messy short cuts that may cause problems in the future).

And Another Book

It’s hard to find books that cover chess AIs. I read ‘The Binary Revolution’ by Neil Barrett. It would have been very useful to read this before I did Computing at AS level, it covers a lot of the content in an easier way. There was a small bit on chess at the end, which I may as well copy here:

“The principle of playing chess was actually found to be reasonably straightforward for a computer. At any stage of the game, each player has only a limited set of available moves, creating a small set of alternative board positions. From each one of these, a further set of moves can be made and board positions created; and from those again, a small set of yet further moves is possible. At each stage, a ‘tree’ of possible board positions is produced. Chess programs work by producing a complete set of ‘If I do this, then you can do this, and then I can do this’ sequences of anticipated moves; the number of future moves calculated is called the ‘depth’. For each of the board positions then produced, the program calculates a score for itself and for its opponent; it chooses the move which minimizes the opponent’s advantage whilst maximizing its own. This is a strategy called ‘minimax’, created by Claude Shannon in 1949 and perfected by Alan Turing the following year. The first computer program written to execute minimax for chess was produced in 1956 at Los Alamos, followed two years later by a more powerful system at IBM.

Using minimax and a depth of only five moves, chess programs can trounce all but the most experienced of club players; given a slightly greater depth, the programs can beat all but the most experienced chess grandmasters. In 1997, when a dedicated computer system developed by IBM (called ‘Deep Blue’ and capable of examining 200 million chess positions per second) was allowed a depth of 14 moves, it beat the then world champion, Gary Kasparov. Although chess is indeed a striking example of human intelligence, and although computers are not programmed to play in anything like the same way as humans apparently do, it seems to be at least one human-like thing that can better performed by computers.”

That “five moves” bit is interesting, I hadn't heard that before.