Iphone Chess Apps

[Tord Romstad]

About one year ago, I gave a one-hour lecture to my colleagues, where I explained how Glaurung's parallel search worked. The audience had rather mixed backgrounds, like mathematical logic, cognitive science, psychology, computer science, and plain software engineering. None of them had ever implemented alpha/beta before, although a couple of them recalled having seen the algorithm in textbooks. I explained negamax, alpha-beta pruning, and the importance of good move ordering, and why the most obvious ways to parallelize alpha/beta are very inefficient. I proceeded to explain YBWC and the helpful master concept, and how my implementation in Glaurung works. Nobody seemed to have any problems understanding the lecture. I got lots of intelligent and interesting questions, and even a few suggestions for possible improvements.

Listening to someone explain a parallel search is _FAR_ different from going out and implementing one yourself. Remember, I talk about this kind of stuff all the time. But when it comes assignment time, everything they understood and asked intelligent questions about in class disappears somehow. So someone sitting in the audience and nodding "yep. uh-huh, yepper, I see, etc does not mean they are going to be able to go out and actually deal with all the dozens of details necessary to do a parallel alpha/beta search.

My audience wasn't students, but my colleagues, most of whom are better programmers than me (which isn't surprising, as I have no formal training in programming or computer science). I work with them every day, and know them well enough to know when they have understood something well enough to implement it themselves.

I've done tons of parallel algorithms over the past 30 years, none come anywhere _near_ the complexity of a good parallel search.

A parallel search isn't even necessary for writing a strong chess program. I also don't agree that it's terribly difficult, as long as good speedup on a small (<= 4) CPUs is enough. A plain implementation of YBWC is just a couple of hundred lines of very straightforward C code.

I don't have much programming experience, but I think most of what I have done (mostly symbolic mathematics, knowledge-based engineering and computational geometry, and server software with huge workloads) feels much harder than chess engine programming.

I've done an othello project in an AI course several times. Othello is far simpler to program than chess since there are no irregular moves of any kind. And it turns into a significant programming project over the course of a semester. And it is trivial compared to chess.

I think othello doesn't differ significantly from chess in terms of difficulty. Chess is certainly more work, but not more difficult work. Othello is clearly better as a pedagogical exercise, as the extra work involved in chess has very little educational value from a programming point of view.

"hashing itself is understood" I would agree with. But using it to reduce the search effort, store best moves and then use them later, and such become complex details that nobody will have experience with the first time around.

I don't see how it is different from any other use of a hash table. It's just a matter of storing what you want to remember, and looking it up again when you need it.

If you are thinking about a case such as where a student can "live" in my office to ask questions, and develop a program quicker, I would agree with you. But if someone is not located where they have ready and instant access to have their questions answered one-on-one, then I believe the project becomes far more difficult...

Thanks to the Internet, everybody has ready and instant access to have their questions answered.

Again, the "null-move hypothesis" is pretty easy to grasp once it is explained. But implementing it in an alpha/beta recursive program is not exactly trivial the first time around without help.

It shouldn't take many minutes to find dozens of 20-line pseudocode listings of PVS with recursive null move pruning.

I have talked to _many_ strong chess players over the years that also program, and they always want to know how this is done. It seems logical and natural to me, but not to a chess player. "Why can't you consider what pieces are controlling that square?" and such questions. It is a very delicate balance of capability vs cost that experience helps to understand.

Remember that I am not talking about winning world championships, but about playing strong chess from a human perspective. You can get quite far with a very crude evaluation function. Material, mobility, passed pawns, king shelter and pawn structure is easily enough to get master-class strength.

I am not sure such knowledge can be transferred to a beginner at a 100% confidence level. Or even at a 50% confidence level. A good starting program is probably going to be at least 10,000 lines of code, and most newcomers have likely never written anything within a factor of ten of that size. The first compiler I wrote, as an undergraduate, was just under 2,000 lines total, comments and all...

