4

I am learning artificial intelligence and chess programming. I want to analyze the architecture and read the code of existing chess engines. But I am confused between multiple choices. There are several free chess engines available, for example:

  • Crafty
  • GNU Chess
  • Stockfish
  • IPPOLIT
  • Fruit 2.1
  • (Add your chess engine here)

I am wondering which chess engine is most efficient in terms of CPU cycles used. For example, if Crafty achieves 3300 ELO by thinking for 30 seconds on each move, and GNU chess achieves 2500 ELO by thinking 1 second on each move, I would consider GNU Chess to be more efficient.

So which engine is most efficient? What would lead me to choose one over another?

  • 5
    I'm not too sure about your definition of efficiency. In your example, an 800 point difference is huge. It may be an amazing display of efficiency to get 800 additional Elo points in only 29 additional seconds. – Tony Ennis Jun 16 '12 at 13:18
  • 1
    Second, why are you concerned with 'efficiency' and not the types of AI algorithms being used, if your goal is to learn AI programming? Third, I believe any of these programs will be sufficiently challenging for someone to learn. – Tony Ennis Jun 16 '12 at 13:21
  • @TonyEnnis I'm concerned with efficiency because I need to write my own code in Java that will run on mobile devices. An algorithm that runs in 30 seconds on my Core Quad machine will take forever on a mobile. – Monika Michael Jun 16 '12 at 14:46
  • 2
    First, computer ELO ratings are pretty dicey - computers don't play in top tournaments and thus their ELOs are less than reliable. Further, the published ratings tend to be on custom hardware. On common hardware they are somewhat lower. Finally, your desire to have it play 'well enough' is logical, but that's a different thing. You aren't looking for an 'efficient' program, you're looking for one that rates at 2500 (or whatever), takes X seconds per move on average, and can be written in Java. That's a lot more concrete than some debatable 'efficiency.' – Tony Ennis Jun 16 '12 at 17:27
  • 1
    By the way, I admire your ambition. However, if you wrote a program from scratch, for a mobile device, in Java (not the speediest of languages), that was rated USCF 1800 or more, and played quickly enough (average 15 seconds a move?), I'd be super-impressed. – Tony Ennis Jun 16 '12 at 18:06
6

If I were going to do this, I'd choose Stockfish, Fruit 2.1, and Crafty for no reason other than their high quality is proven. Then I'd compare and contrast the techniques, algorithms, and choices made by each.

These aren't easy programs; it would be a lot of work to gain a true understanding.

  • 1
    +1 on this, your first priority should not be efficiency but understanding the theory, which is way easier if the framework has a proven high quality standard. Performance comes later, after you understand what the hell is going on! – tmesser Jun 18 '12 at 16:24
  • 3
    The Stockfish code is exceptionally clear, which is a rarity for chess engines. – dfan May 22 '13 at 12:17
6

This is not a direct answer to your question — but because you're interested in Java, check out this link, which has a UCI compatible engine written in Java. Browsing through the code it looked quite readable. It loses to Crafty and Stockfish regularly, but that is to be expected — they usually looked ~4 ply deeper because of the speed difference.

I think it will suit your needs as a fairly strong engine that runs on Java, if only to review the code.

3

For many years, nearly all professional chess programmers have tested code changes by running many blitz games to see whether their changes have improved engine performance. Here's a paper describing a genetic programming technique across many blitz games. Stockfish programmers follow this same method in conjunction with Fishtest.

Stockfish programmers typically test proposed changes by running many fast games with tight time controls. If the proposed changes show a benefit, then the change is submitted for testing at tournament time controls.

Stockfish is not unique in this regard. Nearly all professional or semi-professional engines were tuned at blitz time controls first, and then at tournament controls.

So, in short, because of the way that most chess engines are tuned, I personally feel your supposition is incorrect -- I feel it is more likely that the "most efficient" chess engine will be the best performing engine at any time control.

tl:dr; use Stockfish

EDIT: Not sure why my answer is getting downvoted here. As further evidence that what I'm saying is correct, please check out the CCRL 40/4 and the CCRL 40/40 automated ratings lists. If you compare the two lists you will see that the strongest performers in the 40/40 list are almost exactly the same strongest performers in the 40/4 list. And there is no engine that has an incredible performance jump at tournament vs. blitz controls -- they all typically remain within about 50 ELO of their blitz ratings at long time controls. To me, that is clear evidence of a critical connection between blitz engine "efficiency" and tournament engine "efficiency".

If you want a toy engine to hack on, here is my Superpawn engine.

  • You may be right, John, but the devil's advocate in me suggests that the engines are similarly rated at Blitz and Standard time controls because they were engineered the same way. If a change was discarded because it showed no improvement under blitz timing, no one would ever know if that change would have resulted in a substantial improvement but only at standard time controls, because it's never been tested. For example, any tweak that might have helped overcome the Horizon Problem would probably not budge the ELO at blitz, but might be invaluable at STC. – jaxter Sep 29 '16 at 0:09
  • If you're correct, then you should be able to point out a top-100 chess engine that has a significantly different ranking on the CCRL 40/4 from the CCRL 40/40 ratings lists. HINT: You can't – johnwbyrd Oct 3 '16 at 8:52
1

First, the definition in the question doesn't make much sense. @johnwbyrd is correct, the 'most efficient' chess engine chess engine should be the best performing engine at any time control.

In general, the stronger the engine is the more efficient the computing resources are utilised. This is expected because a chess engine is really a fast calculator of chess moves. The more (and accurate) moves it can think, the better it becomes.

A strong chess engine such as Stockfish is a brilliant example of applying computer optimisation. For example, let's take a look at how the hash table is implemented in Stockfish:

class TranspositionTable

  static const int CacheLineSize = 64;
  static const int ClusterSize = 3;

This definition is telling us the size of a cluster in the hash table should be evenly divided by the size of a cache line. It is a very clever optimization because it ensures no extra CPU cycle would be needed as each data transfer can only be done for each line block.

There're many other optimisation examples, such as lazy evaluation in a loop, making sure the threads have work to do etc etc.

So, you see, a popular engine like Stockfish is highly optimised. The source code has been studied thoughtfully. I have every reason to believe Stockfish is the most optimised and efficient chess engine.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.