self deepening: an improved implementation of IID

[Gerd Isenberg]

Michael,
sorry i don't get your problem exactly. Please consider we are all more or less egomanic individuals with limited time. For instance you can't expect help by posting pages of source code and begging to explain why it doesn't it work as expected. Search is so complicated and full of side effects - for some IID seem to work for some it don't works at all - same for a lot of other search related stuff.

Cheers,
Gerd

[Michael Sherwin]

deleted

[bob]

Sorry but that is a lousy attitude: "Stop what _you_ are doing, such as getting ready for the upcoming WCCC in 2 weeks, and look at my code, figure out what is wrong with it, and fix it."

We get into computer chess programming because we like it. And we do it ourselves. We discuss "ideas" all the time, but I have never, (and never would) post my source and say "this has a bug, please fix it for me" or "I can't get this parallel search to work, please make it work for me" or "I can't get IID to work, look at my source and fix it."

It isn't a "20-minute task" (your words). It might be a 48 hour task. It took me quite a bit of time to get it working acceptably in my program... If I had nothing else to do, I might be willing to look at someone's code for a few hours to see what they were doing and try to help, but most of us don't have hours to throw away, particularly with the WCCC looming large...

Your search might (or might not) have something unique that someone could learn from. I would doubt it based on the number of years of experience combined of the people in this forum. Throwing a tantrum is hardly going to produce help...

[diepeveen]

This bantering back and forth between big shots is not helping this little shot very much -- okay, I really mean, not at all. I have tried 100+ times to add IID to RomiChess to no avail and I have begged and pleaded for help with this. So far, thanks to no one for any help at all. So for those of you that believe in IID, then Romi would be an ideal test subject to prove your point. Or maybe Romi can not benifit from IID and maybe Diepeveen can determine and explain why. As for me I have no clue, as I am only a colege drop out that does not even remember how to spell coledge, college, that some how managed to write a chess program that is aproaching 2500 Elo at some sites. If Romi has a strength or weakness then I assume that Romis' eval is poor and that Romis' search is quite good. Romi can search deeper than most programs. So how about it guys anyone feel like giving stupid little me a hand and use RomiChess as an example. The source is at Leos' WBEC web site.

If you use the iterative deepening search very efficient then of course you will research the same search space over and over again. This is extremely efficient. IID won't work in that case.

If you however mess up for whatever reason taking care you don't search in the same search space each iteration, then iterative deepening will be very inefficient and IID will work.

There is many factors that can influence the search space you're looking at. Extensions especially, nullmove, forward pruning, qsearch and evaluation function and effectiveness of hashtable, to just name a few.

When iterative deepening becomes inefficient it might be an idea to just skip iterations, just like junior is doing already for years.

Vincent

Vincent

[Tom Likens]

Hi Gerd,

Out of 6,000,000,000+ people on this planet I had hoped that there might be one person that could take 20 minutes of their time to look at Romis' rather simple source and at least give a suggestion or two. I wonder if anyone knows that Romi achives the depths that she does with out using history tables for move ordering. My code is very original and I am sure that there is something in there that others could benifit from -- if they have not already. It is not like I am not offering anything in return. But I guess that a bunch of egomainiacs would have nothing to learn from someone like me. So I suppose that I can count you out.

Regards,
Mike

Michael,

Please, try and relax a bit. Remember this is a hobby for most people. If you're not enjoying it, stop doing it. Vincent, Gerd and Bob are usually more than happy to offer advice, but ultimately it's *your* program so you need to make the changes to it. Occasionally, someone will be kind enough to look your code over and point out potential problems or new ideas to try, but that only happens rarely. Most of the people who post here are *very* busy and fixing someone else's chess program is *not* a quick trivial thing.

regards,
--tom

[diepeveen]

Hi Gerd,

Out of 6,000,000,000+ people on this planet I had hoped that there might be one person that could take 20 minutes of their time to look at Romis' rather simple source and at least give a suggestion or two. I wonder if anyone knows that Romi achives the depths that she does with out using history tables for move ordering. My code is very original and I am sure that there is something in there that others could benifit from -- if they have not already. It is not like I am not offering anything in return. But I guess that a bunch of egomainiacs would have nothing to learn from someone like me. So I suppose that I can count you out.

