tag:blogger.com,1999:blog-71449571209016610422024-03-05T23:43:13.131+02:00VICKI Chess EngineThe tale of a chess engine - from the very beginning!Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.comBlogger39125tag:blogger.com,1999:blog-7144957120901661042.post-67089537274732921092013-04-09T07:54:00.001+02:002013-04-11T11:28:06.891+02:00MagicsAs mentioned earlier, I wanted to try Magic bitboards for the sliding pieces (rooks, bishop and queens). Magic bitboards are actually pretty easy once you get the gist of it. There are websites that explain the concept quite nicely (such as <a href="http://www.rivalchess.com/magic-bitboards/">www.rivalchess.com</a>). Basically you take the attack board of your sliding piece, minus the edges. For example, a rook on a1:<br />
<br />
(bitboard 1)<br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 1 1 1 1 1 1 0</span><br />
<br />
This board represents all the squares that the piece can go to, if the board was completely empty. These can easily be calculated before-hand and stored in an array (long[64]). I call these the <b>attack bitboard.</b><br />
<br />
(I did not quite understand why the edge squares should be left out. It's actually pretty easy... Less bits equal less complexity and the piece will always stop on an edge, so we can simplify the board by leaving them out from the start)<br />
<br />
...this values gets bitwise "and"-ed with the board containing all the pieces, or the <b>occupancy board</b>. The result is a board, which indicate all the piece blockers for a rook stationed at a1 (i.e. <b>blocker bitboards</b>). The big problem and the reason for the various techniques (rotated bitboards, magics, etc.) is that we only really want the first blocker in a direction. For example, the following blocker bitboards:<br />
<br />
(bitboard 2,3 and 4)<br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0 </span><span style="font-family: 'Courier New', Courier, monospace;">0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0 1</span><span style="font-family: 'Courier New', Courier, monospace;"> 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0 </span><span style="font-family: 'Courier New', Courier, monospace;">0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0 </span><span style="font-family: 'Courier New', Courier, monospace;">0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0 </span><span style="font-family: 'Courier New', Courier, monospace;">0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0 </span><span style="font-family: 'Courier New', Courier, monospace;">0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 1 1 1 1 0 </span><span style="font-family: 'Courier New', Courier, monospace;">0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0</span><br />
<br />
could all reduce to:<br />
<br />
(bitboard 5)<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 1 0 0 0 0</span><br />
<br />
...and in turn, this board should be used to provide us with:<br />
<br />
(bitboard 6)<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">1 0 0 0 0 0 0 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">0 1 1 1 0 0 0 0</span><br />
<br />
Bitboard 5 (<b>reduced bitboard</b>) indicates a blocker on a6 and d1. Bitboard 6 represents a rook on a1 that can move to b1,c1 and potentially capture on d1, as well as move to a2, a3, a4, a5, (<b>result bitboard</b>) with a potential capture on a6. (To determine if we can capture/move on d1 and a6 is trivial as we only need to "and" the result bitboard with the inverse on the friendly pieces. If d1 or a6 is still set, it means that there the square is either empty or contains an enemy piece that can be captured).<br />
<br />
Anyway, back to the problem. If we had infinite memory, we could create a table long[9,223,372,036,854,775,808] and store the result bitboard for each blocker board (i.e. bitboard 6 for bitboards 2,3 and 4). However... we don't have that amount of memory, and even if we had, it will be a terrible waste. This is where Magic bitboards comes in very handy. Simply take your blocker board, multiply it with some magic number and then simply mod it with a power of 2 (which is essentially a shift). You end up with some index number which is then used for a lookup in a much smaller database, i.e.:<br />
<br />
((attack-bitboards-for-rooks[a1] AND occupancy) * magic-number[a1]) >> (64 - bits-required[a1])<br />
<br />
It turns out, that it is easy to find unique locations for a database the size 2 to the power of the number of bits in the original attack board (and thanks to the missing edge-bits, it is 2 bits smaller). For example, a rook on a1 requires a 12-bit database and we therefore have to shift right with 52 bits, leaving an index in the range 0...4095.<br />
<br />
A chess program will typically have a magic number for each piece for each square (i.e. 128 in total), as well as different space requirements for each square, ranging from 5 to 12 bits (and possibly less...).<br />
<br />
Finding the magics can be done brute force, using random numbers. To find a magic number for a specific square, for a specific piece, it boils down to the following:<br />
<br />
<ol>
<li>Pick some random 64-bit number, call it <b>magic</b>.</li>
<li>Get all the variations for the piece on the square (i.e. for example bb 2,3 and 4).</li>
<li>Create a <b>database</b> of size 2^bits (starting of with the number of bits in the original attack-board, i.e. bb 1).</li>
<li>For each attack <b>variation</b></li>
<ol>
<li>Calculate the result bitboard for the variation, i.e. bb 6 for bb 2,3 and 4. </li>
<li>Create an <b>index</b> by multiplying <b>variation</b> with <b>magic</b> and shift it right with 64 - bits.</li>
<li>If <b>database</b>[<b>index</b>] is not 0 and the result board stored there is not compatible with <b>variation</b>, then we have a clash and we have to try a new magic number.</li>
<li>Otherwise, we store the result bitboard for <b>variation</b> at <b>database</b>[<b>index</b>].</li>
</ol>
<li>If the loop ends with no clashes, then <b>magic</b> is a valid magic number for the piece on a1.</li>
</ol>
<div>
<br />
It takes a few seconds to find all 128 magics, if the bits is equal to the number of bits in the original attack bitboard. However, for a rook on a1, we actually only need a database of size 49. There are only 49 unique configurations with a blocker on the a-rank and first-file. To find a magic number that magically hashes all 4096 variations to a database of 49 result bitboards is a monumental task and turns out to be ridiculously difficult. In fact, no one really knows whether it is possible or not.</div>
<div>
<br /></div>
<div>
Fortunately, we don't have to go the absolute minimum. Shaving off a single bit, will half the space requirements for that square already. So instead of searching for a magic for a 12-bit database, we could try and search for a magic for an 11-bit database for the rook on a1. This is still difficult, but doable...</div>
<div>
<br /></div>
<div>
I have written a program that searches for magics for all pieces, all squares for all database sizes. So far, all my efforts have produced, the following:</div>
<div>
<br /></div>
<table border="0" cellpadding="1" cellspacing="3" style="width: 600px;">
<tbody>
<tr>
<td><b>Piece</b></td>
<td><b>Square</b></td>
<td><b>Bits in attack board</b></td>
<td><b>Bits required for database</b></td>
<td><b>Magic! (base-16)</b></td>
</tr>
<tr>
<td>Bishop</td>
<td>a1</td>
<td>6</td>
<td>5</td>
<td>90a207c5e7ae23ff</td>
</tr>
<tr>
<td>Bishop</td>
<td>b1</td>
<td>5</td>
<td>4</td>
<td>caad949dbf3ffed4</td>
</tr>
<tr>
<td>Bishop</td>
<td>g1</td>
<td>5</td>
<td>4</td>
<td>2a0f37664bfef560</td>
</tr>
<tr>
<td>Bishop</td>
<td>h1</td>
<td>6</td>
<td>5</td>
<td>f174631c5963ffd7</td>
</tr>
<tr>
<td>Bishop</td>
<td>a2</td>
<td>5</td>
<td>4</td>
<td>b2d764c66b3617f5</td>
</tr>
<tr>
<td>Bishop</td>
<td>b2</td>
<td>5</td>
<td>4</td>
<td>f97758b06ebb3f25</td>
</tr>
<tr>
<td>Bishop</td>
<td>g2</td>
<td>5</td>
<td>4</td>
<td>2ba278d2d3287f3f</td>
</tr>
<tr>
<td>Bishop</td>
<td>h2</td>
<td>5</td>
<td>4</td>
<td>0ca85d99b283fe74</td>
</tr>
<tr>
<td>Bishop</td>
<td>a3</td>
<td>5</td>
<td>4</td>
<td>8440f94bf539afdb</td>
</tr>
<tr>
<td>Bishop</td>
<td>b3</td>
<td>5</td>
<td>4</td>
<td>c6e0343a763ab7f6</td>
</tr>
<tr>
<td>Bishop</td>
<td>g3</td>
<td>5</td>
<td>4</td>
<td>78b4002cccfabedf</td>
</tr>
<tr>
<td>Bishop</td>
<td>h3</td>
<td>5</td>
<td>4</td>
<td>cd4a03745eacbfd0</td>
</tr>
<tr>
<td>Bishop</td>
<td>a6</td>
<td>5</td>
<td>4</td>
<td>24ffd9f54b3ec007</td>
</tr>
<tr>
<td>Bishop</td>
<td>b6</td>
<td>5</td>
<td>4</td>
<td>6ccffd59e5fae014</td>
</tr>
<tr>
<td>Bishop</td>
<td>g6</td>
<td>5</td>
<td>4</td>
<td>2eff79dda4a23407</td>
</tr>
<tr>
<td>Bishop</td>
<td>a7</td>
<td>5</td>
<td>4</td>
<td>e3dff263999c90f5</td>
</tr>
<tr>
<td>Bishop</td>
<td>b7</td>
<td>5</td>
<td>4</td>
<td>f06bfd8ab019c8bd</td>
</tr>
<tr>
<td>Bishop</td>
<td>g7</td>
<td>5</td>
<td>4</td>
<td>3fffa27235d24ee9</td>
</tr>
<tr>
<td>Bishop</td>
<td>h7</td>
<td>5</td>
<td>4</td>
<td>cf3fa4b1f1bdb60c</td>
</tr>
<tr>
<td>Bishop</td>
<td>a8</td>
<td>6</td>
<td>5</td>
<td>83c3fd4a7d787936</td>
</tr>
<tr>
<td>Bishop</td>
<td>b8</td>
<td>5</td>
<td>4</td>
<td>f317ee03f569a587</td>
</tr>
<tr>
<td>Bishop</td>
<td>g8</td>
<td>5</td>
<td>4</td>
<td>9ad97f53b94894e3</td>
</tr>
<tr>
<td>Bishop</td>
<td>h8</td>
<td>6</td>
<td>5</td>
<td>91fff9fd4502052f</td>
</tr>
</tbody></table>
<div>
<br />
If you are interested in the code for the above, drop me a mail. I will send it to you and put it on here if enough people bug me. I will continue the search and keep this table updated.
</div>
Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com7tag:blogger.com,1999:blog-7144957120901661042.post-32787671457517490912013-03-14T08:46:00.000+02:002013-03-15T07:56:23.302+02:00FEN StringsI've made some progress yesterday. I have an elementary bitboard representation working and I can set and get the chess board using a FEN string. A FEN String essentially represents the current board setup in a convenient notation. Here is an example after white's initial e4:<br />
<br />
rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1<br />
<br />
Each string in between the slashes represents a rank in the chessboard, starting from the 8th rank. Lower case is black, upper case is white. Numbers represents empty squares between pieces. For example '4P3' represents four empty squares, followed by a pawn, followed by three more empty squares, totaling eight. The '/8/' therefore means (you've guessed it!) a complete empty rank.<br />
<br />
The remaining string 'b KQkq e3 0 1' represents the side to move, the castling rights (e.g. 'K' means white can caste king-side, 'q' that black can caste queen-side, etc.), en-passant square and the move counters. The en-passant square is the square directly behind the pawn that made the two-square move. In this case, white move e4, which means that e3 is the en-passant square. Black can capture the pawn if he had a pawn on either d4 or f4. Regardless, the en-passant square is always indicated, whether it can be taken or not. The move counts are the half-moves since a last capture or pawn move (for the 50-move draw rule), followed by the number of full moves.<br />
<br />
I found myself constantly checking the validity of the FEN string during the parsing stage, which started to look really ugly. So I turned to one of my best friends... regular expressions!<br />
<br />
Regular expressions can get tricky...quickly, but is incredibly powerful to recognise patterns in strings. Here is a short extract from Vicki that shows how a FEN string can be checked:<br />
<br />
<script src="https://gist.github.com/jacovanniekerk/5159299.js"></script>
<br />
The 'verifyRank()' method simply verifies that the a rank adds up to eight. Doing that in a regular expression may get very hairy (actually I don't think it can be done). The code also verifies that there are 2 kings at least. Of course, that can easily be done by the regular expression, but the string will get rather long. Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com0tag:blogger.com,1999:blog-7144957120901661042.post-64308130137508549502013-03-12T12:51:00.001+02:002013-03-15T07:56:54.981+02:00Move generationThe first step is move generation. I have committed myself to Java and bitboards for Vicki 2.0. The advantage of Java is that it is much more platform independent than C... well, mostly. Bitboards is also a good move, given that it is theoretically faster than the postbox method and besides, it is something interesting to learn.<br />
<br />
So the list of tasks for the next few days is as follows:<br />
<br />
<br />
<table style="width: 660px;">
<tbody>
<tr> <td>1.</td> <td>Set up data structures </td> <td>Done </td> </tr>
<tr> <td>2.</td> <td>Set and get board (FEN-based) </td> <td>Done </td> </tr>
<tr> <td>3.</td> <td>Simple textual display </td> <td>Done </td> </tr>
<tr> <td>4.</td> <td>Move generation for non-sliders (pawns, knights and kings) </td> <td>In progress... </td> </tr>
<tr> <td>5.</td> <td>Move generation for sliders (bishops, rooks and queens) </td> <td>Pending </td> </tr>
<tr> <td>6.</td> <td>Make move </td> <td>Pending </td> </tr>
<tr> <td>7.</td> <td>Unmake move </td> <td>Pending </td> </tr>
<tr> <td>8.</td> <td>Perft testing </td> <td>Pending </td> </tr>
</tbody></table>
<br />
For now, the representation simply contains positions for each of the pieces. The derived pieces will be added later.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com1tag:blogger.com,1999:blog-7144957120901661042.post-54053424966596910012013-03-06T10:43:00.001+02:002013-03-12T12:53:18.128+02:00Something stirring in the shadows...I have only fond memories of Vicki... The website is still up, but Vicki has not used a clock cycle in years. The current release is several years old... written in C.<br />
<br />
I am currently (as in already busy) rewriting Vicki. Vicki 2.0 is a complete rewrite of the engine, reusing nothing but the name.<br />
<br />
I am not looking at any existing computer chess code and I am avoiding any heavy bias to single papers and single units of theory - trying my own. The research in computer chess is all but exhausted. So all
that is left is to redesign the wheel for the fun of it and looking at existing code will spoil it for me... Vicki is not meant to "extend" the envelope of computer chess. It's my Everest and South Pole. <br />
<br />
Vicki 2.0 is being written in Java. Java's speed is comparable to C and C++ (in some people's opinions!) Also, I want something which is easily transferable between Linux and Windows platforms. C does not really cut it for me any more.<br />
<br />
Board representation will the elusive bitboard (or bitmap) technique. It cannot be that hard... (famous last words!) and I cannot ignore it's advantages any longer.<br />
<br />
I hope to post regularly and have something on the <a href="http://www.vicki.co.za/">main website</a> up and running soon.<br />
<br />Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com0tag:blogger.com,1999:blog-7144957120901661042.post-19429359159891747892011-07-09T09:08:00.000+02:002011-07-09T09:08:02.368+02:00Ping...I've not posted for over a year. Although I have not had much time to work in Vicki, the engine is definitely not dead.<br />
<br />
I will start with a rewrite in the foreseeable future. I am not yet sure which direction I'd like to take with Vicki - but I am toying with the following:<br />
<ol><li>Possibly rewriting the engine in Java. The speed difference between Java and C is negligible, when the number of objects used are limited. Java also has better testing frameworks (well, from what I could find) and is platform independent. I can also throw in my own GUI, if I like.</li>
<li>General improvement on absolutely everything from move generation write through to opening/ending databases.</li>
<li>Multi-threaded searching for multi-core systems. I have access to some serious hardware at work (i.e. 64Gb RAM with 8 quad core processors). Would be interesting to use of of those for a tournament!</li>
<li>I would like to finally get learning right!</li>
<li>Full-time up server playing on servers.</li>
</ol>Watch this space!Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com1tag:blogger.com,1999:blog-7144957120901661042.post-17948452576781072062010-01-06T11:44:00.000+02:002010-01-06T11:45:28.308+02:00DelaysSeems like I'm going to need a few more days. I've manged to split the move generation so that I now incrementally generate moves and search them (as appose to generate all the moves at once). This seems to be paying off. However, I'm having some transposition table problems again!<br /><br />I'm hoping for end January.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com0tag:blogger.com,1999:blog-7144957120901661042.post-4317084504300619492009-12-30T08:33:00.000+02:002009-12-30T11:05:54.681+02:00Resurrected? ...or just out of the coma?I guess life happened while I was busy working on my chess engine. I few months ago, I dumped the entire engine and started fresh. Then after a month or so, I dumped that idea and went back to the original codebase. I started integrating the sections of code that I rewrote and improved. To be frank, large sections of code in current release of Vicki is a terrible mess and these needed to be rewritten. I'm almost done with that.<br /> <br />I have already rewritten the move generation, which resulted in a speed increase of around 10%. I’ve also changed the representation of the move (I use a 32 bit integer for this) so that a full 8 bits are available for move ordering (this use to be 6). This change will greatly enhance the move ordering capabilities of Vicki.<br /><br />I am now working on the actual search function and the transposition table. Apart from fixing a nasty bug with the transposition table (it returns a mate score, but just chases the king around with trivial end game positions), I also need to rethink all the pruning and speed-up techniques individually. I threw all these together without giving any much thought. I paid the price.<br /><br />I'm also planning pondering, opening book learning and better interface support.<br /><br />The next release is scheduled for the 4th of January 2010.<br /><br />Vicki is back... and smelling blood!Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com1tag:blogger.com,1999:blog-7144957120901661042.post-49781570262430698792008-03-06T08:21:00.002+02:002008-03-06T08:24:55.944+02:00FrustrationEven though I haven't posted in a while - Vicki is not dead. I'm having huge issues with Vicki at the moment which is taking up a great deal of time. The biggest problem at the moment is the transposition tables that are not working as it should. Every time I implement it, the engine plays weaker...substantially weaker. This can only be as the result of a bug. I hope to have this sorted out in the next week or so...<br /><br />The transposition table is a very important component and I want that working first, before spending any more time with move ordering and evaluation as these elements share some common groundJaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com8tag:blogger.com,1999:blog-7144957120901661042.post-44723057146249849942007-11-19T07:50:00.000+02:002007-11-19T19:58:20.443+02:00Refactoing & revisitingThere are few things as annoying as a dormant blog - and here I am doing the exact same thing. I've recently revisit Vicki and I am in the process of refactoring the engine. I have found some bugs with the repetition detection and I am spending some time to get the engine stable. Once this is complete, I'll start working in getting the engine up to scratch. <br /><br />One element that has been missing from Vicki is decent testing. For the time being I've identified 28 engines, ranging from weak to rather strong. The idea is to put Vicki in a gantlet against them and work with the final score as an indication of strength (2 rounds, from the starting position). Later on I'll try the test suites again.<br /><br />Let see how it goes...Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com2tag:blogger.com,1999:blog-7144957120901661042.post-32387342072562388692007-09-03T06:22:00.000+02:002007-09-03T18:25:25.161+02:00New Vicki almost ready...I've been promising a new release for some time now... Fortunately, my thesis was accepted with little change and I can now focus that attention on my chess engine too. Vicki has been a bit a of a disappointment and I am working hard on getting her ready for WBEC Ridderkerk's 15th edition. Hopefully we'll see an engine around 2100 in stength :-)Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com1tag:blogger.com,1999:blog-7144957120901661042.post-81548532033948463022007-08-16T11:12:00.000+02:002007-08-16T23:15:33.258+02:00Time-off...Hi all<br /><br />I need to take some time off from Vicki for a few weeks or so. My thesis has just arrived back from the moderators and I have some minor changes to make before I hand it in on the 24th of August... then there is also a research paper that needs to be submitted before the end of this month. Then apart from that, I also have to work to pay for everything...<br /><br />So, Vicki will have to wait a while...<br /><br />Sorry guys :-(Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com1tag:blogger.com,1999:blog-7144957120901661042.post-24209009849587339182007-08-03T01:05:00.000+02:002007-08-03T01:11:07.383+02:00Null movesI finally got null moves to work in Vicki. I had some trouble with the capturing of the king (which caused Vicki to hang), but I eventually got it fixed. I am utterly amazed at the effect of null moves in the engine. With null moves Vicki searches (on average) 1-2 plies deeper and even more later in the game. In late-middle games, depths of 12 plies are reached! That is without any other form of pruning or transposition tables. The new version of Vicki is already playing on FICS and I am conducting tests against the older version to evaluate the improvement. <br /><br />Why didn't I have this ready for the WRCC?Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com7tag:blogger.com,1999:blog-7144957120901661042.post-30595339486901496012007-07-31T08:28:00.000+02:002007-07-31T08:44:38.149+02:00Test cases and transposition tables!The test cases was a great idea and it paid off! I detected a problem with the Zobrist keys in that en-passant was not correctly added/removed. I also detected a nasty (and embarrassing) castling bug. I omitted the <span style="font-style: italic;">break</span>-statement after each <span style="font-style: italic;">case-</span>statement when verifying that the castling was valid. This means that if white wants to castle king-side, queen side castling must not move through check and white must not prevent black to castling either side, either! A very silly bug! I only detected it after adding a large series of perft checks to my test cases. By squashing this bug, my engine plays much better chess already!<br /><br />Transposition tables is turning out to be very annoying! I keep on getting them "working" only to find that in a duel (100 games, 3 minutes per side, different starting positions) with the previous version that is does badly... or at best, just as good. Shouldn't transposition tables increase the ELO with 200+ points? As a result I've put this on ice for awhile. <br /><br />In the WRCC tournament, my engine lost a particular game by means of a long capturing sequence that ended in a check. As checks are not part of the quiescence search, my engine never saw the pending disaster. I am thinking of ways to incorporate checks into the quiescence search without slowing things down too much. But how?<br /><br />I'm also going to attempt to incorporate null moves into the engine. After reading up on the concept a few months ago I was most intrigued with the concept and it would be interesting to see what effect it will have on my engine.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com1tag:blogger.com,1999:blog-7144957120901661042.post-75228403551808771472007-07-26T06:39:00.000+02:002007-07-26T18:48:25.699+02:00Vicki playing onlineI've just checked on Vicki playing online at FICS. The engine is doing pretty well...actually too well. Vicki has a rating of over 2000 for standard and lightning play and 1897 for blitz (see my website for more exact figures - or better yet - log onto FICS and pay Vicki a visit. She plays under the "myvicki" handle). <br /><br />I've shifted my approach when working on the code. Instead of hacking away and trying to squeeze a few ELO points in between work, family and social life (actually work and family only - sadly this blog is pretty much the limits of my social life :-(), I want to set definite milestones for the engine. The first important change is test cases. I've devoted an entire c-source file for test cases, which I'll run periodically to ensure that I did not break something while adding some nifty new feature. My "hacking"-approach is what cost me to play without a transposition table in last weekend's tournament. This needs to end...Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com3tag:blogger.com,1999:blog-7144957120901661042.post-52518233515249268792007-07-25T11:47:00.000+02:002007-07-25T23:54:40.955+02:00Vicki tasted blood!It is with great pride that I announce that Vicki is now playing on the Free Internet Chess Server (FICS) under the handle of "myvicki". Please pay her a visit! After all the fun of the WCRCC I am very motivated in getting Vicki to play decent chess!<br /><br />Vicki is also competing in <a href="http://loirechecs.chez-alice.fr/chesswar/">ChessWars XI</a> under the promotion section. So far Vicki is not doing that bad, having drawn the first game. It would be interesting to see how she does later on.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com0tag:blogger.com,1999:blog-7144957120901661042.post-30628561481342905412007-07-22T09:34:00.000+02:002007-07-22T21:42:30.416+02:00Final standings...The tournament was very exciting and Vicki actually won one game and drew another. For an engine that's missing serious components, I am quite surprised. However, I can't wait for the next tournament to start so that I can amaze a few people... grrr... :-)<br /><br />Mediocre (blog <a href="http://mediocrechess.blogspot.com">here</a>) did particularly well - the name really does not suit it well. It is far from being Mediocre and to think it is all written in Java! Well done to Jonatan Peterson. He's a real inspiration!<br /><br />Just for fun, here is the game that Vicki won (my little engine was playing black). I hope to have many of these soon!!<br /><iframe src=http://chess.maribelajar.com/chesspublisher/viewgame.php?id=1185133116 width=300 height=380 frameborder=0></iframe><br>Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com0tag:blogger.com,1999:blog-7144957120901661042.post-60102694438874199752007-07-21T00:25:00.000+02:002007-07-21T00:32:08.421+02:00Official tournament!Hi all...<br /><br />I haver entered Vicki into the <a href="http://www.taccl.org/2007Presidents.html">"The 2007 Second Annual ACCA President's Tournament & 2007 World Computer Rapid Chess Championships"</a>. So far, 40 engines have entered and I fear them all! Although this will be a good exposure for Vicki.<br /><br />I am having difficulties with the transposition table and it seems that Vicki may be the only engine participating without a transposition table at all. At least the improved move ordering is allowing fairly deep tree searches. Also the evaluation function has been improved somewhat and bug fixes have been made. I'll add this version of Vicki to the website soon. <br /><br />I know Vicki will be obliterated in this tournament - but if I can only get one draw, I'll be very happy :-)<br /><br />Hold thumbs!Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com2tag:blogger.com,1999:blog-7144957120901661042.post-5759476980717512032007-07-03T06:12:00.000+02:002007-07-03T18:19:11.225+02:00Hello? Someone there?Not a single post in June does not mean that I have not been busy! I have the new version of Vicki almost ready. Only a few more tweaks before release. My focus has been on the static evaluation code which was rather poor up till now. I separated the evaluation function into 3 sets, depending on opening, middle or endgame.<br /><br />The <strong>transposition table</strong> is working... but I did expect a bit more... at least it is working. A few nasty bugs are still lurking in the code during draws which I still need to resolve.<br /><br />I am also implementing better <strong>time control </strong>and rewriting the <strong>winboard section </strong>so that Vicki claims draws and end the game after losing/winning. <br /><br />I'm also running tournaments to measure the development of the engine. This can be viewed at <a href="http://www.vicki.co.za/test.html">http://www.vicki.co.za/test.html</a> and is updated real-time.<br /><br />If only I had more time!Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com4tag:blogger.com,1999:blog-7144957120901661042.post-67702572112720505662007-05-25T08:05:00.000+02:002007-05-25T08:21:46.862+02:00Transposition tables and tidying up.I realised this morning that it has been quite a while since my last posting. I am currently working on a number of things in Vicki and my guess is that release 0.04a would be significantly stronger than the previous versions. I am somewhat reluctant to drop the alpha qualifier, but perhaps I will in the next release (version 0.05beta).<br /><br />I currently have a structure called CHESSENGINE that I pass around (or the pointer to it) between functions. I realised that this parameter-passing may actually degrade performance, cause problems because of its size (I’m not completely sure, but isn’t there a limit of 64k on a "struct"s – even on modern operating systems?) and waste quite a few clock cycles to find the data element within this structure. Regardless, all I gain from this is the ability to have multiple engines in the same process as its state is completely described by this one chunk of data. I’m moving away from this and dumping everything as global variables and structures in a header file. Who wants multiple engines (of the same kind and strength) in the same process anyway?<br /><br />I am also implementing an elementary<strong> transposition table</strong> and cleaning up the code as I go. At the moment I am having problems getting it to work, but I’m sure it is just a case of a silly bug lurking somewhere. Once this are done, Vicki will not be such a pushover anymore! ;-)<br /><br />I’ll keep you all posted...Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com6tag:blogger.com,1999:blog-7144957120901661042.post-10368698577775330812007-05-15T08:39:00.000+02:002007-05-15T08:44:53.136+02:00Testing 1, 2, 3,..., 99282111917764I am currently experimenting with killer-moves, splitting of the evaluation function (opening, middle and end-game), aspiration windows and all kinds of small tricks. For now, I'm leaving transposition tables for later. The idea is to optimise this part of the engine so that the impact of transposition tables will be maximum.<br /><br />I'm running tournaments on my computer and I wrote a little Java application to upload the file to my FTP account every now and again. The current tourney is between 9 engines, 15 minutes a side and 2 rounds. For up-to-date, semi-real time updates, <a href="http://www.vicki.co.za/test.html">visit the test page</a>.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com4tag:blogger.com,1999:blog-7144957120901661042.post-67032881322982217742007-05-08T11:19:00.000+02:002007-05-08T23:36:29.876+02:00Re-engineering...OK, I realised that this early exit strategy (in SEE) of mine is actually pretty dumb. I replaced it with a very elementary minimax search to evaluate the entire capture sequence for both sides. The results were rather good. I search on average a ply deeper with only SEE in quiescence search (no ordering in the alpha-beta). By adding the improved move ordering in alpha-beta as well I get another ply deeper with longer time controls.<br /><br />Although Vicki is no push-over any more, a significant amount of work still lies ahead. In order of implementation this is:<br /><ol><li>A long, hard look at the evaluation function of end-games. Vicki struggles with KQ vs. K (never mind KR vs. K).</li><li>Move ordering within alpha-beta can still be improved.</li><li>Killer-moves, history heuristics and null moves (I may implement transposition tables before null moves though).</li><li>Transposition tables.</li><li>Hash tables (evaluation, pawns, etc.).</li><li>Opening books (adaptive?) and perhaps even end-game databases.<br /></li><li>Pondering.<br /></li><li>Learning.</li><li>Factor X.</li></ol>Factor X is basically that element in Vicki that makes it unique. I don't think I'll be happy with "just-another-chess-engine.". What is factor X? I don't have any idea...(yet!)<br /><br />Version 0.031alpha an now be downloaded at <a href="http://www.vicki.co.za">Vicki's home</a>.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com5tag:blogger.com,1999:blog-7144957120901661042.post-23581361907480027712007-05-02T08:18:00.000+02:002007-05-02T08:43:00.302+02:00Move orderingIf there is one thing in chess programming that cannot be overstressed then it is coffee. Without coffee all is lost... No really, the difference move ordering can have to an engine cannot be overstated. After resolving a few nasty bugs, Vicki now boasts the following move ordering:<br /><br /><ol><li>The previous PV of iterative deepening is feed back into the search. This is been implemented for a while, but I fixed a bug here which caused the engine to hang. A slight difference is that the entire PV line is used, even if a better line is found the previous line is still investigated first. I was quite amazed by the speedup gained from this.</li><li>Quiescence search now uses a Static Exchange Evaluation (SEE), which turned out far easier than I thought and to my surprise, caused a fair amount of speedup. The SEE I use also uses an early exit technique. Say for example, I have a pawn and queen attacking a bishop, while my opponent has two pawns protecting the bishop. The full SEE evaluation will result in a negative value: 3-1+1-9+1=-5 (I gain a bishop and a pawn for a queen and a pawn). With early exit I only realize that I can stop after capturing the knight, resulting in +2. A great move!</li></ol>Vicki is playing a good game of chess already and I find it difficult to beat the engine with tight time controls (3 mins/less), but still beat the engine 80% of the time if I allow myself ample wetware processing time! ;)<br /><br />I am now concentrating my efforts on the ordering of normals moves as part of alpha-beta (in conjunction with the PV-value). So far the results are very promising, but it still needs some work before being released.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com5tag:blogger.com,1999:blog-7144957120901661042.post-7531758991167916482007-04-24T10:06:00.000+02:002007-04-24T10:52:39.145+02:00Vicki is crawling now...Vicki is now out there, but I am not very happy with her performance. It plays terrible chess and the positional play is especially weak. Fortunately, there is still a great deal that I can do. I have started adding to the chess knowledge by tweaking and improving the static evaluation function to get a base to work from. The following is now considered:<br /><ul><li>Pieces on the board, P=100cp; R=495cp; N=280; B=290cp; Q=895cp (a bit less than the accepted values to encourage positional play).</li><li>The pawns positions on the board, giving a small bonus to pawns that have advanced further up the board.</li><li>Bonus for passed pawns; penalty for doubled & isolated pawns.</li><li>Knight position bonus (controlling central squares).</li><li>Mobility bonus (1 centipawn for each move), excluding the king.</li><li>Bonus for castling capability (retains bonus once castled).</li></ul><p>I estimate Vicki at about 1100, having played against rated engines (she even won a few!). Some serious things are still missing and are next on my todo list:</p><ul><li>Vicki does no move ordering whatsoever. I have a few ideas that I would like to implement, including SEE, sorting by the principal variation returned by the iterative deepening search (yes, all previous iterations are wasted!) and finally, a variation of killer moves.</li><li>Transposition table (Zobrist keys are working).</li></ul><p>On a positive note, Vicki had an interesting game against Mediocre, where it was way behind in material and tried to sacrifice a rook (by attacking Mediocre's rook) to force a stale-mate. I was rather impressed by the strategy (which I first thought was a bug!) However, Mediocre is no pushover engine and didn’t fall for that trick and simply moved its rook away! Vicki was mated a few moves later, but at least the draw-detection is working well.</p>Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com5tag:blogger.com,1999:blog-7144957120901661042.post-409098562677328412007-04-22T08:08:00.000+02:002007-04-24T11:51:53.257+02:00First releaseI finally have the first release of Vicki available. It is less than a skeleton of a chess engine and I am rather reluctant to release it, but decided to do so anyway. From the few games I've played against Vicki, I estimate an ELO of around 900, if that much. <br /><br />I have removed the move ordering as it is not contributing to the engine (slow implementation) and will re-engineer this at a later stage.<br /><br />Vicki also has a permanent home now, where I'll add the downloads and progress. Let me know what you think. Oh, yes, Vicki's home is <a href="http://www.vicki.co.za">www.vicki.co.za</a>.Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com4tag:blogger.com,1999:blog-7144957120901661042.post-35734315061399923202007-04-18T08:35:00.000+02:002007-04-24T11:48:46.856+02:00Basic engine...I wish I were still a student... my time is so limited! Vicki is making good progress under the current time constraints. So what do I have:<br /><ul><li>I have a decent move generator that can generate moves pretty fast using the 12x12 representation technique. I can also generate captures only.</li><li>Alpha-beta search.</li><li>Quiescence search, with MVV/LVA move ordering. Currently, I'm not pruning any of the moves and merely orders them by the MVV/LVA scheme.</li><li>Horrible evaluation function. </li><li>Separate input thread that takes minimum amount of processor time. </li><li>A minimal WinBoard interface (but without any time management).</li></ul>This is a good start. I must say the the quiescence search makes a huge difference to the engine and I do not think an engine can be successful without it. Despite the fact that Vicki is very limited in knowledge, it doesn't play as bad as I thought. I estimate the ELO to be around 800. which is a bit better than a human that has just learned how to play chess!<br /><br />Before releasing the first version of Vicki (version 0.1 beta), I need to implement the following first:<br /><ul><li>Do away with MVV/LVA and implement SEE. I have an idea which I would like to try out before reading to much on how other people do it. I basically "count" attackers and defenders on a square AS PART of the move generation. Once I have the idea well defined and tried on paper, I may divulge some information on it... :)</li><li>Implement some move ordering in the alpha-beta search using table lookups.</li><li>Implement the standard iterative deepening and re-use its results in the move ordering.</li><li>Add some time management!</li></ul>But now I'm so-o late for work :)Jaco van Niekerkhttp://www.blogger.com/profile/05438999119366217740noreply@blogger.com0