MTD(f) experiences

[Zach Wegner]

I think that the problem is we have lots of examples of strong programs that use pvs with source code available and zero that use MTD(f).

Perhaps there is a need for an MTD version of Glaurung?

Sigh. So many things to do, so little time. Sometimes I envy all those programmers who are content with just writing a chess engine.

Tord

Don't do it Tord!! I'd rather see a shogi or go engine, really. MTD(f) isn't that interesting to me.

I sympathize. I have tons of projects that I'd like to do, such as rewriting my Go program (maybe/partially in Lisp??). I only have so much I would like to do in chess, but I have spent an awful lot of time recently doing bugfixes and stuff that I could've put off for at least a few months, when I'd be done with my Summer of Code project.

But if you really want to satisfy those who need an MTD(f) program, how about releasing Gothmog?

[Dann Corbit]

I think that the problem is we have lots of examples of strong programs that use pvs with source code available and zero that use MTD(f).

Perhaps there is a need for an MTD version of Glaurung?

Sigh. So many things to do, so little time. Sometimes I envy all those programmers who are content with just writing a chess engine.

Tord

Don't do it Tord!! I'd rather see a shogi or go engine, really. MTD(f) isn't that interesting to me.

I sympathize. I have tons of projects that I'd like to do, such as rewriting my Go program (maybe/partially in Lisp??). I only have so much I would like to do in chess, but I have spent an awful lot of time recently doing bugfixes and stuff that I could've put off for at least a few months, when I'd be done with my Summer of Code project.

But if you really want to satisfy those who need an MTD(f) program, how about releasing Gothmog?

I always liked the search variant called {IIRC} C-Star, which uses mtd(f) like probing, but in a binary search rather than a linear search. There is something very appealing to me about that method.

[Guetti]

I think that the problem is we have lots of examples of strong programs that use pvs with source code available and zero that use MTD(f).

Perhaps there is a need for an MTD version of Glaurung?

Sigh. So many things to do, so little time. Sometimes I envy all those programmers who are content with just writing a chess engine.

Tord

I don't know how you do it, I don't even have time for that.
Since GTA IV took all my time away from programming in the past weeks.

[Dann Corbit]

I think that the problem is we have lots of examples of strong programs that use pvs with source code available and zero that use MTD(f).

Perhaps there is a need for an MTD version of Glaurung?

Sigh. So many things to do, so little time. Sometimes I envy all those programmers who are content with just writing a chess engine.

Tord

Don't do it Tord!! I'd rather see a shogi or go engine, really. MTD(f) isn't that interesting to me.

I sympathize. I have tons of projects that I'd like to do, such as rewriting my Go program (maybe/partially in Lisp??). I only have so much I would like to do in chess, but I have spent an awful lot of time recently doing bugfixes and stuff that I could've put off for at least a few months, when I'd be done with my Summer of Code project.

But if you really want to satisfy those who need an MTD(f) program, how about releasing Gothmog?

I always liked the search variant called {IIRC} C-Star, which uses mtd(f) like probing, but in a binary search rather than a linear search. There is something very appealing to me about that method.

Here is the citation I was thinking of:
"Experiments With The NegaC* Search An Alternative for Othello Endgame Search" by Jean-Christophe WEILL

[Zach Wegner]

I always liked the search variant called {IIRC} C-Star, which uses mtd(f) like probing, but in a binary search rather than a linear search. There is something very appealing to me about that method.

I thought that's what MTD(f) did? At least, when I was thinking about MTD(f), I would've done it that way.

Here was another thing I thought of doing, in case anyone else hadn't thought of it:
When doing the probes, use MTD(f) to get a score for only the first move, instead of searching all moves when the others will likely fail. Then the rest of the root node becomes like PVS.

[Dann Corbit]

I always liked the search variant called {IIRC} C-Star, which uses mtd(f) like probing, but in a binary search rather than a linear search. There is something very appealing to me about that method.

I thought that's what MTD(f) did? At least, when I was thinking about MTD(f), I would've done it that way.

Here was another thing I thought of doing, in case anyone else hadn't thought of it:
When doing the probes, use MTD(f) to get a score for only the first move, instead of searching all moves when the others will likely fail. Then the rest of the root node becomes like PVS.

MTD(f) does a linear search. I would guess that a good hash implementation would be essential, because the initial guess must be excellent for the method to prevail.

On the Nega-C* idea, I wonder if we could use a few trial searches and then do a curve projection to speed the search?

[Tord Romstad]

Perhaps there is a need for an MTD version of Glaurung?

