After a long period of inactivity I’m happy to announce the release of version 3.0 of my Java chess program, chess4j. This version is a good bit stronger than the previous version, though still not as strong as my C/C++ program Prophet (see below). The key areas of improvement are:
- The addition of an opening book, which I discussed here.
- Improvements in the positional evaluation function
- Passed pawns are rewarded
- Isolated pawns are penalized
- Doubled pawns are penalized
- Rooks on open files or half open files are rewarded
- Rooks and queens on the 7th rank, particularly when connected to another rook or queen are rewarded
- There is some attempt to keep the king sheltered until the endgame, and then encouraged to move towards the center
- Almost 2x speed increase
The table below compares the performance of chess4j v2 against v3 on several different test suites. Each suite was run twice and the results averaged. I highlighted changes of +10% or more in green (good), and -10% or more in red (bad). The top 4 suites are tactical suites. There weren’t any significant changes here, despite the 2x speed increase. However, the ‘SBD’ suite and all the ‘STS’ suites below that are positional suites, and there were some differences there. Key areas of improvement (according to these tests) were ‘undermining’, ‘open files and diagonals’, ‘bishop vs knight’, ‘offer of simplification’, and ‘queens and rooks to the 7th rank’. The one suite marked in red measures advancement of the f/g/h pawns. I think the added king safety code has something to do with that: the program is less willing to push those pawns if the king is castled on that side.
| Suite/Time | v2 raw | v2 % | v3 raw | v3 % | Delta raw | Delta % |
|---|---|---|---|---|---|---|
| WAC/5 | 258 | 86.0% | 266 | 88.7% | 8 | 2.7% |
| WAC/10 | 270.5 | 90.2% | 273.5 | 91.2% | 3 | 1.0% |
| WCSAC/5 | 775 | 77.4% | 784.5 | 78.4% | 9.5 | 0.9% |
| ECMGCP/10 | 35.5 | 19.4% | 37 | 20.2% | 1.5 | 0.8% |
| SBD/60 | 45.5 | 34.0% | 96.5 | 72.0% | 51 | 38.1% |
| STS1/5 | 30 | 30.0% | 48.5 | 48.5% | 18.5 | 18.5% |
| STS2/5 | 19.5 | 19.5% | 39.5 | 39.5% | 20 | 20.0% |
| STS3/5 | 45 | 45.0% | 41.5 | 41.5% | -3.5 | -3.5% |
| STS4/5 | 36.5 | 36.5% | 41.5 | 41.5% | 5 | 5.0% |
| STS5/5 | 41 | 41.0% | 59.5 | 59.5% | 18.5 | 18.5% |
| STS6/5 | 47 | 47.0% | 48 | 48.0% | 1 | 1.0% |
| STS7/5 | 22.5 | 22.5% | 33 | 33.0% | 10.5 | 10.5% |
| STS8/5 | 31 | 31.0% | 20.5 | 20.5% | -10.5 | -10.5% |
| STS9/5 | 30 | 30.0% | 37 | 37.0% | 7 | 7.0% |
| STS10/5 | 55.5 | 55.5% | 57.5 | 57.5% | 2 | 2.0% |
| STS11/5 | 19 | 19.0% | 28 | 28.0% | 9 | 9.0% |
| STS12/5 | 42 | 42.0% | 48.5 | 48.5% | 6.5 | 6.5% |
| STS13/5 | 45.5 | 45.5% | 48 | 48.0% | 2.5 | 2.5% |
| STS14/5 | 31 | 31.0% | 62.5 | 62.5% | 31.5 | 31.5% |
| STS15/5 | 22 | 22.0% | 29.5 | 29.5% | 7.5 | 7.5% |
The table below shows chess4j’s performance in a head-to-head match verse four other engines (the bottom one being my engine, Prophet). The match conditions were: only one processor could be used, no thinking on the opponents time, and no opening book libraries or endgame tablebases. The matches were done using a set of 20 starting positions called the ‘Nunn Test Suite’. The engines play from each position twice- once as white and once as black, making the entire match 40 games. One thing that may jump out is that the results don’t seem consistent. Why the variability against the same opponent using different times? It very well could be that chess4j is better at longer time controls, but it would take thousands of games to prove that theory. This game set is too small to be statistically significant. The main point was to get a feel for how strong the engine is.
| Opp | 1 min | 3 min | 10 min |
|---|---|---|---|
| Gerbil | 5-31-4 | 9-23-8 | 10-23-7 |
| Horizon 4.3 | 6-31-3 | 8-28-4 | 4-31-5 |
| Lime 6.2 | 5-32-3 | 4-29-7 | 6-29-5 |
| Prophet 2.0e | 2-32-5 | 4-35-1 | 2-35-3 |
While there is certainly a lot to do with the evaluation, it’s not so far behind Prophet’s that it would explain such a lopsided result. I’m afraid the main disadvantage chess4j has comes down to speed. On my laptop I typically see chess4j search between 180,000 and 200,000 positions per second. That may sound like a lot but this (32 bit compile of Prophet) searches between 800,000 and 1 million positions per second (and there are programs out there that search much faster than that!). To test that theory I ran another set of matches against the same opponents using time odds. In the table below, the 2x, 4x, and 8x columns show how chess4j would fare in a 1 minute match if it were 2x, 4x, or 8x faster than it is now. As you can see, if chess4j were 5-10 times faster than it is it would be much more competitive against this group.
| Opp | 1 min | 2x | 4x | 8x |
|---|---|---|---|---|
| Gerbil | 5-31-4 | 10-22-8 | 12-21-7 | 21-8-11 |
| Horizon 4.3 | 6-31-3 | 8-26-6 | 11-21-8 | 12-21-7 |
| Lime 6.2 | 5-32-3 | 6-30-4 | 14-20-6 | 16-12-12 |
| Prophet 2.0e | 2-32-5 | 6-29-5 | 10-27-3 | 15-9-6 |
Is it possible to make chess4j that much faster? Maybe. I was able to improve the speed of this version by a factor of two by doing a careful analysis of the data structures being used (mostly Collections stuff, like ‘ArrayList’ vs ‘HashSet’ and such), and looking up their runtime complexities for different operations (like adding, or iterating…) and changing the data structures where appropriate. But, I think I’ve gone about as far as I can down that road. This is a Java program after all. It’s not as “close to the metal” as a C program. I think to squeeze much more out of I’d have to scale back on how much object instantiation it does. But then it would look less like an object oriented program, and would probably be less readable and possibly harder to test… all of which go against what I want to accomplish with this program.
So, what’s next? My next areas of focus are:
- It’s time to establish a proper testing routine. Meaning that, going forward, all changes to the program need to be measured in terms of ELO gain. This is a lot harder than it sounds but it will ensure changes are good changes.
- Add a pondering search. Instead of sitting idly as the opponent is on move, try to guess what the opponent is going to do and start formulating a response. If we’re right often enough we can allow more time to think about each move.
- Use all the machine’s processors! Most computers these days have multiple processors, yet chess4j is only capable of using one. (using multiple processors is easy. doing it efficiently [in the context of a computer chess] is MUCH harder than you might think)
If you’d like to try your hand against chess4j, you can download it from the
project website. It’s a console program though, not graphical. However, you can download a GUI and set it up to use chess4j… see the readme.txt file.
Enjoy!