10,000 lines of C code is a fairly small program by modern standards, but very big for a good starting chess program. Viper, the program I wrote to serve as a simple demonstration of YBWC a few years back, ways in at 4,600 lines of code, and it is actually far too complicated and contains lots of advanced stuff which should be removed (like special evaluation functions for KR vs KP). I think it would be easy to reduce the size by 50% without sacrificing more than 100 Elo points (the current version has strength comparable to Crafty 20.13 and Arasan 10 on the CCRL scale).

But how long have you been doing this is the question? Each new version gets easier and easier. But #1.0 is a challenge.

Each new version doesn't get easier, it just gets stronger. I use roughly the same amount of time each time I do a complete rewrite of my program, but every new program is stronger than its predecessor.

I don't have time to participate much more in this discussion, but it is all really so obvious that there is hardly any point in discussing it: Looking at the numbers is enough. There are hundreds of master-class chess engines, and just a handful of chess GUIs, despite the fact that hundreds of thousands of programmers around the world are taught UI design, and almost nobody is taught chess programming. Those of us who have done both (see also the post by HGM in a thread on a similar topic in the "Programming and Technical Discussions" sub-forum) generally agree that writing a GUI is much more difficult. Moreover, our GUIs are usually of a vastly inferior quality compared to our chess engines (and my own GUI, regrettably, is no exception).

Tord

[Tord Romstad]

I would also add that debugging chess programs is FAR harder than debugging most things. And ease of debugging often plays a larger role than anything else in how easy a task is.

Bugs in chess engines are also far easier to avoid than in most other types of software, for several reasons:

• The input is very regular and predictable, without any obscure border cases to worry about. Instead of interacting directly with a user and trying to gracefully handle all the weird things the user could decide to do, a chess engine only has to handle a small and regular set of commands from the GUI. Because broken input is defined as a GUI bug, no sophisticated error handling is required. This is also one of the reasons why chess GUI programming is difficult, of course.
• Hardly any dynamic memory managment: Almost all data structures are flat, fixed-size structs and arrays.
• No floating point computations, roundoff errors, or arbitrary-precision arithmetic with integers, rationals or other types of numbers. All arithmetic is done in the integers modulo 2^32 and 2^64, which are very easy to understand.

The most efficient way to do debugging of a chess program is, in my experience, not to do it at all. If something doesn't work, and it isn't immediately obvious why it doesn't work, the code is too complex, and should be simplified or decomposed into smaller and simpler parts. After I started following this philosophy, C programming is much less painful, and my code is a lot cleaner and easier to work with.

Tord

[Tord Romstad]

I can also point out that TSCP is significantly stronger than many engines out there. Considering that TSCP is open source, not much more than 1000 lines long without comments, not designed to be strong, and is used as a starting point by most people, you'd expect every engine to be stronger than TSCP but that isn't the case.

Also, since I license TSCP and Stobor, I've dealt with companies who try to make an engine in-house with their professional programmers, or contract out the work, and after a few months their project is still at a state where they're better off licensing TSCP. These people haven't heard the "myth" that chess programming is hard but maybe they should have.

They clearly don't know where to look for information. If they did, they would quickly discover that they wouldn't have to do any work whatsoever. They can just grab the source code of an existing engine with a liberal license (like mine) and adapt it to their needs.

Tord

[Tord Romstad]

Thank you.

My original intention was to write an Xboard/UCI/whatever interface for the iPhone and then bundle TSCP and Stobor with it, but you're right, that sort of thing is unfortunately strictly prohibited.

I have considered making a version of my engine and GUI for jailbroken phones (probably in addition to, and not instead of the version for non-jailbroken phones) in order to escape this problem. It would be great for testing the engine, even without any other UCI engines running natively on the iPhone. I could run automated matches between Glaurung on the iPhone and other engines running on a desktop computer, for instance.

I have been reworking Stobor's eval function and right now I assume tChess is somewhat weaker than Genius, but I think it's still much stronger than most of the other iPhone games and I will be releasing free strength updates for some time to come.

Sounds great.

Since automated testing isn't possible between iPhone chess games I have only run one match, between tChess and Caissa. That match took most of a day to run and I am not eager to repeat the experience.

