Fastest chess?

[Mich Robinson]

Phil Freihofner wrote:

Mich Robinson wrote:I would actually love to write this in C just because C would give me a 10x speed increase but sadly no-one would be able to play the program unless they installed it and that is too big a sacrifice.

I presume that is a comment about your skill and knowledge of C programming vs your knowledge of Java programming. Well-formed Java is very fast, quite on a par with C. Certainly it is not 10x slower! From what I have read on this thread, your code is pretty monolithic and could probably perform much better using good Java practices. I recommend checking out the "Cattle Drive" here, for example, as a way to achieve this end.

The 10x figure was based more on another developers experience of taking their (quite strong) java program and turning it into an exe using a converter program. He found his program was examining 10x more positions as an exe than as a java program. Java is pretty fast and more than enough for what I need but it won't compete with a native executable.

Phil Freihofner wrote:Very cool that you got the game working so quickly! You might check out Ludum Dare competition, for Java games written within 48 hours.

Unfortunately it became a bit addictive and I've been working on it ever since with varying results so I doubt it qualifies for under 48 hours now! It still looks the same though. I may have the original code from that point though.

Phil Freihofner wrote:Congratulations on getting minmax working! That is no mean feat.

Minmax really isn't that difficult but sadly a chess program won't do well with only a minmax search as it's way too slow. Alphabeta is a much faster approach as it prunes much of the search tree you need to examine. Next you need to implement iterative deepening so you slowly increase the search depth but keep the score for each move tried then, at the next deeper level, you try the moves in score order. This improves the efficiency of the pruning. Next you need to implement move ordering at all levels - admittedly the scoring here is just a very rough estimate but it still helps. Next you want to continue searching beyond the maximum depth if the position is very volatile - this stops the program thinking it's made a gain after a 6ply search when, if it looked a little deeper, it would have actually lost material. I could go on. When I started this project I had no idea how far game programming had progressed since I first read about it - it's been quite educational for me.

[Phil Freihofner]

There is a very interesting book on programming: "Dreaming in Code". Worth checking out on multiple levels. (Terrific background history, for example: "the mother of all demos"!)

One take-away for me was that the programmers, some of the best in the industry, working on "Chandler" decided to use Python, but none were particularly versed in its idioms/idiosyncracies. When they finally hired a Python hotshot, several years into the project, he was taken aback at the inefficiencies in the code, and wrote a "famous" blog post about Python not being Java (as the programmers were writing Python code using Java best-practices). He was able to improve much of the code and get huge performance gains.

My take-away is that NOT taking the time to truly learn the language one is working in is like handicapping oneself needlessly. Even "legendary" programmers can be hampered by not learning best practices for the language they are working in.

The debate on programming speed goes on and on. A strong case is made, for example, that modern JIT processing surpasses compiled code in certain situations, and is the basis for Java being comparable to C. I'll leave it at that.

It's fun to play the Ludum Dare entries. You can sample some of them, and other Java games here:
http://www.java-gaming.org/boards/showcase/2/view.html

I have found JGO to be a very helpful forum for game programming, and recommend it highly.

[Mich Robinson]

Phil Freihofner wrote:There is a very interesting book on programming: "Dreaming in Code". Worth checking out on multiple levels. (Terrific background history, for example: "the mother of all demos"!)

One take-away for me was that the programmers, some of the best in the industry, working on "Chandler" decided to use Python, but none were particularly versed in its idioms/idiosyncracies. When they finally hired a Python hotshot, several years into the project, he was taken aback at the inefficiencies in the code, and wrote a "famous" blog post about Python not being Java (as the programmers were writing Python code using Java best-practices). He was able to improve much of the code and get huge performance gains.

My take-away is that NOT taking the time to truly learn the language one is working in is like handicapping oneself needlessly. Even "legendary" programmers can be hampered by not learning best practices for the language they are working in.

The debate on programming speed goes on and on. A strong case is made, for example, that modern JIT processing surpasses compiled code in certain situations, and is the basis for Java being comparable to C. I'll leave it at that.

It's fun to play the Ludum Dare entries. You can sample some of them, and other Java games here:
http://www.java-gaming.org/boards/showcase/2/view.html

I have found JGO to be a very helpful forum for game programming, and recommend it highly.

Java performance : JIT was a massive improvement to Java but it still doesn't compare to native code. Chess programmers in general do everything they can to speed up their programs - if it was faster to write the code in COBOL then they would convert their code instantly. There must be a reason that nearly all the strong programs are written in C++. I happen to like Java and wanted my program to play on the net - so Java was my natural choice.

Rewriting to improve things : Rewriting the code to improve the "style" is a neat thought but who would it please? I doubt users care how the program is written. I certainly feel comfortable with the current approach though I do acknowledge it's failings. Perhaps only hard core Java programmers who are interested in chess and who extract the code would care? Would it be worth the investment in time? or the risk of new bugs creeping in? Joel Spolsky wrote some interesting essays on how both Lotus and Netscape lost their position simply by "improving the code" rather than adding extra functionality.

