Prophet4 rewrite status 9/24/19

Evaluator complete. This is a verbatim “migration” of Prophet3’s evaluator. It was a little painful really, because the evaluation routines are clearly a major weakness in the program, but I think it’s important to port everything over and run some comparisons before making any changes.

I found the “random move selection” kind of fun, so a command line parameter was created to enable random mode. Just start the program with the ‘-r’ option.

The next phase of the rewrite will be the search. Before starting this phase I’m going to try a small side project. I’m going to add a JNI layer to chess4j to enable it to call native code from Prophet4. If it works out, this would have some implications for future development.

  1. It may be easier to do some testing from the Java tier where we can use proper mocks without resorting to function pointers (the indirection probably slows the native code down anyway).
  2. If it works out really well I may be less inclined to implement some things in C, such as an opening book or PGN facilities. Possibly not even pondering.
  3. I’ve had in mind to do some distributed computing work (not to be confused with parallel processing). Perhaps I could do this from the Java tier where there are more supporting libraries.
  4. What about machine learning experiments? Best done from a higher level language?

Those are just some thoughts. Since I’m not on a timeline and not getting paid to do this I have the luxury of playing around a little. 🙂

Posted in Computer Chess, Prophet | Leave a comment

Prophet4 rewrite status 8/30/19

The protocol handler is complete. Enough of the XBoard protocol has been implemented to play a complete game. Move selection is completely random. A 20,000 game match was run between identical copies of the program (which didn’t take long since it moves instantly), and as predicted the outcome was almost exactly 50%. Interestingly, 85% of the games resulted in a draw.

The next area of focus will be implementing the evaluation routine, which gives a static analysis of a position. This will be a direct port of the evaluator from Prophet3. The evaluation needs a lot of work, but forward progress will come after the rewrite is complete. Once the evaluator is in place I can make the engine just slightly smarter than a complete random mover. I’m also considering a JNI integration with chess4j, as a proof of concept for future work.

Posted in Computer Chess, Prophet | Comments Off on Prophet4 rewrite status 8/30/19

Prophet4

I’ve decided to start fresh, and completely rewrite Prophet from the ground up for the third time. The first iteration of Prophet was written around 2000. Prophet2 was started in 2007. Prophet3 was started in 2011 (see Shall we play a game?) but didn’t really get completed for several years after that. Now, in 2019, it’s time again.

There are numerous reasons I’ve decided to start over. In short though, I’ve been doing some C coding professionally lately, and when I look at the Prophet3 codebase (which was started at a time I had only done C as a hobby), well, I know I can do better.

Design Goals

  • Use pure C. Prophet3 is “nearly C” anyway. It is not an object oriented program.
  • Modularize the codebase. Group source files into directories according to functionality. E.g. movegen, eval, search, etc.
  • Break the code down into more source files that are more focused in nature.
  • Make better use of static functions.
  • Make better use of the const qualifier.
  • Improve the documentation. Each function should have at least a brief description of its purpose, a listing of arguments and return value.
  • Improve testing coverage. In general Prophet3 is well tested, but there are some areas the coverage could improve.
  • Use a proper test harness, e.g. GoogleTest or the like. The release binary should not contain the test code. Prophet3 uses assertions exclusively, and all the test code is built into the binary (even though it can’t be executed when compiled with the NDEBUG flag).
  • Make use of memory leak detectors such as Valgrind on each release.
  • Produce a static library containing the move generation, evaluation, and search related functions. It will not include the opening book related code or the Xboard protocol related code. The intent is to modularize the core functionality for inclusion in other projects.
  • Retire SQLite. It never felt like a relational database was a good fit for the opening book. Replace with a Key-Value store type database, possibly LMDB.

If you are interested in having a look or just tracking the progress, the Github repo is https://github.com/jswaff/prophet4.

Posted in Computer Chess, Prophet | Comments Off on Prophet4

chess4j 3.5 is released

I’m releasing version 3.5 of my Java based chess engine, chess4j. The only changes since 3.4 are some bugfixes to the ponder search and changes in some logging levels.

As always the source code is available on the project website on Github: https://github.com/jswaff/chess4j, or download the binary from the chess4j page.

Posted in chess4j, Computer Chess | Comments Off on chess4j 3.5 is released

Prophet3 20180811 is released