It should be pointed out though that for the hardware and market we're talking about, almost any chess engine will be able to beat almost any human. More interesting to me is how "well" my program plays at the lower levels.

Yes, making a program play weak, but interesting chess is surprisingly difficult. I have a lot of work left to do in this area. Fortunately, because my program is free, I don't have to make the first iPhone version of Glaurung perfect in all ways. For the initial version, I will be happy with a simple but stable GUI and strength at least on the level of Genius.

Tord

[tomker]

I can also point out that TSCP is significantly stronger than many engines out there. Considering that TSCP is open source, not much more than 1000 lines long without comments, not designed to be strong, and is used as a starting point by most people, you'd expect every engine to be stronger than TSCP but that isn't the case.

Also, since I license TSCP and Stobor, I've dealt with companies who try to make an engine in-house with their professional programmers, or contract out the work, and after a few months their project is still at a state where they're better off licensing TSCP. These people haven't heard the "myth" that chess programming is hard but maybe they should have.

They clearly don't know where to look for information. If they did, they would quickly discover that they wouldn't have to do any work whatsoever. They can just grab the source code of an existing engine with a liberal license (like mine) and adapt it to their needs.

Tord

I did a quick Google search and it looks like your engine is GPL'ed. I would hardly call that license liberal. Anyone who wanted to use your engine would have to take great care to separate their interface from your code, otherwise they would also have to release their interface under the GPL (as a derivative work) and provide source code for it upon request. I used to work for a company that was involved in open source and it was always the biggest headache to try to design our code around that.

[tomker]

I would also add that debugging chess programs is FAR harder than debugging most things. And ease of debugging often plays a larger role than anything else in how easy a task is.

Bugs in chess engines are also far easier to avoid than in most other types of software, for several reasons:

• The input is very regular and predictable, without any obscure border cases to worry about. Instead of interacting directly with a user and trying to gracefully handle all the weird things the user could decide to do, a chess engine only has to handle a small and regular set of commands from the GUI. Because broken input is defined as a GUI bug, no sophisticated error handling is required. This is also one of the reasons why chess GUI programming is difficult, of course.
• Hardly any dynamic memory managment: Almost all data structures are flat, fixed-size structs and arrays.
• No floating point computations, roundoff errors, or arbitrary-precision arithmetic with integers, rationals or other types of numbers. All arithmetic is done in the integers modulo 2^32 and 2^64, which are very easy to understand.

The most efficient way to do debugging of a chess program is, in my experience, not to do it at all. If something doesn't work, and it isn't immediately obvious why it doesn't work, the code is too complex, and should be simplified or decomposed into smaller and simpler parts. After I started following this philosophy, C programming is much less painful, and my code is a lot cleaner and easier to work with.

Tord

Your philosophy doesn't address any of the hard bugs one encounters when chess programming, where you mistype a constant or offset or otherwise make a typo where the program will continue to run, and may even run quite well, except for the extremely rare cases where it crashes or plays a sub-optimal move because of some subtle memory corruption or an inaccurate term in eval. I had a bug in my MP search for years, which I only found and corrected last year, because of a simple oversight which caused the program to hang once every few weeks.

[bob]

About one year ago, I gave a one-hour lecture to my colleagues, where I explained how Glaurung's parallel search worked. The audience had rather mixed backgrounds, like mathematical logic, cognitive science, psychology, computer science, and plain software engineering. None of them had ever implemented alpha/beta before, although a couple of them recalled having seen the algorithm in textbooks. I explained negamax, alpha-beta pruning, and the importance of good move ordering, and why the most obvious ways to parallelize alpha/beta are very inefficient. I proceeded to explain YBWC and the helpful master concept, and how my implementation in Glaurung works. Nobody seemed to have any problems understanding the lecture. I got lots of intelligent and interesting questions, and even a few suggestions for possible improvements.

