james swafford

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):

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

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.

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:

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:

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:

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:

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.

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.

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.

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!

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:

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!

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.

I just released version 3.1 of chess4j, my Java based chess engine. This version is about 100 elo stronger than 3.0. The key differences are:

• The Groovy language is no longer used. Groovy is a fine language for some purposes. chess4j didn’t make heavy use of it but did use it for some I/O type classes, which I wrote about in this post. Unfortunately, it was a constant struggle with my IDE of choice (STS). It constantly balked and complained about the Groovy classes. I had hoped that in time IDE support would improve but in the end I just got tired of constantly messing around with it. On a positive note the chess4j jar file went from 11.5 mb to 4.5 mb.
• Some modest search improvements, worth about 20 elo.
• Added pondering. This means that when it’s the opponent’s turn to move, chess4j is already thinking about its response. If chess4j correctly predicted what the opponent will play, then it is that far ahead in formulating a response (it may even be able to play its move instantly). Seems to be worth about 80 elo.

In my testing, chess4j 3.1 scores 53% against 3.0 in a 1000 game match without pondering, and 64% in a 1600 game match with pondering.

I have my sights set on a parallel search for the 4.0 release, but I think there will be another minor release or two before that to work on search speed optimizations.

You can grab the latest and greatest from the project website. Enjoy!

This is the second installment about our second cross country trip, focusing on the northwest. In case you missed it: Chapter II part I.

June 25 – Albany OR – Just an overnight stay on the way to Seattle.

I love this picture of the truck in front a big rig… shows just how much we were hauling!

And once again we finally made it to “the other side!”

June 26-July 1 – Seattle WA – one of my favorite cities. The first two pictures here are the view from the top of the Space Needle in a restaurant we ate lunch at. We also got coffee from the original Starbucks and visited the fish market.

We did have a near catastrophe here. Not paying attention at a gas pump, I filled our diesel truck full of unleaded gas! That set us back a few days and caused me a lot of anxiety. That won’t ever happen again!

July 2 – Pendleton OR

July 3 – Jerome ID – Not a lot going on in Jerome, but one of Amy’s long time Internet friends lived here. She got to meet her face to face and have lunch with her.

July 4-7 – Yellowstone – there is no way I could describe the beauty of this place, so I took a lot of pictures. One of the things that was striking to me (other than boiling puddles of water) is the grassy forest floors. It was very different than the forests back east. It almost felt like we were walking to the Shire.

July 8-10 – Billings MT – the battle of Little Big Horn. RIP General Custer. He’s not actually buried here but this is where he fell as he was surrounded by Indians (Native Americans).

July 11-15 – Rapid City SD – lots going on in this area. We did a drive through tour of the Badlands, went to Devil’s Tower, and Mt. Rushmore. Amy really loved this area.

July 16-17 – Bismarck ND – we camped in Bismarck but we stayed here just to take a day trip up to Minot, which is not too far from the Canadian border. The remarkable thing about Minot (“Magic City”) is that I was born there! And there is a cool Stave church.

July 18 – Nowhere MT

July 19-23 – Minneapolis MN – Mall of America!! And we timed it just right so that we were here over Ailsa’s birthday. What else could a girl want other than to be in the biggest mall in America on her birthday with some spending money??

July 24-26 – Madison WI – home of “House on the Rock.” That place is insane.

July 27-28 – Elkhart IN – just a stop over. We were going to see where Zinger travel trailers are made but unfortunately the timing didn’t work out. They only did public tours on certain days of the week.

July 29-31 – Dayton OH – birthplace of Orville and Wilbur Wright. We met up with Amy’s long time friend Tanya to tour the Wright bicycle shop and a museum, as well as the Cincinnati zoo.

Aug. 1-2 – Wytheville VA – we were getting into familiar territory here. We took a day to do a little day hiking on the AT so that Jamie could finish his hiking merit badge.

Aug. 3 – HOME.

What an amazing journey. The best part was the time with the family, completely disconnected from the rest of the world. I miss that more than anything.

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 🙂