Regards,
Mike

Michael,

Please, try and relax a bit. Remember this is a hobby for most people. If you're not enjoying it, stop doing it. Vincent, Gerd and Bob are usually more than happy to offer advice, but ultimately it's *your* program so you need to make the changes to it. Occasionally, someone will be kind enough to look your code over and point out potential problems or new ideas to try, but that only happens rarely. Most of the people who post here are *very* busy and fixing someone else's chess program is *not* a quick trivial thing.

regards,
--tom

Tom, don't worry, i understand very well his concern.

He makes something open source and the reality of the world is that open source nearly never gets improved nor modified by others. Note that several guys look in such code, but they all keep their mouth shut bigtime.

I know that feeling quite a lot.

Additional helping people improve open source is not easy. I've tried to report bugs in all kind of open source software i use.

Sometimes that is very succesful such as the filezilla server and client software. It is a free open source ftp server for windows and a very good client. Look it up!

I tried to report bugs for GCC and other open source projects. If you just 'report' bugs, you already get a big mouth back from: "i do this in my spare time bla bla, we are just 15 volunteers bla bla, and if you find bugs, fix them yourself".

Of course the first 10 emails being: "there is no bug, because it doesn't crash here at my home".

Or: "why don't you figure out the exact bug that GCC produces at diep's source code?".

Or you get completely ignored for 10 years. I remember Linus and Cox, especially the latter apologize himself: "this is not my job to fix all those issues, i just run this list".

In general projects run by many people, they just improve if there is a commercial incentive to improve.

Many other projects are programmers on their own, who are very dissappointed that when there is other projects which are 1% more well known, that all the people that DO contribute a little, that they are at that other project and not helping YOU.

The fundamental mistake that people make is that if you publish open source, that you get helped by the 'community'. The problem is that it is not easy to build a community around you.

Being a professor and being for nearly 12 years the strongest open source project until Fruit was there, and being in specint2000, which meant suddenly the person in question got all kind of support from persons from big companies who will 100% sure help the person in question less when he gets kicked out of specint2006.

It's hard to compete with that. The few persons that DO help some open source projects also usually get the bill presented.

I won't quote any names, but there is plenty. I helped several programs in past. Some of them have litterary returned zero useful input to me with respect, yes not even saying 'thank you' for the insight what to improve in their engine.

Lucky that's a minority.

But they are there.

I remember another statement from Frans Morsch very well. A few years ago he told me: "by god please don't post all that, please let them all get bitboards and figure out those search and eval details themselves, it's difficult to improve the engine in that case. It will be real difficult for others to become strong now as you need to be a hell of a programmer in first place when using bitboards.".

He is so so so so right.

After Bruce Moreland stopped joining, I met just 1 real good programmer last X years. He became world champion in 2005. Basically confirming Frans' point. At the same time there is Fruit now.

A single non-bitboard open source engine called Fruit, and soon after we get an entire new generation of 'amateur' programs where Frans was so afraid for, namely playing away every cloth he has. Just Fruit inspires so so many to improve their engine. It's not very well optimized in anyway this Fruit.

Everyone guesses: "if fruit can kick butt, and i can easily read that source code, so can i".

It is way harder to indicate what the power is from Crafty than to indicate why Fruit plays so strong. Fruit is a very tiny engine. Crafty a very big monster whose code is difficult to read for most.

There we have the next big problem of Romi. There is a bunch of open source engines, i mentionned already 2, which are stronger than Romi.

The help that others received in past over the years, Romi will probably not get, because of the recent experience with Rybka.

p.s. History tables don't work for Diep either, despite that i experimented recently again for months with them. Just look what moves get favoured by those primitive tables and you'll realize why some simplistic table inside Diep is already improving upon that.

Global killers also hardly work for diep. Local killers do work great. But if i would kick out killers in diep, it still would order quite well.

So Michael don't worry, but keep in mind that if you're from USA trying to compete with Bob, that "winner takes it all". This sucks bigtime, i agree.

Move to Europe i'd say.

