Iphone Chess Apps

[pavel]

Hi pavel, gang,

Tom Kerrigan here, author of TSCP, Stobor, and now tChess for the iPhone.

Hi Tom, of course we remember you. it's good to see you back here. I will definitely try out tChess over the weekend, it sounds very interesting. I will probably also end up getting Genius. Gotta support the developers!!

Cheers.

[bob]

Writing an interface is easy for an experienced programmer but writing a good chess program from scratch is extremely difficult.

Actually, it's the other way around. I've done both in Mac OS X, and writing a chess engine is at least an order of magnitude easier. On the iPhone, the difference is even bigger. Designing a good interface for the tiny screen and finger input is a very difficult task.

Tord

I don't agree, for several reasons. First, 99.99% of programmers have absolutely no idea how alpha/beta works. That's a handful by itself. Not to mention the ancillary stuff like hashing, extensions and reductions, how/what to evaluate, etc.

I wrote a working version of Crafty, starting dead from scratch, in a month and had it playing on ICC. Lacked significant features such as null-move and so forth, but it worked. I've done X-windows applications and found that easy to do. And while I don't think chess is an impossibly difficult task, for a first-timer it is most certainly non-trivial. So for me, writing a program from scratch is an easy task. But I've only been doing this for just a hair over 40 years now so it should be. But starting from scratch, with no alpha/beta/minimax experience of any kind, this is not for the casual one hour a week programmer.

[Tord Romstad]

I think they are all very different skills: UI programming, UI design, and chess engine programming. I think you are taking the latter for granted. I have a friend who's working on a strategy game. He is good at UI design and has quickly mastered the iPhone API, but now he's trying to write the AI for his game and his questions have really opened my eyes to how much knowledge is involved in writing something like a chess engine. (Or an engine for anything.)

This is a flawed example, because your friend was already good at UI design.

I also think you're taking for granted the amount and depth of resources someone has today when starting out with chess engine programming. There are many web pages and sites about it today, and many open source engines, including my tutorial engine TSCP. When I started in ~1994, it was WAY more difficult to get information about how to write an engine. It's nice that everything is in place now for it to SEEM easy to make an engine.

It doesn't just seem easy, it is easy. You are certainly right that the reason it has become easy is the work of pioneers in the past, and that the knowledge that we now possess was not easily achieved. Nevertheless, the knowledge exists, and is easy to acquire and implement.

I wonder if you've tried tChess Pro?

I haven't, but perhaps I will when I find some time. Honestly, I am not very interested in using chess programs written by others (except as sparring partners for my own program), but mostly in writing my own programs.

Tord

[Tord Romstad]

Writing an interface is easy for an experienced programmer but writing a good chess program from scratch is extremely difficult.

Actually, it's the other way around. I've done both in Mac OS X, and writing a chess engine is at least an order of magnitude easier. On the iPhone, the difference is even bigger. Designing a good interface for the tiny screen and finger input is a very difficult task.

Tord

I don't agree, for several reasons. First, 99.99% of programmers have absolutely no idea how alpha/beta works.

Even if we assume that your 99.99% figure is right (I think it is way too high, and should be closer to 90%), it doesn't change much. Alpha/beta is trivial to explain and understand.

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.

Of course, the reason why alpha/beta now seems trivial is the hard work done by you and other pioneers. Most brilliant new ideas are very hard to grasp in the beginning, but gradually become easier when they become better understood and the presentation is polished. As an example, consider the cartesian coordinate system -- arguably one of the most brilliant and important ideas in the history of science -- which seems totally obvious today, and which is now taught to children in elementary school.

That's a handful by itself. Not to mention the ancillary stuff like hashing,

Hashing is a technique all programmers are already familiar with. Moreover, the hash tables used in conventional chess programs are particularly simple (fixed size, very simple hashing function). Again, this is of course because of the work done by others. Inventing the idea of Zobrist hashing is hard, but understanding and implementing it is extremely simple.

extensions and reductions,

Extend checks and use recursive null move pruning, and you already have a very fast and efficient search, with very little effort.

how/what to evaluate, etc.

This is more about chess knowledge than about programming knowledge. It would be hard work for someone who doesn't know anything about chess, but such people probably wouldn't be interested in writing a chess program in the first place.

And while I don't think chess is an impossibly difficult task, for a first-timer it is most certainly non-trivial.

It is non-trivial, but no more than moderately difficult (assuming that the goal is to write a master-strength program, and not to win the world championships).

So for me, writing a program from scratch is an easy task. But I've only been doing this for just a hair over 40 years now so it should be.

Yes, but because you have generously shared the knowledge you have obtained through your 40 years of experience, the younger generation can learn everything in a tiny fraction of the time.