On May 17th we set out on the second leg of our Tour de States. This time our focus would be on the Northwest. We would start out going through Tennessee and up through St Louis MO, then across to Kansas, through to Colorado, Utah, Oregon, Washington, and back along the northern most states- Montana, Wyoming and the Dakotas, before heading back south and east. Everyone was super excited about this trip. Neither Amy nor I had ever been to that part of the country before.

We didn’t have the smoothest of starts to this trip. The evening before leaving, as I went to hitch up the truck, the tongue jack wouldn’t lift the trailer high enough to clear the ball hitch on the truck. I scrambled to the Tractor Supply store to get a tongue jack that, though it does the job, isn’t quite what you want for a travel trailer. With some help from my brother-in-law Rob and a little luck we got the new tongue jack put on and we managed to leave on time (almost). In hindsight, that seems to be a foreshadow of things to come. There were definitely more maintenance issues on this trip than the last!

Just like last time, there would be a mix of travel days, sight seeing days, work/school days, and sometimes combinations of those. It didn’t take us long to get back into a rhythm once we were on the road. We wanted to stop and see some family in NC, TN and MO on the way out west, so that was the focus of our first few stops. Here are the stops we made on the way out west:

May 17-18 – Lexington NC – We stopped here to see Amy’s stepmother Gale. We spent a nice day at the house visiting. We went out for a meal at a nice restaurant. It was good to catch up.

May 19 – Newport TN – This was just an overnight stop in the mountains on the way towards Nashville. On our last trip we actually went down to Atlanta and then back up to Nashville just to avoid the mountains, but I figured that after 8000 miles or so of pulling that trailer I’d be OK. Besides, we’d have to go through the Rockies!

The campground was one of my favorites… definitely somewhere we could have spent more time. Pictured below is Jamie cooking up our supper! I think we were having cheeseburgers.

May 20-23 – Nashville TN – My dad’s side of the family are in the middle TN area so seeing family was definitely the primary agenda in Nashville. We managed to see my grandmother, sisters Fallon and Hillary along with their kids, as well as my aunt Carla. We also squeezed in a trip to the Parthenon.

May 24-26 – Bowling Green KY – Bowling Green is the home of the famous Mammoth Cave. Carlsbad Caverns was one of my personal highlights of the last trip so I was really looking forward to this. There are around 400 miles of caves in this system! Of course only a small portion of that is open to the public.

We set out on a tour, and as we got just about to the bottom, in a fairly narrow “corridor,” the group suddenly stopped. We stayed in place for 20-30 minutes before a Park Ranger came through saying that “we have a situation, law enforcement might be coming behind you.” Wait, what!?! That’s all the information we had for several more minutes before we learned that someone had fallen, possibly dislocating a shoulder so they didn’t want to move them. Our tour guide said that was the first time in 17 years that tour had been stopped – we just hit the lucky day! So, we “backed out” of that cave, but they put us on another tour that technically wasn’t even open to the public just yet.

May 27-30 – St Louis MO – my mom and sister Amanda both live in southeast MO so they were able to come spend time with us over the (Memorial Day) weekend. Being a summer holiday weekend, the campground was very busy. We ended up with a pretty good spot though, on the back end of the campground overlooking a cemetery! (At least the neighbors were quiet!)

We arrived at the campground on a Friday afternoon. That Saturday my sister Amanda, her daughters Cheyenne and Leah, and my sister Hillary (from TN!) with her family came up to see us. We went to a kid’s museum in St Louis, and of course the Gateway Arch. The Arch was a neat experience. The elevator that goes to the top has these little “pods” that look like something out of a sci-fi movie. Each “pod” seats about 5 people. You get out at the top, walk across a breezeway of sorts (though it’s anything but breezy, it’s actually pretty hot and stuffy) that overlooks the city, then get back in the elevator to go back down. The architecture and engineering are pretty amazing.

Shortly after that whole crew left us my mom came up and spent a night with us. We took a trip over to Grant’s Farm. The property was once own by Ulysses S. Grant and now owned by Anheuser-Busch.