Vincent

[diepeveen]

Hi Gerd,

Out of 6,000,000,000+ people on this planet I had hoped that there might be one person that could take 20 minutes of their time to look at Romis' rather simple source and at least give a suggestion or two. I wonder if anyone knows that Romi achives the depths that she does with out using history tables for move ordering. My code is very original and I am sure that there is something in there that others could benifit from -- if they have not already. It is not like I am not offering anything in return. But I guess that a bunch of egomainiacs would have nothing to learn from someone like me. So I suppose that I can count you out.

Regards,
Mike

Mike,

If you like to receive help, i hope you realize Bob has 1 major advantage over you. First of all all his source code carries a GPL header. Clearly indicating the project state of Crafty.

Secondly, Bob is a professor. I know if i put my source code on his machine, he won't steal it. Yes, not even take a look.

I know that 20 years from now, Bob still is busy improving crafty without being busy to convert crafty into a commercial project. So any help you give, you give to a GPL project in that case.

With Bob, any help you give is transparant. It moves into the GPL crafty project.

How about you?

I just see:
"Interests: chess, tennis, girls, prophecy"

Will Romi be open source if you kick butt in world champs 2007?

Introduce yourself i'd say. This is the first time i heard that Romi chess is open source by the way. Thanks for mentionning it.

Vincent

[Volker Pittlik]

...
If you like to receive help, i hope you realize Bob has 1 major advantage over you. First of all all his source code carries a GPL header. Clearly indicating the project state of Crafty...

Vincent, would you please be so kind to stop this sort of posts?

They are

a) obviously wrong

b) Within the last years personal attacks haven't been tolerated in this forum. I don't see a reason to change this now.

Volker

[Gerd Isenberg]

Hi Mike,
well i can understand your frustration. I allways hate to read other people's source code. Of course i had a look to Fruit (a bit closer) and Crafty. Crafties code was too "dense" for me and did not fit my "esthetical" taste
I think the lesson from fruit was using asserts a lot and steady eval.
So i don't promise anythink - i will have look to your source during the next weeks/months after WCCC.

Be patient and keep on posting and sharing your ideas with us

Cheers,
Gerd

[diepeveen]

...
If you like to receive help, i hope you realize Bob has 1 major advantage over you. First of all all his source code carries a GPL header. Clearly indicating the project state of Crafty...

Vincent, would you please be so kind to stop this sort of posts?

They are

a) obviously wrong

b) Within the last years personal attacks haven't been tolerated in this forum. I don't see a reason to change this now.

Volker

Volker, if you read well, then you see it is not a personal attack at Mike at all.

I just mention that a doctor or professor setting up an open source project has a huge advantage. Nothing personal intended.

If someone has helped many open source projects, then it's me.

So no personal incentives.

Just interpret my posting correct please.

It is a general comments, not a personal comments to crack him down.

[Michael Sherwin]

deleted

[Michael Sherwin]

deleted

[Michael Sherwin]

deleted

[H.G.Muller]

Michael, why do you think you would need IID in your engine? I use IID in uMax because, being a 100-line engine, it cannot afford any intrinsic move ordering at all. So obviously, without IID it would go depth-first on stupid moves very often, and would waste huge amounts of search efforts there before finding the cut move.

Trying to implement something that you might not need at all, and trying to judge from the overall performance if the implementation was successful, seems the wrong approach. You should first figure out how much there really is to gain.

So I suggest you first run some tests to determine how much your current search tree deviates from the optimal one. Let each search call pass towards the root the number of essential nodes that had to be searched. For a cut node this is the number of essential nodes from the search of the cut move plus one (for the current node). For other nodes is is the sum of the essential nodes for all moves, plus one. Do this for a search with a window that only contains the final score that the search will come up with (that you determine first through a search with an open window). This simulates optimal aspiration of the window. Any search would have to search at least that number of nodes (for the given search depth), or it would skip nodes that might have influenced the score.

If the number of actual nodes your search visits is not much higher than this number of essential nodes, you know there is not much to gain from better move ordering, and hence from IID. Best do both counts without allowing hash hits, to eliminate (possibly unpredictable) effects of the hash table: it is OK to use the hash-table moves, but do not use the scores for returning in case of sufficient depth, but just continue the search to get the node count.

