Finished the chess program.

I think I'd better stop here. There are a few more things I could add, but they won't improve it very much, seem quite difficult to implement, and I've already done what I've set out to do. Also there's a deadline very soon.

Since the last update, I've added the ability to undo moves, made some buttons for people who can't handle keyboard shortcuts, fixed a few bugs involving pawn promotion, and made the AI slightly less aimless in the opening part of the game (it's still utterly aimless in endgames: if you have only a king, and it has two rooks, it won't ever let you capture the rooks, but it will dance around with until it happens to checkmate you).

Now I have to fill in all these forms, reports, reviews and conclusions that the examiners love so much. Sigh...

Oh, and I'll put the source code up, if anybody is at all interested in how I did something: Link to source code

And I just realised I haven't put up any new screenshots. So here:

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.