Listening to someone explain a parallel search is _FAR_ different from going out and implementing one yourself. Remember, I talk about this kind of stuff all the time. But when it comes assignment time, everything they understood and asked intelligent questions about in class disappears somehow. So someone sitting in the audience and nodding "yep. uh-huh, yepper, I see, etc does not mean they are going to be able to go out and actually deal with all the dozens of details necessary to do a parallel alpha/beta search.

My audience wasn't students, but my colleagues, most of whom are better programmers than me (which isn't surprising, as I have no formal training in programming or computer science). I work with them every day, and know them well enough to know when they have understood something well enough to implement it themselves.

I've done tons of parallel algorithms over the past 30 years, none come anywhere _near_ the complexity of a good parallel search.

A parallel search isn't even necessary for writing a strong chess program. I also don't agree that it's terribly difficult, as long as good speedup on a small (<= 4) CPUs is enough. A plain implementation of YBWC is just a couple of hundred lines of very straightforward C code.

I don't have much programming experience, but I think most of what I have done (mostly symbolic mathematics, knowledge-based engineering and computational geometry, and server software with huge workloads) feels much harder than chess engine programming.

I've done an othello project in an AI course several times. Othello is far simpler to program than chess since there are no irregular moves of any kind. And it turns into a significant programming project over the course of a semester. And it is trivial compared to chess.

I think othello doesn't differ significantly from chess in terms of difficulty. Chess is certainly more work, but not more difficult work. Othello is clearly better as a pedagogical exercise, as the extra work involved in chess has very little educational value from a programming point of view.

"hashing itself is understood" I would agree with. But using it to reduce the search effort, store best moves and then use them later, and such become complex details that nobody will have experience with the first time around.

I don't see how it is different from any other use of a hash table. It's just a matter of storing what you want to remember, and looking it up again when you need it.

If you are thinking about a case such as where a student can "live" in my office to ask questions, and develop a program quicker, I would agree with you. But if someone is not located where they have ready and instant access to have their questions answered one-on-one, then I believe the project becomes far more difficult...

Thanks to the Internet, everybody has ready and instant access to have their questions answered.

Again, the "null-move hypothesis" is pretty easy to grasp once it is explained. But implementing it in an alpha/beta recursive program is not exactly trivial the first time around without help.

It shouldn't take many minutes to find dozens of 20-line pseudocode listings of PVS with recursive null move pruning.

I have talked to _many_ strong chess players over the years that also program, and they always want to know how this is done. It seems logical and natural to me, but not to a chess player. "Why can't you consider what pieces are controlling that square?" and such questions. It is a very delicate balance of capability vs cost that experience helps to understand.

Remember that I am not talking about winning world championships, but about playing strong chess from a human perspective. You can get quite far with a very crude evaluation function. Material, mobility, passed pawns, king shelter and pawn structure is easily enough to get master-class strength.

I am not sure such knowledge can be transferred to a beginner at a 100% confidence level. Or even at a 50% confidence level. A good starting program is probably going to be at least 10,000 lines of code, and most newcomers have likely never written anything within a factor of ten of that size. The first compiler I wrote, as an undergraduate, was just under 2,000 lines total, comments and all...

10,000 lines of C code is a fairly small program by modern standards, but very big for a good starting chess program. Viper, the program I wrote to serve as a simple demonstration of YBWC a few years back, ways in at 4,600 lines of code, and it is actually far too complicated and contains lots of advanced stuff which should be removed (like special evaluation functions for KR vs KP). I think it would be easy to reduce the size by 50% without sacrificing more than 100 Elo points (the current version has strength comparable to Crafty 20.13 and Arasan 10 on the CCRL scale).

But how long have you been doing this is the question? Each new version gets easier and easier. But #1.0 is a challenge.

Each new version doesn't get easier, it just gets stronger. I use roughly the same amount of time each time I do a complete rewrite of my program, but every new program is stronger than its predecessor.

