struct for Move

I replaced my Move class by a IMove interface and made a struct implementation for it.

Its kind of an int wrapper although a bit more luxurious since I can call methods directly on it.

    public interface IMove
    {
        int from { get; }
        int to { get; }
        bool isPromotion { get; }
        bool isCapture { get; }
        char capturedPieceType { get; }
    }

Perft 6 improved to 73.8 seconds (where Crafty uses 6.23 second). "Only" a factor 10 left to go!

Legal moves

I added a legal move generator this proved to be a much more difficult task than I initially thought.

First I thought that only adding X-ray lookups do the job. Two rules:

- don't put the king where it can be attacked
- don't move a piece from the line in which the king is x-ray attacked

But I had to add the following rules as well:

- if single checked by slider: take attacker or opposing king or move between
- if double checked: just take opposing king if possible

It took a lot of debugging before I got good perft results again:

Depth 5 took 14.2 seconds
Depth 6 took 6 minutes 10 seconds now, almost factor 5 improvement.

First perft test

Here are the result of the first succesfull perft tests of my move generator:

    Depth    Nodes     Time
        1           20    0:00:001
        2          400    0:00.016
        3         8902    0:00.142
        4       197281    0:02.720
        5      4865609    1:05.221
        6    119060324   25:30.243

Not very impressive... Crafty does depth 6 in 6.23 seconds :S

Ideas for improvement:
- make a int wrapper for the moves
- don't recreate pieces (reuse)
- generate legal moves

Getting started

I started out doing a PGN parser. I read it is supposed to be tokenized but I made a character parser anyway (which also needs a SAN parser). SAN stands for Short Algebraic Notation. The PGN parser talks to an IBoard interface:

    public interface IBoard
    {
        bool CompleteMove(Move test);
        void MakeMove(Move move);
        void UnMakeMove(Move move);
        void Init();
        bool IsWhiteMove { get; }
    }

Its the minimal interface the PGN parser needs. I skipped the part where FEN setup is done. (Had enough parser building excersise for the moment)

The CompleteMove is where this incomplete SAN move is completed. For example Nxf6 gets translated to a Move where h5xf6 Knight captures Queen. Here a lot of movement knowledge is already needed.

I found this game somewhere as for the testing of the parser:

[Event "New Orleans"]
[Site "New Orleans"]
[Date "1849.??.??"]
[Round "?"]
[White "Morphy, Paul "]
[Black "J. MacConnell sr"]
[Result "1-0"]
[Annotator "Fritz 6 (6s)"]
[PlyCount "57"]
[EventDate "1849.??.??"]