It’s been about a year since the last release of Prophet3, which was version 20170909. The main changes since then are the addition of a pawn hash table, improved Winboard compatibility, and a ponder search (*). I also added a depth preferred hash table, and tried using it in combination with an “always replace” table, but surprisingly that seemed to be slightly weaker. I plan to revisit this idea – it seems it should work.

* – A ponder search means Prophet will take advantage of the time the opponent is “on move.” Instead of idling, it assumes the opponent will make the next move in the principal continuation evaluated from the last search. If the opponent doesn’t make that move, then nothing is lost, we just start the search over. If, however, the opponent does make the predicted move, then we are already that much closer to having a response ready. In some cases, we may play an instant response. This can be a huge time saver, allowing us to allocate slightly more time-per-move to the engine.

This version isn’t much stronger without pondering, but with pondering on it gains about 40 elo vs my standard set of opponents. Here are the current test results (without pondering):

Rank Name Elo games score oppo. draws
1 plisk 0.2.7d 101 26870 62% 15 19%
2 tjchess 1.3 97 28184 62% 15 21%
3 jazz 71 31167 59% 6 19%
4 myrddin 50 34344 58% -8 19%
7 prophet3-20180811 1 25776 46% 29 24%
5 Horizon 4.4 -3 34342 50% -4 17%
6 tcb 0052 -8 34342 49% -3 19%
8 jumbo 0.4.17 -15 34502 48% -3 20%
9 madeleine 02 -59 34502 41% 1 19%
10 Beowulf 2.4a -96 22380 39% -21 18%
11 prophet 2.0 e1 -106 19180 40% -35 18%
12 matheus 2.3 -114 19180 39% -34 17%

Binaries can be downloaded from Prophet’s home page. Source code is available on Prophet’s Github repo. Enjoy!

Posted in Computer Chess, Prophet | Comments Off on Prophet3 20180811 is released

chess4j 3.4 is released

chess4j 3.4 is officially released. The main changes in this release are the hashing related changes that I discussed some time back in this post. Other than that, there are many smaller changes, many of which I’m sure I’ve lost track of, but some that come to mind are: converting to Java8 syntax, incorporating Scala in testing, and improved Winboard compatibility.

Also, the source code has been moved from SourceForge to Github. The new project website is https://github.com/jswaff/chess4j.

The next major area of work will be to parallelize the search, but I anticipate another minor release before that work begins.

Posted in chess4j, Computer Chess | Comments Off on chess4j 3.4 is released

Hashing in chess4j

Hashing is an area I’ve meant to revisit in chess4j since it was originally implemented, for a couple of reasons. (1) The hash entries consume too much space, limiting the number of entries the hash table can store, and (2) in preparation for multi-processing capabilities. I’ll address the first issue in this post, and follow up on the second at a later date.

If you don’t know what a hash table is used for, I recommend reading this article: https://chessprogramming.wikispaces.com/Hash+Table .

Up until recently the table entries in chess4j had the following structure:

TranspositionTableEntry
   long zobristKey (64 bits)
   TranspositionTableEntryType type  (32 bit reference to an Enum)
   int score (32 bits)
   int depth (32 bits)
   Move move (32 bit reference to an Object)

So how much space does a single hash entry take? It’s not very straightforward to figure it out. With C you can use the ‘sizeof’ operation, but things get more complicated with object oriented languages. But, we can make some educated guesses and do some hand waiving to get some estimates.

The zobristKey, score, and depth members are all primitive: longs are 64 bits, and ints are 32 bits each. The ‘type’ member is a reference to an enum. An assumption is that references are 32 bits, since we’re using less than 32GB of heap — though that is JVM specific. By the same logic ‘move’ is also a 32 bit reference. Therefore, the TranspositionTableEntry itself is 64 + 32 + 32 + 32 + 32 bits == 192 bits == 24 bytes. (That likely ignores some OO “overhead.”)

That is already pretty bad, but it’s not even the complete picture. Note ‘move’ is a reference to an instance of a Move object. The Move object being referenced has a cost associated with it too. That object can’t be deallocated from the heap as long as we’re referencing it. So how big is a Move?

Move
   Square from
   Square to
   Piece piece
   Piece captured (possibly null)
   Piece promotion (possibly null)
   boolean castle
   boolean epCapture

Again, it’s difficult to come up with an exact number, but we have between 3 and 5 references (2 Square and 1-3 Piece) to Singleton objects, and two booleans which are 8 bits each. So, somewhere between 14 and 22 bytes. Note that not every hash entry will have a Move associated with it: upper bounds for example, but most would.