But starting from scratch, with no alpha/beta/minimax experience of any kind, this is not for the casual one hour a week programmer.

I have always been a casual one hour a week programmer, and I am fairly sure most other amateur chess programmers also are.

Tord

[tomker]

I wonder if you've tried tChess Pro?

I haven't, but perhaps I will when I find some time. Honestly, I am not very interested in using chess programs written by others (except as sparring partners for my own program), but mostly in writing my own programs.

Tord

Yet this doesn't seem to prevent you from calling Genius "by far the best available iPhone chess program at the moment."

[bob]

Writing an interface is easy for an experienced programmer but writing a good chess program from scratch is extremely difficult.

Actually, it's the other way around. I've done both in Mac OS X, and writing a chess engine is at least an order of magnitude easier. On the iPhone, the difference is even bigger. Designing a good interface for the tiny screen and finger input is a very difficult task.

Tord

I don't agree, for several reasons. First, 99.99% of programmers have absolutely no idea how alpha/beta works.

Even if we assume that your 99.99% figure is right (I think it is way too high, and should be closer to 90%), it doesn't change much. Alpha/beta is trivial to explain and understand.

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. I've done tons of parallel algorithms over the past 30 years, none come anywhere _near_ the complexity of a good parallel search.

I believe the same is true for hashing, null-move, reductions, extensions, evaluation, and goes all the way down to the very low-level details dealing with generating moves and making/unmaking them, etc...

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.

Of course, the reason why alpha/beta now seems trivial is the hard work done by you and other pioneers. Most brilliant new ideas are very hard to grasp in the beginning, but gradually become easier when they become better understood and the presentation is polished. As an example, consider the cartesian coordinate system -- arguably one of the most brilliant and important ideas in the history of science -- which seems totally obvious today, and which is now taught to children in elementary school.

That's a handful by itself. Not to mention the ancillary stuff like hashing,

Hashing is a technique all programmers are already familiar with. Moreover, the hash tables used in conventional chess programs are particularly simple (fixed size, very simple hashing function). Again, this is of course because of the work done by others. Inventing the idea of Zobrist hashing is hard, but understanding and implementing it is extremely simple.

"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.

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...

extensions and reductions,

Extend checks and use recursive null move pruning, and you already have a very fast and efficient search, with very little effort.[/quote]

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.

how/what to evaluate, etc.

This is more about chess knowledge than about programming knowledge. It would be hard work for someone who doesn't know anything about chess, but such people probably wouldn't be interested in writing a chess program in the first place.

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.

And while I don't think chess is an impossibly difficult task, for a first-timer it is most certainly non-trivial.

It is non-trivial, but no more than moderately difficult (assuming that the goal is to write a master-strength program, and not to win the world championships).

So for me, writing a program from scratch is an easy task. But I've only been doing this for just a hair over 40 years now so it should be.

Yes, but because you have generously shared the knowledge you have obtained through your 40 years of experience, the younger generation can learn everything in a tiny fraction of the time.

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...

But starting from scratch, with no alpha/beta/minimax experience of any kind, this is not for the casual one hour a week programmer.

I have always been a casual one hour a week programmer, and I am fairly sure most other amateur chess programmers also are.

Tord

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

[BubbaTough]

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.

-Sam

[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.

[Tord Romstad]

I wonder if you've tried tChess Pro?

I haven't, but perhaps I will when I find some time. Honestly, I am not very interested in using chess programs written by others (except as sparring partners for my own program), but mostly in writing my own programs.

Tord

Yet this doesn't seem to prevent you from calling Genius "by far the best available iPhone chess program at the moment."

Sorry about that -- I wasn't aware of the existence of your program at the time. As a punishment for myself, I just bought your program.

tChess doesn't feel quite as strong as Genius so far, but as my impression is still only based on two games, I may still change my mind. Do you have any test results?

It's a pity that Apple's strict rules for iPhone applications makes it impossible to write a GUI for UCI engines. It would be fun to run automatic matches between our engines...

Tord

[tomker]

I wonder if you've tried tChess Pro?

I haven't, but perhaps I will when I find some time. Honestly, I am not very interested in using chess programs written by others (except as sparring partners for my own program), but mostly in writing my own programs.

Tord

Yet this doesn't seem to prevent you from calling Genius "by far the best available iPhone chess program at the moment."

Sorry about that -- I wasn't aware of the existence of your program at the time. As a punishment for myself, I just bought your program.

tChess doesn't feel quite as strong as Genius so far, but as my impression is still only based on two games, I may still change my mind. Do you have any test results?

It's a pity that Apple's strict rules for iPhone applications makes it impossible to write a GUI for UCI engines. It would be fun to run automatic matches between our engines...

Tord

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 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.

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. Of course raw strength is still critical for any analysis features.