Dreaming in code : The book you mention describes a large project that never gets anywhere. 4 years into the build and there's still nothing to ship. One reviewer felt that one guy working in his spare time could of done a better job. I'm not sure what you intend me I learn from this book. I often take over projects where developers and PMs have become intoxicated with technology but sort of forgotten what's required. I think I'll happily accept any inadequacies I might have in Java standards as long as I can continue to get the goods out the door - hopefully I'll absorb these better methods as I go.

Our own experiences : The style of programming I use for writing board games hasn't much changed from the approach I took when writing games in machine code 30 years ago. I'm certain the code in your chess program would look better than mine and more closely resemble accepted standards. But, at the end of the day, my program plays a reasonable game of chess and I believe your program has still yet to make a move. I am impressed by anyone who attempts to write a chess program though - you soon realise that rocket science is pretty simple in comparison

I've just released a new version Fun Chess 17.1 which plays much stronger and also allows you to copy and paste PGN game histories (or FEN descriptions). Please give it a try if you have a free moment and say what you think.

[Phil Freihofner]

I hope you don't take my comments in the wrong way. They come from my personal experience, and the limited info I was able to glean from reading this thread. I came to Java only two years ago with a background largely in VBA and VisualBasic.Net & a smattering of C++. I found that my first attempts to write Java code based upon this experience had very mixed results, to say the least, and that as I learn more about Java, the effectiveness of the code increases dramatically.

I certainly don't mean to say one should risk making changes for cosmetic or stylistic reasons for their own sake. Along those lines, I'm not entirely clear on the pros and cons of using statics. But I do know that it took about 18 months before I started being able to make positive use of the excellent knowledge and suggestions in "Effective Java" by J. Bloch, and am still working to better understand the underlying memory model & how the JVM works. I'm currently working through a book on Refactoring, and checking out a book "Write Great Code, vol.2: Thinking low-level, writing high-level" as an ongoing investment in expanding my skills. As you have considerable assembly coding experience, you are probably far ahead of me in this regard. At the assembly-code level, I've only had a course in University (PDP11!)and about a year or two with FORTH and helping with some Z-80 and 8080, when I was game programming on CPM machines in the early 1980's.

"Dreaming in Code" worked for me as a book because it has some excellent history. But also as a list of "blind spots" that programmers are subject to. I've always taken to heart the classic philosophy advice "Know thyself!" Knowing where one is likely to err due to self-inflicted and thus correctable shortcomings seems to me a very valuable plus. Along those lines, it seems it is very common for programmers to try to apply what they are comfortable with and know is effective in one environment, and apply it to another situation where it can be less than optimal. The "warning flags" that led me to consider this might be the case for you were the comments about monolithic code by others, and by your assessment of Java being 10x slower than C++ compiled code. They indicated the *possibility* of a blind spot and of a self-fulfilling prophesy. But of course, you are the best judge of the reliability of the co-worker who gave you his/her estimate, and of your own coding abilities and Java experience. I meant no disrespect!

I don't plan to spend time with chess or go or other alphabeta/AI issues in the near future. My current interest is primarily with game sound and music, which has its own high-performance challenges, and detractors who say Java is not up to the task. I do recall having good luck with advancing from the use of ArrayLists in search trees to converting to more finely honed collections such as HashLists and HashSets, on an exhaustive tree-search algorithm for puzzle program I wrote, and for a Boggle emulator, where new knowledge led to refactoring and use of superior tree algorithms.

The Ludum Dare suggestion was more to alert you to the existence of this competition in the case that you like the 48-hour challenge aspect, not meant for your current chess program.

At Java-gaming.org there are some very interesting posts, concerning performance issues that you might enjoy perusing. An example of data-driven programming, using "fast-objects" by the poster Riven is very intriguing. These folks are often concerned with issues pertaining to 3D and various engines, but some might be transferable.

Best wishes and best of success to you!

[Mich Robinson]

Phil Freihofner wrote:I hope you don't take my comments in the wrong way.

Sorry Phil, I think I was being a bit too defensive. You spend so long with a program that it almost becomes like another child. Interesting to see someone else use FORTH - I remember writing a Forth compiler (actually a threaded language interpreter) for an Acorn Atom computer - it was certainly a very interesting language.

I did have a look at the Dare competition but they want you to write new code in 48 hours - I can imagine being stuck in a sweaty cellar full of 20 year olds consuming nothing but coffee - it gives me the shudders! It wouldn't be too bad if they were all pretty girls but I suspect they'd all be male. On the positive side I did find am old copy of my 48 hour chess so I put that on the web for comparison.

Good luck with your music software and remember to post a link.

Mike