Sigh. So many things to do, so little time. Sometimes I envy all those programmers who are content with just writing a chess engine.

Don't do it Tord!!

I probably won't. I could probably make a simple MTD version without much time and effort, but it would be much weaker than the normal version, and people would too easily conclude that MTD isn't good. Writing an MTD version of comparable strength to the PVS version would be a big task, and my time is probably better spent doing other things.

I'd rather see a shogi or go engine, really.

Go is unlikely, at least in the near future. It's a great game, but I can't stand watching the ugly games played by the current generation of go programs (and my own program would of course be far worse, especially in the beginning). Shogi is more attractive from this point of view, but it's a pity that there isn't much of a shogi programming community outside Japan.

In the nearest future, I'll have to concentrate on completing my chess evaluation function with space and development, adding bitbases, improve my GUI, and finish the iPhone port of Glaurung. Maybe I'll give shogi a try after that.

I sympathize. I have tons of projects that I'd like to do, such as rewriting my Go program (maybe/partially in Lisp??). I only have so much I would like to do in chess, but I have spent an awful lot of time recently doing bugfixes and stuff that I could've put off for at least a few months, when I'd be done with my Summer of Code project.

What's your Summer of Code project about?

But if you really want to satisfy those who need an MTD(f) program, how about releasing Gothmog?

Too embarrassing, and it wouldn't be useful to the community. It is too ugly and messy to be understandable, and not sufficiently strong to prove that MTD(f) is competitive.

I always liked the search variant called {IIRC} C-Star, which uses mtd(f) like probing, but in a binary search rather than a linear search. There is something very appealing to me about that method.

The advantage of progressing by tiny steps like in plain MTD(f) is that all searches except the first are usually very fast, because you get a huge number of hash cutoffs. This advantage mostly disappear if you do a binary search. In practice, I think most programs use a hybrid approach. Gothmog did this: At each iteration, it started with a plain MTD(f) search, but if the search failed in the same direction multiple times, it started gradually increasing the step size, before finally converging towards the right value by something similar to a binary search.

Tord

[Tord Romstad]

I think that the problem is we have lots of examples of strong programs that use pvs with source code available and zero that use MTD(f).

Perhaps there is a need for an MTD version of Glaurung?

Sigh. So many things to do, so little time. Sometimes I envy all those programmers who are content with just writing a chess engine.

I don't know how you do it, I don't even have time for that.

The secret is that once you have a complete and working engine, developing it further isn't that much work. When you have all the low-level functions in place, adding more knowledge and experimenting with new search techniques is fairly straightforward and doesn't take much time. The time-consuming thing is testing, but that can easily be done while you are doing something else.

Since GTA IV took all my time away from programming in the past weeks.

Fortunately, I hate playing games (this includes chess). Unfortunately, playing the viola is just as addictive, and takes just as much time.

Tord

[hgm]

Shogi is more attractive from this point of view, but it's a pity that there isn't much of a shogi programming community outside Japan.

Well, you can count me in! I have decided I am definitely going to write a Shogi engine. What I haven't decided yet is if I am going to write a Crazyhouse engine as an intermediate step. At least that is a game I have actually played (well, Bughouse, really, but that is close enough to have a feel for the strategy), and it would only be a matter of adding the piece drops to one of my existing engines.

Another question, as I know you like variants: have you ever considered equiping Glaurung with a capability to play Knightmate? It is so boring for JokerKM to be 350 Elo above all its competitors.

[Tord Romstad]

Shogi is more attractive from this point of view, but it's a pity that there isn't much of a shogi programming community outside Japan.

Well, you can count me in!

Great!

I have decided I am definitely going to write a Shogi engine.

Then I'll definitely have to do it, too -- and I'll better start quickly, because my program will probably be bigger than yours by a factor of 10 thousand, and will therefore require a much longer period of development.

What I haven't decided yet is if I am going to write a Crazyhouse engine as an intermediate step. At least that is a game I have actually played (well, Bughouse, really, but that is close enough to have a feel for the strategy), and it would only be a matter of adding the piece drops to one of my existing engines.

The disadvantage is that there is even less of an community for Crazyhouse.

Another question, as I know you like variants: have you ever considered equiping Glaurung with a capability to play Knightmate? It is so boring for JokerKM to be 350 Elo above all its competitors.

Would be fun. In principle it could probably be done in a minute or two, simply by swapping the arrays used for attack generation for kings and knights. Making it play decently would also require some changes in the evaluation function, but it still wouldn't be a lot of work. The only real problem is that I would also need a Knightmate compatible version of PolyGlot. I'm not sure how hard that would be.

Tord