Pondering and Analysis

chess4j can now ponder! If you’re not familiar with that term, it means that the program will make use of the time the opponent is on move. It does this by predicting the move the opponent will make, and thinking about what its response will be.

Let’s say that the program would spend X seconds formulating its response. The opponent makes its move in Y seconds, and it makes the predicted move. If X <= Y, the program can move instantly. If X > Y, then the program only needs to spend X-Y more seconds. If, however, the program did not correctly predict the opponent’s move, it will need to throw out the work and start over.

There are other ways to implement pondering. One variation is for the engine to start thinking about what it would do if it were the opponent. The idea is that when the opponent does move, the hash tables will be full of good information that should make the search move along very quickly. It’s hard to see how this can be more effective than the “guess” approach though, assuming the prediction rate is fairly good. A 50% prediction rate is completely reasonable. That’s a lot of the opponent time being utilized by the engine.

So how many ELO is pondering worth? Conventional wisdom is that a doubling of speed is worth around 70 ELO, so that should serve as an upper bound (effectively using 100% of the opponent’s time would conceptually be equivalent to a doubling of time). If we effectively use about 50% of the opponent’s time, I would expect a 30-40 ELO boost.

I ran some tests, chess4j with pondering vs without pondering. This was mainly a stability test; I wouldn’t put too much stock in the results as the prediction rate against itself will obviously be a lot higher than it would against another opponent. Still, the results are interesting.

With PonderingWithout PonderingDrawRate
10106513390.670

Clearly pondering is a big advantage.

Analysis mode is also supported now, meaning it’s possible to analyze games or just try different moves to see the engine’s “opinion” of each. Make a move, let the engine think for a while, back up and try another move, etc.

One final note: Pondering and Analysis mode are not supported in Prophet directly, but they are supported by chess4j when using Prophet. This highlights the benefit of the JNI integration – keep the native engine “lean and clean” and implement the ancillary functions in the high level language.

Now, onto a quiescence search.

Posted in chess4j, Computer Chess | Comments Off on Pondering and Analysis

chess4j + Prophet4 rewrite status 6/14/20

Support for time controls has been added to both Prophet and chess4j. Each is capable of playing with a fixed time per move or incremental chess clocks. They can use conventional chess clocks as well, but the timing strategy doesn’t really take into account that time will be added after the time control is up (for example 40 minutes for the first 40 moves, then 5 more minutes for each 10 moves, etc.).

Another addition that was tricky to get right was the JNI support to print changes in the principal variation during a search. I ended up adding a callback function that is invoked from the search when the PV changes at the root. When using P4 as a standalone engine, that callback would be a simple “print PV” function. When invoking the P4 search from chess4j, the callback is a method in the JNI layer that calls a similar “print PV” function in the Java code. It was tricky, but works beautifully.

I mentioned in my last post that I was kicking off some self play matches in P4 using 10 second matches with 0.5 second increments. This did uncover a couple of bugs, but everything is stable now. Unlike fixed depth matches where you would expect an exact .500 result, the timed matches will introduce a small amount of variability as the system becomes “busy” at times which will cause the search to stop at different points. So, the result of a 4000 game match was close to but not exactly 0.500.

Just out of curiosity I also played a 2000 game match of P4 vs P3. There was absolutely no doubt that P3 should win this match hands down. P4 is missing many search algorithms that are worth lots of ELO. I just wanted to test for stability and get a baseline measurement to gauge future improvements against. The result – 5 – 1959 – 36! Clearly a long way to go, but search improvements are coming soon.

Next up: analysis support, ponder support in chess4j, and a Windows build of the chess4j + P4 bundle. Once those features are complete, it will be time to start re-adding those search enhancements to climb the ELO ladder. Can’t wait.

Posted in chess4j, Computer Chess, Prophet | Comments Off on chess4j + Prophet4 rewrite status 6/14/20

Prophet4 rewrite status 5/31/20

The last couple of weeks have been focused on transitioning P4 from a single threaded engine that plays to a fixed search depth to a multi-threaded engine that can respond to commands while searching, and can search for a fixed period of time.

As soon as the code to use threads for searching was complete, I immediately pulled out an old laptop, got everything up to date, and turned it loose on doing a series of fixed depth self play matches using the fantastic Cute Chess: https://github.com/cutechess/cutechess .

The first test was to run depth 1 vs depth 1, then 2 vs 2, up to 5 vs 5. Each match was 20,000 games using over 1000 starting positions. The results are below. The score itself isn’t interesting, only that the end result was a perfect .500 in each case, and that there were no crashes, stalls, etc.