I don't have time to participate much more in this discussion, but it is all really so obvious that there is hardly any point in discussing it: Looking at the numbers is enough. There are hundreds of master-class chess engines, and just a handful of chess GUIs, despite the fact that hundreds of thousands of programmers around the world are taught UI design, and almost nobody is taught chess programming. Those of us who have done both (see also the post by HGM in a thread on a similar topic in the "Programming and Technical Discussions" sub-forum) generally agree that writing a GUI is much more difficult. Moreover, our GUIs are usually of a vastly inferior quality compared to our chess engines (and my own GUI, regrettably, is no exception).

Tord

I suspect that those that are interested in GUI development comprise a limited number of people compared to those that are interested in actually developing an AI application. Since everyone can trivially lash up their program to xboard /winboard and avoid the GUI issue altogether, I'd bet that is the reason for limited chess GUI development as compared to chess engine development.

[Gian-Carlo Pascutto]

IMO, asking for permission of the author is just a formality. If you couldn't care enough to have your project open source and have the whole world modify it and distribute it to their heart's content. Why should "asking before using it" be such a big deal?

There is no need to ask for permission to use Sjeng-Free's source code. It comes with a license (the GPL) describing exactly what you can and cannot do with it. If you redistribute something derived from it, you MUST distribute it with the COMPLETE source code.

They are not doing that. They only published Sjeng's source code, and not the one of the complete program (Sjeng + GUI). This makes their business COMPLETELY ILLEGAL. If you bought from them, you got scammed, and are contributing to piracy. Please contact Apple and ask for your money back.

When I complained about this, they removed the link to the (incomplete) source code and put a link to ask for it. Unfortunately this means it's now much more difficult to verify that they're in compliance or not. But given by their behavior, it's highly doubtful.

I repeat: DO NOT BUY THIS PROGRAM. By doing so, you are actively encouraging people to break the law and rip off somebody else's work for profit.

I am trying to get Apple to remove the illegal software from the webstore, but without much success so far. I guess they're not interested unless you show up with lawyers and sue them.

[Michel]

There is no need to ask for permission to use Sjeng-Free's source code. It comes with a license (the GPL) describing exactly what you can and cannot do with it. If you redistribute something derived from it, you MUST distribute it with the COMPLETE source code.

It is not a GPL violation if they are calling Sjeng command line (leaving aside possible other legal issues with the iPhone).

Are you claiming that they are not calling Sjeng command line? If so this is a blatant GPL violation and you should report it here.

http://gpl-violations.org/

These people have a lot of experience in handling GPL violations. Such violations occur very often in embedded systems.

Michel

[pavel]

IMO, asking for permission of the author is just a formality. If you couldn't care enough to have your project open source and have the whole world modify it and distribute it to their heart's content. Why should "asking before using it" be such a big deal?

There is no need to ask for permission to use Sjeng-Free's source code. It comes with a license (the GPL) describing exactly what you can and cannot do with it. If you redistribute something derived from it, you MUST distribute it with the COMPLETE source code.

They are not doing that. They only published Sjeng's source code, and not the one of the complete program (Sjeng + GUI). This makes their business COMPLETELY ILLEGAL. If you bought from them, you got scammed, and are contributing to piracy. Please contact Apple and ask for your money back.

When I complained about this, they removed the link to the (incomplete) source code and put a link to ask for it. Unfortunately this means it's now much more difficult to verify that they're in compliance or not. But given by their behavior, it's highly doubtful.

I repeat: DO NOT BUY THIS PROGRAM. By doing so, you are actively encouraging people to break the law and rip off somebody else's work for profit.

I am trying to get Apple to remove the illegal software from the webstore, but without much success so far. I guess they're not interested unless you show up with lawyers and sue them.

Hi GCP,
First, thanks for the excellent chess engine and making it available under GPL. 99 games has two chess program, "Chess lite" and "Chess Pro", chess lite is free which is what I use (as mentioned in the first post).

I am not going to argue about the GPL licensing because I think you guys know it better than I do.

But this is what I saw in one of the review on "chess lite" on the app store.



I can't verify any of these but I thought I would post it here since its relevant. The pro version doesn't mention anything about sjeng engine and someone mentioned castling is not possible on the pro version; but I can't verify it since I didn't buy it.

Hope this helps.