1. e4 {C39: King's Gambit Accepted: 3 Nf3 g5 4 h4} e5 2. f4 exf4 3. Nf3 g5 4.
h4 g4 5. Ne5 h5 6. Bc4 Rh7 7. d4 d6 8. Nd3 f3 9. g3 (9. gxf3 Be7 10. Be3 Bxh4+
11. Kd2 Bg5 12. f4 Bf6 13. a3 c6 14. Nc3 Bh8 15. f5 Ne7 16. Qe2 Kf8 17. f6 Bxf6
18. Raf1 d5 19. Rxf6 dxc4 20. Ne5 Nd7 21. Nxd7+ Bxd7 22. Rh6 Rg7 23. R6xh5 Ng8
{Pektor,A-Zvara,P/Prague 1992/0-1 (48)}) 9... Nc6 10. Nf4 $146 (10. c3 Nge7 (
10... Nce7 11. Kf2 c6 12. Nf4 Qc7 13. Qb3 b5 14. Bd3 Rh8 15. Re1 Ng6 16. Nxg6
fxg6 17. e5 Ne7 18. Bxg6+ Kd8 19. Qf7 Nxg6 20. Qxg6 Qg7 21. Bg5+ Kc7 22. exd6+
Kb6 23. Bd8+ Ka6 24. Qxg7 Bxg7 25. Bc7 {
Abbe de Lionne & Morant-Maubisson & Auzout/Paris 1680/1-0 (40)}) 11. Nf4 a6 12.
a4 Bg7 13. Qb3 Bh8 14. Nxh5 Kf8 15. Nf4 Na5 16. Qa2 Nxc4 17. Qxc4 c6 18. Nd2 d5
19. exd5 cxd5 20. Qb4 Bf6 21. Nf1 Kg7 22. h5 Nc6 23. Qc5 Be6 24. Qa3 Qd7 {
Jannisson & Maubisson-Lionne & Morant/Paris 1680     (36)}) (10. Bb5 d5 11. Ne5
Bd7 12. Nxd7 Qxd7 $17 (12... Kxd7 $2 13. exd5 Bd6 14. Kf2 $18 (14. dxc6+ $6
bxc6 15. Ba4 Bxg3+ 16. Kf1 Rb8 $16 (16... Bxh4 $4 {
taking the pawn will bring Black grief} 17. Qd3 $18)))) 10... Bd7 (10... Nf6
11. Nc3 $17) 11. Nc3 Nf6 (11... Bg7 12. Be3 $17) 12. Be3 Ne7 (12... Bh6 13. Rf1
$17) 13. Kf2 c6 (13... Bh6 14. e5 dxe5 15. dxe5 $17) 14. Re1 Bg7 15. e5 dxe5
16. dxe5 Nfd5 (16... Nfg8 17. Ne4 Bxe5 18. Ng5 Bxf4 19. Nxh7 Bxe3+ 20. Rxe3 $11
) 17. Bxd5 (17. Nfxd5 Nxd5 18. Nxd5 cxd5 19. Qxd5 Bh8 $14) 17... cxd5 (17...
Nxd5 18. Ncxd5 cxd5 19. Nxd5 Be6 $14 (19... Bxe5 {
Black again will not be able to digest the pawn} 20. Bg5 f6 21. Nxf6+ Kf7 22.
Rxe5 (22. Qxd7+ $6 {is not possible} Qxd7 23. Nxd7 Bd4+ 24. Kf1 Kg6 $18) 22...
Qb6+ 23. Re3 $18)) 18. Bc5 (18. Ncxd5 Nxd5 (18... Bxe5 $2 {
is nothing because of} 19. Bb6 Qb8 20. Bd4 $18) 19. Nxd5 Be6 $14 (19... Bxe5 {
as before the pawn must remain untouched} 20. Bg5 f6 21. Nxf6+ Kf7 22. Rxe5
Qb6+ 23. Re3 $18)) 18... Bc6 (18... Rc8 19. Bxa7 Qa5 20. Bd4 $15) 19. b4 (19.
Qd3 Rh6 $11) 19... b6 (19... d4 $142 20. Qd3 Rh6 $15 (20... dxc3 21. Qxh7 Kf8
22. Rad1 $18 (22. Qxh5 $6 {is the less attractive alternative} Qd2+ 23. Kg1 Kg8
$18) (22. Nxh5 $4 {the pawn is indigestible} Qd2+ 23. Re2 Qxe2+ 24. Kg1 Qg2#)))
20. Bxe7 $14 Qxe7 {The isolani on e5 becomes a target} 21. Nfxd5 Qb7 $4 (21...
Bxd5 $142 {is just about the only chance} 22. Nxd5 Qd8 23. Nf6+ Bxf6 24. exf6+
Kf8 25. Qxd8+ Rxd8 $16) 22. Nf6+ $18 Bxf6 23. exf6+ Kf8 24. Qd6+ Kg8 25. Re7
Qc8 26. Rc7 Qf5 27. Qxc6 {Threatening mate: Qxa8} Qxc2+ (27... Rf8 {
does not save the day} 28. Nd5 Qe5 $18) 28. Ke3 Rd8 (28... Rf8 29. Rxa7 Qb2 30.
Ra8 Qxc3+ 31. Qxc3 Rxa8 32. Qc7 $18) 29. Rd1 $1 {
the end of the story. Threatening mate... how?} (29. Rd1 Rf8 30. Rxa7 $18) 1-0

It has a lot of nested variants with comments.

I made the SAN and the PGN parser in a way that it should be possible to parse any game type of which the board spans at most 26 by 26 with pieces that can be described by a Unicode character. (Didn't test this though).

To test the parser, I implemented a SimpleChessBoard class which implements the IBoard interface.

Test with SilverLight example

Underneath you see the SilverLight demo application I want to use to demonstrate features or bugs of the engine. Currently it is the original version but I'll strip out the garbo engine. The sample is from here.

Generating Moves

Since the code should be as readable as possible I'll start with some move generating pseudo-code. I want to be able to generate few moves at a time so I'll start with the capturing moves.

- checking moves
- capturing moves (preferably ordered Least Valuable Attacker/Most Valuable Victim)
- promotions moves
- castling moves
- other moves
- check evasion moves

Just a reminder to myself: the board should be able to continue where it left off doing moves after an UnmakeMove is done.

First decision is where to start generating: with the attackers or the victims.

Attacker approach:

Player.Knights.ForEach(x => x.YieldAttackingMoves);
Player.Bishops.ForEach(x => x.YieldAttackingMoves);
Player.Rooks.ForEach(x => x.YieldAttackingMoves);
Player.Queens.ForEach(x => x.YieldAttackingMoves);

etc.

Victim approach:

Ponderer.AttackedPieces.ForEach(x => x.Attackers.ForEach(y => y.YieldAttackOn(x)));

Since I want to have the possibility to have the LVA/MVV ordering I'll go for the victim approach. AttackedPieces should be ordered MV first and Attackers LV first.

Note for later: The LVA/MVV may fail, so I might need to add a on the fly Static Exchange Evalutation later.

I start doing this pseudo code creation to get insight into what my Board class will have keep track of.

My Chess Engine

Every now and then I feel like picking up a new hobby. Chess Engines have always fascinated me. I have built a chess engine once before in Delphi (version 7 back then). It used bit-boards with maintained rotated boards (no magic). It only did do: move generation, material evaluation and alpha-beta search, but it already beat me most of the time. (This says more about me then about the engine). I'll try making the engine available as soon as possible so that the audience can help me improve the engine.

Since there are already so many chess engine projects I postponed the picking of a name for this engine. I have some goals defined for this engine:

- architecture should be so that logical parts can be exchanged easily
- the code should be extremely readable without sacrificing to much performance