DepthWinsLossesDrawsScore
122552255154900.500
27147714757060.500
38913891321740.500
47804780443920.500
59123912317540.500

100,000 self play games (actually 200,000 if you consider that the program played both sides) is a pretty good indication that it’s stable, but just out of curiosity I also played some fixed depth self play matches where one side was able to search deeper than the other. Naturally you would expect the side that can “see further” to have a large advantage, and indeed that is the case. The table below shows the results of a series of 20,000 game matches.

12345
10.50.0120.001
20.9880.50.0380.045
30.9990.9620.50.10.029
40.9550.90.50.095
50.9720.9050.5

As you can see, even a 1 ply advantage is enormous, at least at very shallow depths. I believe that advantage would diminish at larger depths, but our branching factor isn’t good enough to play any longer games without it taking forever. Anyway, the point of this exercise wasn’t really to quantify the advantage of a larger search depth, but to test P4’s stability, and I’m happy to report it’s rock solid. P4 has played around 1 million fixed depth games at this point with 0 crashes.

I’m starting another round of testing now, using incremental clocks – 10 seconds per side with 0.5 second increment. I don’t expect any stability issues but I’d like to see that the engine never runs out of time (or at least very, very rarely).

Posted in Computer Chess, Prophet | Comments Off on Prophet4 rewrite status 5/31/20

chess4j + Prophet integration status 5/17/20

Several months ago I wrote about a proof-of-concept JNI integration between chess4j and Prophet4. At the time I had managed to compile Prophet4 as a static library, load that library into chess4j and write a JNI layer. The only function the Prophet4 library was serving at the time was for endpoint evaluation, but it was enough to show the idea was viable. Based on the success of the proof-of-concept, I’ve decided to go “all in” with this chess4j + Prophet4 integration. And, it’s going really well.

Since the time I wrote that article, I’ve added a search function to Prophet4 with some basic heuristics, as well as an iterative deepening driver. I’ve also added some additional JNI layer code that allows chess4j to utilize Prophet’s search. The native code runs 2-3x faster, so there is a tremendous speed improvement.

I’ve also realized some benefits when it comes to testing. Just to be able to compare apples to apples, I’ve stripped a lot of chess4j code out to simplify the search to the exact equivalent of Prophet’s. It didn’t really bother me too much to do that, because I wanted to refactor it to improve the test coverage anyway. Now, I’m building both programs back up, feature by feature. I’ve found that it’s often easier to build more comprehensive tests in Java, largely due to the ease of “injecting” mocked dependencies. As a feature is implemented in chess4j and I’m satisfied with the testing, I’ll implement the same feature in Prophet4. I still add tests in P4, using Google’s test framework, but not always as comprehensive. Then, the JNI layer is leveraged to ensure that the searches traverse exactly the same tree, produce the same score, and that the iterative deepening driver produces exactly the same PV. Proving that the searches are equivalent gives a sort of transitivity argument.

So, chess4j and Prophet4 are now and probably forever linked. In some sense you could consider chess4j a Java port of Prophet4, or Prophet4 a C port of chess4j. But, there’s more to it than that. The programs serve different purposes. chess4j will be the more “feature complete” engine. It contains an opening book, where P4 does not. It will be capable of pondering, but P4 may not. Prophet4 will be the lighter weight / faster of the two and more suitable for testers that focus on engine-to-engine testing. The chess4j releases will include platform specific builds that utilize P4 as a static library, and for any platforms that aren’t included, the Java engine will still work.

For future work I’m envisioning an SMP implementation such as Young Brothers Wait in P4. P4 is the more likely to use tablebases. Since chess4j uses P4 as a static library, it will automatically benefit from those features. Macro level work such as distributed computing and learning experiments are more likely to be done in chess4j. Who knows, but for now I’m having fun. I guess that’s the main benefit.

Posted in chess4j, Computer Chess, Prophet | Tagged , | Comments Off on chess4j + Prophet integration status 5/17/20

Prophet4 rewrite status 3/24/20

Killer moves have been implemented. Two killer moves are kept per ply. A killer move is defined as a non-capturing move that causes a fail high. A new killer move is stored in “slot 1,” while the previous killer move in slot 1 is shifted to slot 2. Killer moves are tried after capturing moves, before any other non-capturing moves are even generated.

The next item on the agenda is to add draw checks into the search, then iterative deepening and “last PV” move ordering.

Posted in Computer Chess, Prophet | Comments Off on Prophet4 rewrite status 3/24/20

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