Any Brave Benchmarkers?

[LiquidNitrogenOverclocker]

I know some of you might get ill at the prospect of running a checkers benchmarking application, but I don't have enough meaningful data from systems that are not overclocked to see how fast some of the overclocked computers' scores are at this link:

http://www.liquidnitrogenoverclocking.c ... ults.shtml

The test run takes several hours, so don't do it when you are in the middle of something (maybe start it before you would otherwise shut down your computer for the day).

When you are done, I only need to see the time on the last line of the "report.txt" file that gets created.

Thanks to all who do volunteer.

And, there is one side benefit for you: You can see how fast your computer is compared to everyone else who submits a result. Since it is a 64-bit application that uses only integer math, the results should scale linearly with the "true speed" of the CPU.

[zullil]

I know some of you might get ill at the prospect of running a checkers benchmarking application, but I don't have enough meaningful data from systems that are not overclocked to see how fast some of the overclocked computers' scores are at this link:

http://www.liquidnitrogenoverclocking.c ... ults.shtml

The test run takes several hours, so don't do it when you are in the middle of something (maybe start it before you would otherwise shut down your computer for the day).

When you are done, I only need to see the time on the last line of the "report.txt" file that gets created.

Thanks to all who do volunteer.

And, there is one side benefit for you: You can see how fast your computer is compared to everyone else who submits a result. Since it is a 64-bit application that uses only integer math, the results should scale linearly with the "true speed" of the CPU.

The application is a Windows executable. So Mac and Linux users are excused (unless they want to run this under wine).

[LiquidNitrogenOverclocker]

The application is a Windows executable. So Mac and Linux users are excused (unless they want to run this under wine).

Which is kind of ironic because I wrote it in XCode under OS 10.4 on my Mac, and just compiled it with MS Visual Studio later.

[Mark]

Just uploaded my report.txt file, but had a 404 error, so I'm not sure if it got through... Anyway, results for stock Q6600 at 2.4GHz were:

Tuesday, February 16, 2010 @ 04:40:50
#################### This entire database was solved in 6 hours, 17 minutes, 41 seconds. ####################

Tuesday, February 16, 2010 @ 04:40:50
Database solving run completed in 6 hours, 49 minutes, 19 seconds.

I'm not sure which time above you use. There was no place to include ram in the questionnaire, so I'm guessing that doesn't matter. (I have 4 GB) Also, this benchmark only uses one core, doesn't it?

Hope this is helpful!

Mark

[LiquidNitrogenOverclocker]

Thanks Mark!

Yes, my email box was full, somebody emailed me about 20 pictures, about 1440x1200 @ 300dpi, of an overclocked computer that he wanted to list on my website for sale. Those images took up most of my 100 MB allotment for email on the server. His system looked like something Frankstein designed in metal shop with his eyes closed, so it won't be making an appearance any time soon.

About the 2 different times:

" This entire database was solved in 6 hours, 17 minutes, 41 seconds. "

That was the 6-piece database. Recall before this one was solved, you have to solve the 2-piece, 3-piece, 4-piece, and 5-piece databases. That is why this time...


"Database solving run completed in 6 hours, 49 minutes, 19 seconds. "

...was longer.

Thanks again. I will post your result. Very much appreciated!

[LiquidNitrogenOverclocker]

Also, this benchmark only uses one core, doesn't it?

Yes it does. I only want to compare "per core" performance, without any parallelizations.

Your result is now here, at slot #13:

http://www.liquidnitrogenoverclocking.c ... ults.shtml

There is a huge gulf spanning positions 11 though 16, with the top 10 spots pretty closely fought out by the overclockers.

[Mark]

Also, this benchmark only uses one core, doesn't it?

Yes it does. I only want to compare "per core" performance, without any parallelizations.

Your result is now here, at slot #13:

http://www.liquidnitrogenoverclocking.c ... ults.shtml

There is a huge gulf spanning positions 11 though 16, with the top 10 spots pretty closely fought out by the overclockers.

Thanks Ed. Glad it was helpful!

What's going on now in the world of checkers? I'm not a checkers player myself, but I occasionally check http://www.fierz.ch/checkers.htm to see if there's anything new out. I had followed the saga of solving checkers closely and am a big fan of "One Jump Ahead."

Regards,

Mark

[LiquidNitrogenOverclocker]

Thanks Ed. Glad it was helpful!

What's going on now in the world of checkers? I'm not a checkers player myself, but I occasionally check http://www.fierz.ch/checkers.htm to see if there's anything new out. I had followed the saga of solving checkers closely and am a big fan of "One Jump Ahead."

Schaeffer was nice enough to mention me in the update to his book "One Jump Ahead: Computer Perfection at Checkers." My buddy Gil and I helped verify the Chinook team's 8-piece databases in the fall of 2001 before Schaeffer started the project to solve the game of checkers. It turns out, from the hundreds of billions of positions in his databases, only 89 were incorrect. Gil and I were able to demonstrate our data was correct, so Schaeffer had to recalculate his 8-piece set before building the 9- and 10- piece sets. He was thankful that we helped locate these errors before they ended up being inherited by the larger databases.

