Chenard Web Edition by Don Cross - revision history

This is the list of changes I have made during the development of my online chess applet.

12 January 2006

• Added some more opening continuations for the Two Knight's Defense.

2 January 2006

• When the computer predicts the opponent's move correctly, it now recycles the previous path information and starts at a higher search depth. This allows the computer to look deeper into the future within a given amount of time.

31 December 2005

• Added support for Forsyth-Edwards Notation (FEN). Now display the board position in Java console after each move, including the FEN string.

30 December 2005

• Fixed a really bad bug in the quiescence search: the function for generating pawn captures/promotions was not generating any pawn captures other than those that caused promotion! In other words, it hardly ever noticed a pawn capture. I expect this fix will cause some questionable tactical behavior I have seen to go away.
• Improved search speed by about 30% by eliminating unnecessary determinations of whether making a move causes check to the opponent in certain cases. For example, if the computer is making a move just to see whether it is legal, there is no need to determine whether it causes check to the opponent. All that is necessary in that case is to see whether the move causes one's own king to be placed in danger.
• Made even more search speed improvements by using lazy illegal move determination. I used to generate a list of raw moves, then filter out all illegal moves, then try searching through that list. Now I generate a list of raw moves and start searching. If I find a position where the side who just moved is still in check, I backtrack and try another move. The reason this is faster is pruning: much of the time, pruning will bail out of a level of the tree before a move is even explored, so it doesn't matter whether that move is illegal or not!

29 December 2005

• Wrote an automatic converter to translate Chenard's opening library into Java code that this applet can use. So now it knows all the openings that Chenard does. In the process, I found some mistakes in Chenard's opening library and fixed them!

28 December 2005

• Enhanced the search to find knight forks and pawn forks. The pre-enhanced quiescence search had a tendency to miss them until it was too late, because the victim of the fork often has no captures, thus pushing the loss of material beyond the search horizon. I just added a small fork probability bonus in the eval function.
• Added a small penalty in eval for having an immobile rook.
• Added bonus for having pawns in front of a timid king.
• Added a tiny opening book. (Needs a lot more work.)
• Fixed yet another bug in draw-by-repetition detection. This time was rather subtle: it turns out that the makeMove function was not clearing the "in-check" bit for whichever side just moved. This caused draw-by-repetition to think the position wasn't repeated because the flags had changed in some cases. Now it always clears the bit for the side that moved, and if it turns out the mover is still in check, the move is later determined to be illegal and is filtered out anyway.

21 December 2005

• Fixed logic error that made draw-by-repetition notice a draw on the fourth position repetition instead of the third. (The program compares the current board position with past board positions, and if 2 past positions match the current position, it means the current position has occurred 3 times.)

20 December 2005

• Fixed occasional null pointer exception bug that was introduced as a side-effect of timed search. When think time expired, the best move could have been null, even in full-width search. This resulted in the game abruptly stopping play.

18 December 2005

• Made average evaluation speed 26% faster by skipping time-consuming positional analysis when the evaluator encounters positions in which obvious material blunders have occurred. In these cases, positional analysis will not matter, because the result will be pruned out anyway.
• Toned down the value of passed pawns. The program was too willing to throw away other material in order to get a passed pawn, and would later lose the game because of it.
• Now the full-width search will delay quiescence search for one extra ply when the leaf node has the current player in check. This adds a small amount of time to the search, but should dramatically improve ability to see forced checkmates, forks, etc.
• Switched from fixed full-width search limit of 4 plies to timed search of 5 seconds. In the future, I intend to add the ability for the user to adjust the think time, and therefore the difficulty level.
• Added special evaluation heuristics for the case where one side has a lone king and the other side has at least one queen and/or rook. This heuristic says that the winning side wants to push the losing king into a corner, and that the winning king wants to be close to the losing king to assist in checkmate. I call this slaughter mode.

17 December 2005

• Added bishop position table.
• Added bonus for trading when computer has material advantage, and penalty when opponent has material advantage.

16 December 2005

• Improved search speed by another 19% by using hash tables that feed back good moves to the move ordering when the same chess position is seen again.

15 December 2005

• Now we detect draw by repetition. Not only is this important for detecting and displaying that the game is over in that case, but it steers the search toward moves that force draw when the computer is losing, and away from draw when it is winning.
• Increased search efficiency by adding "killer move" heuristic. This causes increased pruning of the search tree by searching moves sooner that were previously deemed best for related board positions. Now the search is doing the same job with 43% less work!

11 December 2005

• Added knowledge about pawn configuration to the evaluation function:
  • Bonus for pawns protecting each other.
  • Bonus for passed pawns.
  • Penalty for doubled pawns.
  • Penalty for isolated pawns.
  • Penalty for pawns on rook files.
  • Bonus for pawns in the center.
  • Bonus for advancing pawns closer to promotion.

10 December 2005

• Fixed bug in move notation generator: it was generating ambiguous notation when the move was not pawn promotion, two pieces of the same type could move to the given destination, and both pieces started on different ranks and different files.
• Use best path from each iteration of the search to help order move lists in the next iteration. The intent is to make the search faster by pruning out more of the search tree. This is not yet working as well as I had hoped.

9 December 2005

• Now detect draw due to 50 moves having elapsed without a capture or pawn advance.
• Minor tweaks to evaluation function: added motivators to hasten good things and delay bad things, plus corrected a logic error in how tempo bonus is computed.
• Fixed problem in search algorithm that caused it to gloss over non-stalemate draws and think the game was still in progress. This caused it to go into repeated positions and draw the game even though it could have forced a win. (Once the draw-by-repetition logic is implemented, this will happen after 3 moves instead of 50.)
• Fixed problem in pawn promotion graphics that caused question mark to not always appear on the promotion square.

8 December 2005

• Now we detect that the game is over and display a message on the chess board saying that White won, Black won, or the game is a draw.
• Added the ability to detect that a game is a draw due to the fact that neither side has enough material to possibly issue checkmate. (I have not yet added checking for 50-move rule or draw by repetition.)

7 December 2005

• Added user interface for pawn promotion. When human player promotes a pawn, he sees a question mark where the pawn is going to be promoted. He also sees a yellow box with a queen, rook, bishop, and knight. The computer waits for him to click on one of the pieces. As soon as he does, the pawn is promoted to that piece and the game continues.

6 December 2005

• The applet now displays moves using Portable Game Notation.

5 December 2005

• The computer now terminates the chess search once it sees a move that forces a win in the minimum number of plies, or that it is going to lose no matter what it does anyway. In other words, once a forced win/loss is detected, the search algorithm will not change its mind no matter how much more time it spends thinking, so there is no point wasting time by thinking further.
• Added a primitive game listing text display to the right of the chess board. Eventually I want to replace the cheesy R2D2 syntax with Portable Game Notation (PGN).

4 December 2005

• Added knight position tables to evaluation function.
• Added move ordering to improve pruning efficiency. Now the search is much faster!
• Starting to add iterative deepening in the search. This is a first step toward having a timed search, meaning the computer will always used a specified amount of time to pick its move.

3 December 2005

• The applet now randomly picks whether to play White or Black.
• Now the computer player chooses randomly from the set of moves that it considers to have equal maximum value. This will reduce the robotic nature of its play and add variety to repeated game play.
• Now the applet is compressed into a Java Archive (jar) file. The main reason is to enable the board to be displayed much more quickly when the page is loaded. The browser will now download all 28 chess piece bitmaps and all 9 Java class files with a single http transaction. Before, the piece bitmaps would not be downloaded until the applet started rendering the board for the first time.