All in all, that makes the cost of a single hash entry somewhere between 24 and 46 bytes! Doing a little more hand waiving, let’s assume an average of 38 bytes (which is probably low). That means a fully loaded hash table would have the following maximums:

RAM Entries (millions)
64 mb 1.7
128 mb 3.5
256 mb 7
512 mb 14.1
1 gb 28.3

So how can this be improved? It turns out that with a little bit twiddling it’s possible to encode the type, score, depth and move members into a single 64 bit value!

TranspositionTableEntry
   long zobristKey (64 bits)
   long val (64 bits)

Not only does that reduce the overhead of an entry from 192 bits to 128 bits (24 bytes to 16 bytes), but it completely eliminates the need to keep those Move objects on the heap! Now a fully loaded hash table has the following maximums:

RAM Entries (millions)
64 mb 4.2
128 mb 8.4
256 mb 16.8
512 mb 33.6
1 gb 67.1

That’s a fantastic improvement in terms of storage capacity. Essentially we’re trading the computational cost of doing the transformations for space. The theory is that the extra space, which allows us to store far more entries, will more than offset that computational cost. So does it work?

chess4j has a command line parameter “-hash=NNN” that can be used to set the number of hash entries. NNN must be a power of 2. I ran several tests with the old and new hash schemas. Using the Silent but Deadly test suite at 30 seconds per problem, I measured average depth achieved at various combinations of max heap space (the Java -Xmx VM argument) and max # hash entries.

Results for the old hash schema:

Heap size (-Xmx) NNN=1m NNN=2m NNN=4m NNN=8m NNN=16m NNN=32m NNN=64m NNN=128m
64m 11.31 11.34 11.03 OOM
128m 12.42 12.22 12.12 11.93 11.42 OOM
256m 12.59 12.93 13.04 12.99 12.68 12 OOM
512m 12.64 12.99 13.31 13.4 13.49 13.43 12.64 OOM
1g 12.64 13.02 13.21 13.42 13.48 13.61 13.54 13.03

OOM = “Out of Memory”. The green cells indicate the peak performance setting for that combination of heap space and # hash entries. As you can see, performance can actually decline when the number of hash entries is too large for the given heap space, even before the JVM throws an Out of Memory error.

Results for the new hash schema:

Heap size (-Xmx) NNN=1m NNN=2m NNN=4m NNN=8m NNN=16m NNN=32m NNN=64m NNN=128m
64m 12.01 11.83 11.61 10.84 OOM
128m 12.58 12.84 12.84 12.46 11.69 OOM
256m 12.68 12.93 13.26 13.43 13.31 12.36 OOM
512m 12.72 12.97 13.26 13.45 13.62 13.46 12.89 OOM
1g 12.70 13.06 13.30 13.50 13.58 13.63 13.62 13.37

So, it appears the new hash schema indeed performs better, particularly with smaller heap sizes.

It occurred to me during testing that perhaps the JVM should have been initialized with the ‘-Xms’ argument equal to ‘-Xmx’, in order to not “penalize” the program for the overhead of increasing the heap, since it will surely grow to capacity. I reasoned that, using a large initial -Xms value would likely make the larger heap sizes look even better relative to the smaller ones, but doesn’t really matter if the point of the test is to compare performance of one schema to the other, as long as all settings are consistent.

Node rate per second, hash hit rate, and hash collision rate were also measured, but were less interesting. Node rate and hash collision rate predictably decreased with successively larger tables while hash hit rate increased.

It’s worth pointing out that my experience here is similar to Jonatan Pettersson’s with Mediocre Chess. See http://mediocrechess.sourceforge.net/guides/memoryinhashtables.html

These changes will be part of the 3.4 release. For the impatient, the changes to the main hash table have already been merged into master on the project github repo.

Posted in chess4j, Computer Chess | Comments Off on Hashing in chess4j

Another round of sparring partners for Prophet3

Back in early March I added aspiration windows to Prophet with a window of 1/3 pawn, as well as some futility pruning and delta pruning. My schedule hasn’t allowed me to do a lot of work on the code since then, so I took advantage of the time to find some new sparring partners. The results are in the table below.

