Prophet4 rewrite status 2/16/20

Added a simple depth first search. The search uses the alpha/beta algorithm and recognizes checkmated and stalemated positions but otherwise has no “intelligence.” It is a simple fixed depth search without iterative deepening or timing.

The next phase of work will be to add some basic move ordering, such as trying the previous PV first, MVV/LVA capture scoring and killer moves.

The JNI integration with chess4j has gone extremely well. chess4j is capable of using Prophet for search, so after this rewrite is complete there will likely be a chess4j bundle that includes P4 for some platforms. I am leaning towards keeping P4 as a lightweight, XBoard compatible “calculation engine” and leveraging chess4j for ancillary functions such as opening book, pondering support, and distributed computing support.

Posted in chess4j, Computer Chess, Prophet | Comments Off on Prophet4 rewrite status 2/16/20

chess4j + Prophet4 POC

I just wrapped up a successful proof-of-concept to marry up my two chess engines – the Java based chess4j and the C based Prophet4 . Note, Prophet4 isn’t even a complete engine yet – it doesn’t even have a search! The idea for the POC was to see what it would look like for chess4j to load Prophet4 as a static library and call down into the native code for endpoint evaluation. It has worked out fairly well. The “bridge” is the Java Native Interface (JNI).

Why would I want to do this? Well, there are advantages and disadvantages to writing a chess engine in a high level language like Java. (I know C is technically a high level language too, but it’s much closer to the hardware than Java.) It is certainly easier to quickly write and test new code in Java (well, to me it is). It is easier to maintain – the refactoring support in IntelliJ is fantastic. There are almost limitless open source libraries available for things like opening books and even machine learning. There are high level abstractions to support functional programming and parallel processing. In short, programming in a higher level language is just more productive. The major disadvantages are that they tend to run slower and are less memory efficient. Can we have the best of both worlds?

I can envision writing the core functionality in native code for speed of execution, but implementing the engine itself with all the bells and whistles in Java. The protocol code, opening book, search iterator, pondering code and distributed (multi-machine) search could be implemented at a high level. When it’s time to execute a search, drop down to native code. The search in the native code could efficiently use multiple processors.

In this POC, calling the Prophet4 library to do the endpoint evaluation slowed the engine down by more than 50%. That’s not unexpected though. There is an overhead to “crossing the bridge.” Evaluating a single endpoint is simply too granular a unit-of-work to overcome that overhead. I’m sure that when the C code is called to perform a search, there will be a tremendous speedup.

One major drawback to this entire idea is that it flies in the face of one of the main benefits of Java, which is machine independence. By relying on native code, you are once again tied to a specific architecture. That means platform-specific build artifacts: Linux, Windows, Mac, for both 32 bit/64 bit if desired. This being a personal project, I’m not terribly worried about it. I could always leave a Java implementation of the search in place as a fallback if I wanted to – still deciding.

The next major task on my list is to implement a search in Prophet4. As that develops I will continue to play around with this idea. We’ll see where it goes, but so far I’m feeling pretty good about it.

Posted in chess4j, Computer Chess, Prophet | Tagged , | Comments Off on chess4j + Prophet4 POC

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 | Comments Off on Prophet4 rewrite status 9/24/19

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 | Comments Off on Another round of sparring partners for Prophet3