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.

Made a Google calendar

I've set a rough schedule up on Google calendar. Hopefully I'll remember to keep to it.

Board Representation

I'm going to use a one-dimensional array with border squares to represent my board, as described here:

http://www.cis.uab.edu/hyatt/boardrep.html

0x88 representation seems to be the most commonly used, but I don't believe it's worth me using it. The different it will make seems minimal, and I would have to work with bitwise operations, which I'm not at all comfortable with. 0x88 representation is described at these links, as well as the first link:

http://diovo.com/2012/01/chess-programming-the-0x88-board-representation/
http://mediocrechess.blogspot.co.uk/2006/12/0x88-representation.html

I can't really build a prototype for the board representation on it's own, I'd have to work out move generation first, so I can do something with it.

Plan and Schedule

I figured it's about time I wrote a rough plan/schedule for this project.

August: and September: Read more books, papers and articles on AI, specifically chess AI, and different methods I could use for my program. I'd like to do some small tests on the way, testing out certain ideas.
October: Start building the program, putting all the ideas together.
November: to January: Keep building, testing, improving, all that stuff.

This plan came out even vaguer than I'd expected. I'm not sure what else I can do though, that really is all there is to my project: do research, build the program.

Virtual Organisms

I've read 'Virtual Organisms' by Mark Ward.

There is next to nothing in the book that's relevant to this project, except for a couple of passing references to chess playing computers. I'll quickly summarise the book, so I can refer back to this if I need to, for some reason. I'm aware this post is an incoherent mess, but it's really just for my reference.

Chapter 1) Biological stuff, the theories about how life started on Earth. DNA, RNA, genes, those sort of things.
Chapter 2) Von Neumann's automata ideas, cellular automaton, Conway's Game of Life, CA categorisation (classes I - IV), Sugarscape, quantum cellular automata to process information and make smaller CPUs.
Chapter 3) Turing machine, Godel's incompleteness theorem/Hilbert's problem, 'On Computable Numbers', theorem proving programs, Shakey, William Gray Walter's tortoises - exploring what complexity of behaviour can be achieved with the smallest number of elements, the previous belief that thinking involves mainpulating symbols that represent the world. Tilden's BEAM robots.
Chapter 4) Genetic algorithms (Tierra, Avida) - evolution. Ants/agents in BT's CSS program.
Chapter 5) FGPA (Field Programmable Gate Arrays), Adrian Thompson explores how evolution via GAs can create useful circuits on these. Working tone discriminator in 32 cells, 100 was thought to be the minimum. Thompson doesn't know how it works.
6) Humans playing God, better be careful.



And a quote from Kasparov on Deep Blue: "I could feel — I could smell — a new kind of intelligence across the table."


It was quite an interesting book.

Tic Tac Toe Board Storage Idea

I'm using a Tic Tac Toe (Noughts and Crosses) AI to test certain ideas for my chess AI, because Tic Tac Toe is an awful lot easier to build. Whilst designing this, I was thinking about the best way to represent the board and where the noughts and crosses are in the board. My first thought was to have two 2d arrays, one for each player, with each position in the array representing a position on the board. The values would be true or false, true if that player had a piece in that position, and false if they didn't. I thought this would be a better idea than having one array with either "X", "O" or "nothing" in the positions, as booleans are faster to compare than strings.

To check for a win with this system would involve checking the 8 possible lines in which there could be three of the same piece in a row, and doing this for each player. This would mean (8 * 3 * 2) = 48 checks would need to be performed on the board.

I came up with another system (which is almost definitely not original, but I hadn't heard of anything like it before), in which each player has a number that represents their board. Both numbers start at 1. The positions on the board are represented as prime numbers, as shown in the picture below:

When a player puts a piece in a position, their number is multiplied by the prime number representing that place. So if a player was to put a piece in the middle, they would multiply their number by 11. Because numbers can be split in to unique prime factors, every board layout can be represented by two numbers, one for the positions of the noughts, and the other number for the positions of the crosses. It should be noted that this approach is heavily influenced by Gödel numbering (http://en.wikipedia.org/wiki/Gödel_numbering).

In the board opposite, the number representing the crosses would be (3 * 7 * 13 * 23) = 6279. The number representing the noughts would be (2 * 11 * 19) = 418. Obviously, this approach greatly reduces the number of values that need to be stored in the computer's memory in order to represent the board. However, more interesting is the way in which this can be used to check for a win. Say you wanted to check whether a certain player had won down the middle column. If they had, their number would at some point have been multiplied by 3, 11 and 19, so (3 * 11 * 19) would be a factor of their number. Every line can be checked by this method, in only one operation, instead of the three it would take with the conventional approach.

What is surprising is just how much more efficient this prime method is. I wrote a short program in Visual Basic that generates a number of tic tac toe boards with noughts and crosses randomly distributed in them, and then the user can use either the conventional boolean array method, or the prime method, to check all of the boards for which player has won, if any. (The source code for this program can be found at  http://pastebin.com/MpnrPKjs). In all cases, both methods returned the same results for the number of wins for each player, so it's safe to say that they're accurate. Here are the results of the tests:

Now, it's difficult to see how this exact method could be of use in my chess AI: on an 8x8 grid with 7 different types of pieces, any system of numbers like this would seemingly be far too large to work. However, this experiment does demonstrate the importance of using efficient methods, especially ones that aren't quite so obvious to begin with. The chess AI will involve looking ahead across many possible moves, and analysing the positions. The more efficient the methods used, the quicker this can be done, and the further ahead the AI can look.