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
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.