Category Archives: Prophet

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.

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%

Prophet is back

After a VERY long absence from server play, the rewrite of my chess engine Prophet is finally far enough along to play some games online. The engine itself has been capable of play for a little while now, but I’ve establishing a testing routine and wanted to get an opening book.

Previous versions of Prophet had a custom book format, using fseek() and the like on a binary file. I may go back to that at some point but right now Prophet 3 uses SQLite to query the book built for chess4j.

Anyway, the engine has been online ICC most of the day:


67: + 1632 W 1469 brittabeast [ br 5 3] D11 Res Nov 30 16 15:29
66: + 1622 B 1479 brittabeast [ br 5 3] B03 Mat Nov 30 16 15:23
65: + 1611 W 1466 ituchesstech [ br 5 3] D08 Mat Nov 30 16 15:13
64: + 1600 B 1533 Knipshun [ br 5 3] A00 Res Nov 30 16 14:56
63: + 1586 W 1547 Knipshun [ br 5 3] C00 Res Nov 30 16 14:53
62: + 1570 B 1563 Knipshun [ br 5 3] A00 Res Nov 30 16 14:49
61: + 1553 W 1092 Darkpower [ br 5 3] A04 Res Nov 30 16 14:42
60: + 1551 B 1094 Darkpower [ br 5 3] B00 Res Nov 30 16 14:37
59: + 1549 W 1096 Darkpower [ br 5 3] D35 Res Nov 30 16 14:33
58: + 1547 B 1098 Darkpower [ br 5 3] B02 Res Nov 30 16 14:29
57: + 1545 W 1100 Darkpower [ br 5 3] C41 Res Nov 30 16 14:23
56: + 1543 B 1102 Darkpower [ br 5 3] B07 Res Nov 30 16 14:16
55: + 1541 W 1104 Darkpower [ br 5 3] D31 Res Nov 30 16 14:14
54: + 1539 B 1106 Darkpower [ br 5 3] B06 Res Nov 30 16 14:04
53: + 1537 W 1108 Darkpower [ br 5 3] D37 Res Nov 30 16 13:59
52: + 1534 B 1111 Darkpower [ br 5 3] B01 Res Nov 30 16 13:53
51: + 1531 B 1520 zalk [ br 5 3] A00 Res Nov 30 16 13:50
50: + 1514 W 1537 zalk [ br 5 3] B06 Res Nov 30 16 13:45
49: + 1495 W 1233 TT [ br 5 3] A04 Fla Nov 30 16 13:33
48: + 1695 B 1431 amr [ Br 2 1] B00 Mat Nov 30 16 13:28

20/20 isn’t too bad! Granted, it helps that it was vastly underrated, but still…what fun 🙂

It’s About Time

I’ve been working on “the big rewrite” of my C chess engine lately. I mentioned some time back that it was just barely capable of playing a legal game of chess. At the time it did a depth first search using a depth of 4. Since then, I’ve added a timing algorithm. The idea is that, we don’t necessarily want to search to a fixed depth — we want to figure out how much time we can afford to spend on the next move, and then search as deeply as we can in that time, because generally the deeper your search tree the stronger your move.

The problem is, you don’t really know ahead of time how deep you’re going to be able to search in the allotted time. The approach taken by Prophet (and virtually every other chess program that I know of) is to use iterative deepening. First, search to depth 1, then depth 2, then depth 3, and so on.

In the output below, there is one line each time Prophet changes its mind about the ‘principal variation’ (what it thinks the optimal line of play is given that each side is trying to win), and one line at the end of each iteration. The score represents ‘centipawns’ — so 507 == “5.07 pawns.” Time is recorded in centiseconds. It may seem odd to use centiseconds as opposed to milliseconds or just seconds, but that’s the XBoard protocol. In this example Prophet completed the depth 5 search and started but did not fully complete the depth 6 search:

DEPTH  SCORE  TIME   NODES PV
    1    219     0       2 a8b8
    1    224     0      14 c7c6
    1    231     0      15 d7d6
    1    234     0      16 d7d5
    1    629     0      20 a6c4
    1    629     0      40 a6c4
    2    214     0      41 a6c4 d1d4
    2    214     0     187 a6c4 d1d4
    3    319     0     364 a6c4 e2c4 f4g2
    3    527     0    1183 a8c8 c4a5 a6e2
    3    532     1    4127 c7c6 c4a5 a6e2
    3   1024     1    7877 d4e2 c3f3 a6c4
    3   1029     2    8924 f4e2 c3d3 a6c4
    3   1029     2    9173 f4e2 c3d3 a6c4
    4    614     3   18415 f4e2 c3d3 a6c4 d3d4
    4    614     6   23954 f4e2 c3d3 a6c4 d3d4
    5    922    22  139575 f4e2 c4a5 c5b6 c3e3 b6a5
    5    922    47  383672 f4e2 c4a5 c5b6 c3e3 b6a5
    6    507   242 1472162 f4e2 c4a5 c5b6 c3e3 b6a5 d1d4
 # Aborting search depth=1, ply=5 on time...
 move f4e2

At first glance this may seem like an awfully inefficient solution. After all, search time grows exponentially with depth. If we knew we were likely to search to depth 6 (or 10, or whatever), wouldn’t it be more efficient to just skip the previous searches? Surprisingly, no. That is, not if your program uses knowledge from each search to guide the next one.

At the moment the only apriori knowledge that Prophet uses is the principal variation itself. When Prophet begins a depth N search, the principal variation from depth N-1 will be tried first. This quickly establishes tight alpha/beta bounds which helps “cutoff” useless branches of the search tree. It also avoids the situation in which depth N-1 says move A is best, and depth N says move B is best (but hasn’t gotten around to searching move A yet) when time runs out. What do you do?

The next improvement will be to add some hashing. Hashing will significantly improve the “sharing of information” from one search to the next. The main challenge here is producing a good hashing key (signature). The key should be fairly unique — there should be very little chance of two distinct positions producing the same key. Additionally, the keys generated should be uniformly distributed over the solution space. And, it’s very important that it be fast!

That said, I think I’m going to put a temporary hold on the development of the engine itself and work on building a bit of infrastructure. I’ll describe what I have in mind in a separate post, soon.