Chess. (Part I)

Chess is a game almost everyone knows how to play. The rules are simple, yet the game is so deep that people devote their entire lives to mastering it. The simplicity of chess has had one very interesting consequence that is relevant to this course.

Chess engines.

For the unaware, a chess engine is a computer program specifically written to play chess. It makes a good problem since currently chess is an unsolved game (i.e there is no known strategy that will win every time), but it can quite easily be represented and evaluated in computer memory if done right.

So how might we write one? Well the first thing to think of are the basic classes we might want to simplify things. Some immediate ideas that spring to mind are:

1. A representation of the current state of the board, with a specific place for each piece, and when a move is executed it updates the board.
2. Each piece with it's legal moves.

Programming the piece movements is actually a fairly complicated question, for a few reasons. Some pieces are simple, for example the Knight. Let's say we represented co-ordinates on the board as (7,1) for G1, or C6 as (3,2) then we might make a list of legal Knight moves by creating a list of tuples where we add all 8 possible move permutations:

1. right 2, down 1 (2, -1)
2. right 2, up 1 (2, 1)
3. right 1 down 2 (1, -2)
4. right 1, up 2 (1, 2)
5. left 2, down 1 (-2, -1)
6. left 2, up 1 (-2, 1)
7. left 1 down 2 (-1, -2)
8. left 1, up 2 (-1, 2)

So for example, if we ran our function on G1, we would have the list:
[(9, 0), (9, 2), (8, -1), (8, 3), (5, 0), (5, 2), (6, -1), (6, 3)]

Then we would need to filter our list, since our coordinates are only from 1 to 8 inclusive, so we would have:
[(8, 3), (5, 2), (6, 3)]

We would then just have to exclude moves that are already occupied by our pieces, for example on the opening we couldn't play E2 since it is occupied by a pawn, so our move list would be [(8,3), (6,3)].

Other pieces get way more complicated, for example with rooks we would have to take castling into account, whether we can capture, all possible moves in each rank and file, etc

When we also think about board positions, we need to take all the possible moves, and then somehow evaluate them. This will be the topic of part II.