[Michael Sherwin]

deleted

[Michael Sherwin]

deleted

[diepeveen]

Hi Gerd,

Thanks, I feel a little better now! I hope that you do well at WCCC.

Everyone does.

Perhaps he can again manage some opponent to bury his knight volunteerly on a1

[bob]

Hi Gerd,

Out of 6,000,000,000+ people on this planet I had hoped that there might be one person that could take 20 minutes of their time to look at Romis' rather simple source and at least give a suggestion or two. I wonder if anyone knows that Romi achives the depths that she does with out using history tables for move ordering. My code is very original and I am sure that there is something in there that others could benifit from -- if they have not already. It is not like I am not offering anything in return. But I guess that a bunch of egomainiacs would have nothing to learn from someone like me. So I suppose that I can count you out.

Regards,
Mike

Mike,

If you like to receive help, i hope you realize Bob has 1 major advantage over you. First of all all his source code carries a GPL header. Clearly indicating the project state of Crafty.

Secondly, Bob is a professor. I know if i put my source code on his machine, he won't steal it. Yes, not even take a look.

I know that 20 years from now, Bob still is busy improving crafty without being busy to convert crafty into a commercial project. So any help you give, you give to a GPL project in that case.

With Bob, any help you give is transparant. It moves into the GPL crafty project.

I don't quite agree with that. I can think of several things people have sent to me to test, and it _never_ made it into anything public. Peter G (dark thought, later some other program) talked to me about trying "one legal move" and later "one sane response/move" which I put into Cray Blitz, tested, even used for a while, but never released.

Bruce and I worked on his "simple-singluar-extension" idea several years back and I never released that code until after he had said it was OK to do so...

The fact that you are not aware of some of these things I have been involved in suggests that what I am saying is true...

How about you?

I just see:
"Interests: chess, tennis, girls, prophecy"

Will Romi be open source if you kick butt in world champs 2007?

Introduce yourself i'd say. This is the first time i heard that Romi chess is open source by the way. Thanks for mentionning it.

Vincent

I've given up on the idea of helping others with the expectation of getting help back. Time and time again, this has become a one-way street as others become commercial after finding some new useful idea, where they decide it is time to stop "telling all". It's just become a part of the culture. I've learned to live with it easily enough..

[bob]

Hi Diepeveen,

Thank you so much for your words. They are very helpful in determining the 'nature of the beast'. And helpful in understanding some things about programming chess. It is also helpful to know that there is someone of your stature that feels about history tables the way I do. As far as IID I am at the point where I will just have to assume that what I do with move ordering is better than the way Bob does it and that IID is not needed in Romi. This has been a confidence builder for me to read your words and I guess that I will just have to blaze my own trail thru the chess programming wilderness. Bob says he doubts that there is anything that he (or anyone else -- implied) can learn from Romis' source. A God like attitude and a good reason why the once great Crafty has been steadily slipping down the tournament tables for years now. Maybe he should just retire to mount Olympus and throw lightning bolts at the rest of us. When I read on the CCC forum the war between you and Bob I was shocked and appauled and then when it appeared in this thread I just wanted to expose the selfish nature of the people involved. Job done. At the CCC forum I originally felt that you were the bad guy, now I am not so sure. At least you refrained from personal attacks and wrote something helpful. As for Bob and WCCC why is he here if WCCC is so important and so close, shouldn't he be concentrating on getting Crafty ready?

A couple of points.

(1) _YOU_ made the ugly post complaining "hey, nobody will help me, why not?" I explained pretty concisely since your post had a lousy tone. As does this one, but that's your problem to deal with, not mine.

(2) You need to look in a mirror. Before you complain about my response to your post, you ought to look at your post with an honest eye. Then go read the story about "the pot and the kettle" and figure out what that means. You will become wiser and less obnoxious once you do.

For the record, I _am_ working on Crafty daily right now. And I am able to multi-task and read/post here and at CCC while waiting on test results to complete.

It's past time to grow up...

[Michael Sherwin]

deleted