May 31-June 2 – Kansas City MO – The main thing we wanted to do in Kansas City was go to Union Station. Union Station is, well, a big ole train station full of shops and exhibits. When we walked through it was just about empty. It’s striking how tall the ceilings are. It’s truly a beautiful building. After walking through the building we walked through a pedestrian crossing over the tracks on our way to Jack Stacks Barbecue.

June 3-6 – Omaha NE – We were really looking forward to getting to Omaha to see our good friends from our San Diego days, the Phipps family. It’s been a long time since we’d seen them but you wouldn’t have known it, we just picked right up like we’d just seen them last week! Jason and Candice were very welcoming and hospitable. We ate a great meal with their family and thoroughly enjoyed the evening! We just hope it’s not another 10 or 15 years before we see them again!

One negative note about Omaha – we caught a flat on the trailer. The road going into Omaha was so bad and bumpy that we didn’t even know it! It wasn’t until we made a left turn about a mile from the KOA we were staying at that I saw the tire in the mirror. Unfortunately this wouldn’t be the last flat either.

June 7 – North Platte NE – Just passing through here on the way to Denver!

June 8-10 – Denver CO – I was really looking forward to our stay in Denver – the Mile High City! We didn’t actually stay in Denver, but just west of Denver in Central City. Central City is in the Rockies and sits at about 8500 feet. The view was gorgeous! The campground in Central City was one of my favorites, but it was a challenge to get up to it. There were several switchbacks and sharp turns up some pretty steep climbs.

Before we left home Amy had already looked ahead for any opportunity to see the San Diego Padres play and this was it! They were playing the Rockies while we were in Denver, so naturally we went to the game. We (mostly Amy) were one of just a few rooting for the Padres, but they won!

June 11-12 Silt CO – After leaving Denver and continuing west we had to climb up to just about 11,000 feet in elevation. Trucks were having to go slow to avoid overheating (including us). At one point going down some elevation our brakes started smoking. It was a real balancing act keeping the truck slow enough to maintain control and not smoking the brakes.

One of our favorite activities of the entire trip was in Silt. We ziplined over the Colorado river! We also celebrated Father’s day in Silt by hiking along the river.

June 13-14 – Vernal UT – AKA Dinoland! Vernal’s “claim to fame” is the dinosaur bones found in the area. We went to the National Park where they have a structure built onto a rock wall with bones still embedded into it. The theory is that there was a river in that area where the bones had collected. Pretty incredible place.

June 15-20 – Salt Lake UT – On the way to SLC we came across the famous Bonneville Salt Flats. It’s literally a huge flat area of … salt. Many land speed records have been set here. It was pretty cool to just walk around on the salt. It was so bright that you had to squint.

Of course we also had to visit the Great Salt Lake. We took a short hike around a section of the lake, ate lunch and then ventured down onto the beach. The water in the Salt Lake is very warm, and obviously salty. Nothing lives in the lake except brine shrimp. Amy bottled some of the water, and several brine shrimp were in the bottle. Most died but one hung on for quite some time. She named him Fred. Sadly, Fred died just a few days ago in a sea monkey aquarium in our home in NC. He lived a pretty long and adventurous life for a brine shrimp!

June 21 – Winnemucca NV – the road between SLC and the west coast is long and barren! You can see in the picture below the sign that read “Next Gas 179 Miles” !! There was very little on that road and hardly any cell reception. It’s definitely not somewhere you’d want to breakdown! Thankfully we made it through without any trouble.

Every time I think of Winnemucca I also think of the Johnny Cash song “I’ve been everywhere.” We would play that song in the truck naming off the places we had been.

June 22-24 – Klamath Falls OR – Home of Crater Lake. Crater Lake is easily, without a doubt the most beautiful place I’ve ever seen. The lake sits on an “imploded” volcano, and the water is nearly 2000 feet deep. It’s the deepest lake in the US and the 9th deepest lake in the world. The depth of the water makes it an incredible blue. There is no “feed” into the water – it’s filled just off rain and snow runoff. This area get a LOT of snow – over 10 feet a year. We drove about half way around the lake, stopping at different points to look at the lake from another point of view (the road on the other half was still closed from snow!). I hope to return to this area again one day, it was truly stunning.

That’s all for this installment. I’ll write about the rest of this trip in another post soon!