These games — almost 200k of them — are played at 3+0.5. That is, the clock starts at 3 seconds and 1/2 second is added after each move. That may seem like a fast game but when you’re going for quantity, it’s actually slower than I’d like. That’s about as fast as I could go on my older test system without getting a lot of time forfeits.

Rank Name Elo games score oppo. draws
1 plisk 98 25092 62% 17 18%
2 tjchess 98 32400 62% 11 21%
3 jazz 74 33286 60% 4 19%
4 myrddin 49 31082 58% -7 18%
5 Horizon 2 31080 51% -3 17%
6 tcb -5 31080 50% -2 18%
7 prophet3-20170319 -11 42068 45% 27 23%
8 jumbo -12 31240 49% -2 19%
9 madeleine -12 31240 49% -2 19%
10 Beowulf -94 24900 39% -17 19%
11 prophet2 -104 21700 39% -30 18%
12 matheus -107 21700 39% -29 18%

I’ve actually dropped Beowulf, Prophet2, and Matheus off the active list. The others should keep Prophet busy for a while.

With summer coming and other commitments starting to wind down for a while, I’ve started working again. The latest version seems to be about +10 ELO above this version.

Posted in Computer Chess, Prophet | 1 Comment

chess4j 3.2 is released and it’s magic!

I just released chess4j 3.2. This release is purely about optimizing for speed. That is, there are no changes to the search or evaluation terms.

chess4j is now a bitboard engine, and uses magic bitboards for move generation. Simply by replacing some loops over all squares with loops over (possibly sparsely populated) bitboards, and probably most importantly getting rid of some managed collections stuff, chess4j 3.2 is 4-5x faster than 3.1. In a head to head match of almost 700 games with 3.1, 3.2 scored 79% which translates into a 200-250 elo gain.

One other important difference is that the opening book is now off by default. If you want to use the opening book included with the release, you must add “-book=book.db” to the command line. (This is done in the included chess4j.bat.)

I think I can still get some more ELO just off speed optimizations and efficiency improvements (such as splitting up capture and noncapture move generation), so there will probably be one more release in the 3.x line before moving onto 4.0. The 4.x line will be focused on parallel search.

As usual you can grab the latest and greatest from the project website. Enjoy!

Posted in chess4j, Computer Chess | Comments Off on chess4j 3.2 is released and it’s magic!

Prophet’s sparring partners

Several months ago I decided to get a little more rigorous about how I test changes to Prophet. With previous versions of Prophet, I would make a change, run some test suites consisting of a few hundred or a thousand tactical positions, play a few games online to convince myself the change was good, and that was it. That doesn’t really cut it any more though. Fruit and other engines that have followed suit have shown the importance of a having a solid testing methodology that accurately measures how effective changes are. So, to that end, I found some sparring partners and took my first measurements:

Rank Name Elo games score oppo. draws
1 matheus 101 7360 67% -20 16%
2 prophet2 86 7360 64% -17 14%
3 lime 35 7360 56% -7 12%
4 gerbil -25 7360 46% 5 15%
5 prophet3-20160903 -54 8000 41% 12 17%
6 elephant -138 7360 28% 27 11%

Then Christmas happened, and I found myself with a little spare time to work on Prophet. I implemented bitboards, and then magic bitboards, and a few other speed optimizations. Suddenly it looked like I needed some new sparring partners!

Rank Name Elo games score oppo. draws
1 prophet3-20170118 91 24436 68% -42 17%
2 matheus 65 10648 58% 5 20%
3 prophet2 23 10649 51% 10 16%
4 lime -24 10649 44% 17 13%
5 gerbil -81 10643 35% 24 14%
6 elephant -191 10648 21% 39 10%

Here is what I ended up with. I like this a lot, as Prophet3 is right in the middle with some engines below and above. That seems like a pretty good cross section. As Prophet3 continues to improve, I’ll just add newer strong engines to the mix and drop the bottom ones off.

Rank Name Elo games score oppo. draws
1 myrddin 84 4811 63% -7 18%
2 tcb 46 4810 57% -4 18%
3 Horizon 30 4812 55% -2 17%
4 jumbo 19 4972 53% -2 18%
5 prophet3 7 12733 51% -2 22%
6 madeleine -26 4972 46% 4 20%
7 matheus -36 4812 44% 4 20%
8 Beowulf -67 4812 39% 7 20%
9 prophet2 -71 4812 39% 7 18%

Posted in Computer Chess, Prophet | Comments Off on Prophet’s sparring partners