One other person has a 10-piece database set, and that is Ed Gilbert of New Jersey. He has the "bitbases" (just win-loss-draw) plus some of the Distance To Conversion databases (like how long it takes to EITHER promote a checker to a king, OR execute a capture). The DTC in checkers is similar to the DTC in chess, where either a pawn promotes or one side captures a piece.

Here is the longest DTC (with red to move) in the game of checkers found in Ed Gilbert's 10-piece database (shown with my pieces that will be in the new program I am writing now)



The white checker is about to promote and become a king, so the red king needs to block it on its turn to move. This is like tying down a Rook to defend a pawn, not a good use of your material.

Even now, in 2010, Gil Dodgen and I are the only ones to have computed Distance To Win in the game of checkers. DTW is difficult to compute in checkers, odd as that may sound. The problem is: kings! Kings move forwards and backwards, and sometimes the best way to "make progress" is for 1 or more of them to retreat, and later regroup.

The way most database resolving iterators work in checkers is much different than in chess. In chess, you can start with all mate positions (checkmate and stalemate) and take "backward steps" which, by definition, must be "n+1" moves from the mate. Take another step, you are the losing side that is "n+2" moves from losing, etc.

In checkers, you can execute single jumps, double jumps, triple jumps, etc, and all jumps are forced. But, sometimes you have the choice to make more than one jump (rare, but it happens). For this reason, DTW must load boatloads of subdatabases in RAM during the jump routines. Even more complicated is the fact that sometimes you jump into the CROWNING ROW and now have a king (which would be similar to a move such as cxd8 = Q in chess).

Even worse, in checkers, sometimes you determine a move is a win in X, then on the next pass, the "losing side" finds an improvement, so you must revisit the original winning position, and demote the "win in X" to something like a "win in X + 2", which takes longer. This, in turn, can influence other positions. And, even more tragic, sometimes a faster win is not proven to win after several more iterations, which means all of the lost positions for the other side to move need to be recalculated.

You can see evidence of this in the "report.txt" file that gets generated.

Code: Select all

wins resolved this pass = 716, losses resolved this pass = 0, draws resolved this pass = 30.
win lengths improved this pass = 4353, loss lengths that changed this pass = 0.

total move pass wins = 11241528, total move pass losses = 112181, total move pass draws = 283047.
cumulative win lengths improved = 9825190, cumulative loss lengths that changed = 5.

As shown above, only 716 new wins were found in that iteration, but 4,353 wins lengths had improved. In finding quicker winning paths, the "loss lengths" will be perturbed on the next pass, and so on. This process must iterate until no new wins/losses/draws are found AND no win/loss lengths change.

This can take a very long time! Also, the algorithm runs the chance of becoming an infinite loop that never terminates. This is the reason why most programmers abandon the task of trying.

Nobody has published an original research paper involving the game of checkers since Schaeffer solved it, and I believe I was the last one who published a paper before the game was solved (see http://www.GothicChess.com/7_piece.pdf for that one).

Since I wrote a 64-bit checkers move generator that uses less than 20 lines of code (not quite a "magic bitboard" but one with unique properties to reduce most of the overhead for move generation) I believe I have the fastest possible implementation. I've tested it against 3 other programs from a common platform, and my program is about 1.8 times as fast as the others, on average. That might be worthy of a paper.

Computing the 10-piece perfect play databases using this new technology, run on a cluster of my 4.5 GHz overclocked Intel Core i7-920 processors, should allow this computation to be completed in a reasonable amount of time (less than one year). This will definitely be the subject of a paper.

I'm not sure there's really too much news to report other than this. People have long since migrated away from checkers as an interesting field of study. I still think DTW in checkers is pretty cool. The wins are so long, programs with the bitbases can't win the positions, even if you give them the winning side. That was the surprising fact that allowed my one paper to get published.

Everyone thought checkers was simple enough that a program could always win a position that was a proven win. They were almost correct.

[Mark]

Thanks for the info, Ed. Yes, I remember you being mentioned in the update to One Jump Ahead. I was actually mentioned (indirectly) in the update, also! I had stumbled upon a web page under construction by someone involved with Chinook that indicated that checkers was solved. I reported it here:

http://www.talkchess.com/forum/viewtopi ... ers+solved

and it was denied here:

http://www.talkchess.com/forum/viewtopi ... ers+solved

Anyway, in his update of the book, Jonathan printed the email I had sent him congratulating him on solving checkers (pg 502). This caused problems because the results were supposed to be kept secret until his paper was approved by "Science." At the time, he had denied solving checkers to avoid jeopardizing the paper.

I saw that Ed Gilbert's 10-piece database is for sale. I look forward to the results when you compute the 10-piece perfect play databases. I'll bet there are some amazingly long wins yet to be found!

Interesting that you're writing a new program now. Best of luck with it.

Mark

[LiquidNitrogenOverclocker]

I saw that Ed Gilbert's 10-piece database is for sale.

And Ed's program, Kingsrow, was one of the programs that could not win in the 7-piece endgame where it had 4 pieces and my database defended the losing side with 3 pieces. I think I am to "blame" for his creation of the DTC databases for his program



So you were the one who almost gave Schaeffer a heart attack, lol! He mentioned that one of his web people put the announcement on the production server instead of the test staging server, or something like that, and almost jeopardized the whole thing.

That is interesting, isn't it? Is your picture on his dartboard?