Simple NULL move enhancement, checks in qsearch

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Simple NULL move enhancement, checks in qsearch

Postby mjlef » 14 Apr 2006, 21:06

For programs using NULL pruning close to the qsearch which also include checks in qsearch, make sure you set your depth high enough to catch at least one ply of checking moves in the qsearch.

For example, if you only do checks at depth=0 in the qsearch and you are at say depth=2 now, with R=3, that wpuld make the new depth 2-3-1 = -2. Better set the depth at 0 to include those checks (that might be mates or other wins). I see a few public domain sources that do not do this, and can miss mate threats. I see no search explosion, and it does solve some mate threat purning problems.

Mark
mjlef
 
Posts: 64
Joined: 29 Mar 2006, 22:04

Re: Simple NULL move enhancement, checks in qsearch

Postby Uri Blass » 14 Apr 2006, 21:54

when the depth is not positive I simply call the qsearch that is a different function so there is no difference if the depth is 0 or negative.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Simple NULL move enhancement, checks in qsearch

Postby Tord Romstad » 14 Apr 2006, 23:14

mjlef wrote:For programs using NULL pruning close to the qsearch which also include checks in qsearch, make sure you set your depth high enough to catch at least one ply of checking moves in the qsearch.

For example, if you only do checks at depth=0 in the qsearch and you are at say depth=2 now, with R=3, that wpuld make the new depth 2-3-1 = -2. Better set the depth at 0 to include those checks (that might be mates or other wins). I see a few public domain sources that do not do this, and can miss mate threats.


Hi Mark,

I suspect my program is one of those you are thinking about. Actually it does always search checks at the first ply of the qsearch, even if the depth is -(2*PLY). However, when I look at this part of my code again now, I see that the code is potentially confusing and can give the impression that checks are not searched in such cases. I should try to clean this up before I release the next version. Thanks for reminding me.

By the way, I am happy to see an old top programmer like you post in this forum. Are you still working on your program, and is there any hope that we will see a new public version soon?

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: Simple NULL move enhancement, checks in qsearch

Postby mjlef » 15 Apr 2006, 08:21

Hi Tord,

Thanks. I have not worked on my chess program in about 10 years, concentrating on the universal game program "Zillions of Games" instead. It plays most any board game, and I found it a challenge trying to come up with a search and evaluation based simply on the rules of the game and board topology. It plays pretty well.

Recently, talking with my friend Frederic Friedel I heard about some advances in computer chess (amateur programs suddenly getting a lot stronger) so I started looking at my old program. I found it still runs pretty fast (and it is 16 bit code an Pascal!). Many of the new ideas were based on the old idea of reducing depth in cetain conditions. The history reduction idea was clever and worth a try so I guess I am back in. I need to work on something better than the old Borland Pascal compiler I used. I just downloaded freepascal and will see if I can use that. Might speed things up and give me more memory to play with.

Thanks for your encouragement.

Oh, in the past I tried most everythng, so if anyone wants my advice, let me know.

Mark
mjlef
 
Posts: 64
Joined: 29 Mar 2006, 22:04

Re: Simple NULL move enhancement, checks in qsearch

Postby Tom King » 15 Apr 2006, 21:15

mjlef wrote:Hi Tord,

Thanks. I have not worked on my chess program in about 10 years, concentrating on the universal game program "Zillions of Games" instead. It plays most any board game, and I found it a challenge trying to come up with a search and evaluation based simply on the rules of the game and board topology. It plays pretty well.

Recently, talking with my friend Frederic Friedel I heard about some advances in computer chess (amateur programs suddenly getting a lot stronger) so I started looking at my old program. I found it still runs pretty fast (and it is 16 bit code an Pascal!). Many of the new ideas were based on the old idea of reducing depth in cetain conditions. The history reduction idea was clever and worth a try so I guess I am back in. I need to work on something better than the old Borland Pascal compiler I used. I just downloaded freepascal and will see if I can use that. Might speed things up and give me more memory to play with.

Thanks for your encouragement.

Oh, in the past I tried most everythng, so if anyone wants my advice, let me know.

Mark


Mark Lefler as in the chess program "Now"? Or should I call it "Then" if you haven't been around a while ;-)

I used to use Now as a sparring partner for my program way back before useful things like Winboard were invented.

Welcome back! I took a two year "sabbatical" from computer chess, but am back tinkering again. Like you, I think the buzz around things like Fruit, Rybkha and new techniques such as the history pruning stuff have got my creative juices flowing again (in the very limited free time I have).
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: Simple NULL move enhancement, checks in qsearch

Postby diepeveen » 16 Apr 2006, 00:33

Tom King wrote:
mjlef wrote:Hi Tord,

Thanks. I have not worked on my chess program in about 10 years, concentrating on the universal game program "Zillions of Games" instead. It plays most any board game, and I found it a challenge trying to come up with a search and evaluation based simply on the rules of the game and board topology. It plays pretty well.

Recently, talking with my friend Frederic Friedel I heard about some advances in computer chess (amateur programs suddenly getting a lot stronger) so I started looking at my old program. I found it still runs pretty fast (and it is 16 bit code an Pascal!). Many of the new ideas were based on the old idea of reducing depth in cetain conditions. The history reduction idea was clever and worth a try so I guess I am back in. I need to work on something better than the old Borland Pascal compiler I used. I just downloaded freepascal and will see if I can use that. Might speed things up and give me more memory to play with.

Thanks for your encouragement.

Oh, in the past I tried most everythng, so if anyone wants my advice, let me know.

Mark


Mark Lefler as in the chess program "Now"? Or should I call it "Then" if you haven't been around a while ;-)

I used to use Now as a sparring partner for my program way back before useful things like Winboard were invented.

Welcome back! I took a two year "sabbatical" from computer chess, but am back tinkering again. Like you, I think the buzz around things like Fruit, Rybkha and new techniques such as the history pruning stuff have got my creative juices flowing again (in the very limited free time I have).


Just skip history pruning i'd say and read what Mark has to say.
I remember Mark and NOW very well. Great days those were!

Note in diep every ply in qsearch is the same. However that's pretty pricey compared to Mark's suggestion. What mark is saying is basically what i used to do in diep before 2001 or so (i can't recall at this hour the exact year i changed it whether that was 1998-2002, some year at least that i had a discussion there with Andrej Dados and/or Peter Gillgasch there).

Vincent
diepeveen
 
Posts: 116
Joined: 28 Jun 2005, 01:09
Location: Netherlands

Re: Simple NULL move enhancement, checks in qsearch

Postby mjlef » 16 Apr 2006, 10:15

Well thanks! You made my day. I kind of retired from chess programming years ago when NOW score the same number of points as Fritz in a tournament (maybe AEGON..I am not sure). I figured I would never top that.

I really need to get winboard working with NOW. I wonder if anyone has some sample pascal or c code I could look at. only have a few old programs I can autoplay with and would like to expand that. I downloaded the free pascal compiler, but it has problems finding the system unit. Hmmm. Well I will figure it out eventually. In old 16 bit NOW I was always running out of memory space for clever tricks I wanted to do. Once I get this working, it should be no problem.

OK, some experiments I want to do (maybe you all have the same ideas and some data). When does history reduction fail? Ideas:

a. Create a program that logs number of attempts history pruning is done at each depth, and number of failures, to see if the fail rate is dependant on depth. Also log the number of the move that was found in the resulting research. This might give information to tune it (is the Fruit /Toga rule of pruning the 4th and higher legal moves good, or should that number vary by depth?)

b. Log the history ratios used and once again compare with failures. A chart could be made indicating relative reduction risk based on varying percentages by different depths.

Mark
mjlef
 
Posts: 64
Joined: 29 Mar 2006, 22:04

Re: Simple NULL move enhancement, checks in qsearch

Postby Tord Romstad » 16 Apr 2006, 10:54

mjlef wrote:I really need to get winboard working with NOW.


You might want to have a look at the newer UCI protocol instead. You can find it in the download section at the Shredder homepage. The UCI protocol is somewhat less flexible than the XBoard protocol in some ways, but it is much easier to implement. These days, UCI engines can easily be used in Winboard, thanks to Fabien Letouzey's excellent PolyGlot adapter.

I wonder if anyone has some sample pascal or c code I could look at.


There are a lot. A reasonably complete list of open source Winboard and UCI engines can be found here. Most of these are in C or C++. I don't know them well enough to give any useful advice about which one(s) would be best to look at.

My own UCI code is very simple and compact, but I don't have any support for Winboard.

OK, some experiments I want to do (maybe you all have the same ideas and some data). When does history reduction fail? Ideas:

a. Create a program that logs number of attempts history pruning is done at each depth, and number of failures, to see if the fail rate is dependant on depth. Also log the number of the move that was found in the resulting research. This might give information to tune it (is the Fruit /Toga rule of pruning the 4th and higher legal moves good, or should that number vary by depth?)


I have tried lots of such experiments, but I have never found anything that works better than reducing beginning with the 4th move at all depths (except in the last two plies before the horizon, where I don't reduce at all).

My program doesn't only play normal chess, but also hexagonal chess, which has a much higher branching factor. To my surprise, it seems that reducing from the 4th move is the optimal setting there as well.

b. Log the history ratios used and once again compare with failures. A chart could be made indicating relative reduction risk based on varying percentages by different depths.


This could be interesting, but my experience is that history ratios are not a very useful criterion for reductions.

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: Simple NULL move enhancement, checks in qsearch

Postby Tord Romstad » 16 Apr 2006, 11:02

mjlef wrote:Hi Tord,

Thanks. I have not worked on my chess program in about 10 years, concentrating on the universal game program "Zillions of Games" instead. It plays most any board game, and I found it a challenge trying to come up with a search and evaluation based simply on the rules of the game and board topology. It plays pretty well.


I didn't know you were part of the ZoG team. Being a Mac user, I can't use your program, but based on what I have read about it it looks like a very remarkable achievement. I consider it to be a much more impressive piece of software than any normal chess program.

Since some time, I have considered writing a somewhat similar, but much less ambitious program myself. My idea is to write a program which lets the user define the rules of a chess-like game, and which outputs the C source code for a program for playing this game.

Oh, in the past I tried most everythng, so if anyone wants my advice, let me know.


Thanks! I hope you'll stay around.

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: Simple NULL move enhancement, checks in qsearch

Postby mjlef » 16 Apr 2006, 13:41

You might want to have a look at the newer UCI protocol instead. You can find it in the download section at the Shredder homepage. The UCI protocol is somewhat less flexible than the XBoard protocol in some ways, but it is much easier to implement. These days, UCI engines can easily be used in Winboard, thanks to Fabien Letouzey's excellent PolyGlot adapter.

>>

Thanks. Looks easy enought o implement.

Is there a good public domain UCI display program/auto tester you would recommend? What I have done in the past is have a set of say 50 standard openings. The auto player lets each program play once as white and once as black, with the game reuslts going in a file. I have a simple utility to tally the results. What is everyone using now (back in the ealry 90's, me and other prrogrammers just came with with a scheme using files).
mjlef
 
Posts: 64
Joined: 29 Mar 2006, 22:04

Re: Simple NULL move enhancement, checks in qsearch

Postby mjlef » 16 Apr 2006, 13:46

[quote="Tord Romstad"][quote="mjlef"]

>>

I didn't know you were part of the ZoG team. Being a Mac user, I can't use your program, but based on what I have read about it it looks like a very remarkable achievement. I consider it to be a much more impressive piece of software than any normal chess program.

>>
We started off with dual Mac and PC development (Microsoft had a compile they said could do both), but the Mac market was not big enough. Maybe someday.

>>
Since some time, I have considered writing a somewhat similar, but much less ambitious program myself. My idea is to write a program which lets the user define the rules of a chess-like game, and which outputs the C source code for a program for playing this game.

>>

ZOG supports external engines for any game (very simple format using DLL calls). If you ever write something like this, it would be cool. You could use the Zillions Rules Files to let people write a game, then your utility could compile it on the fly. It would run a lot faster, though our node rate is not too bad.
mjlef
 
Posts: 64
Joined: 29 Mar 2006, 22:04

Re: Simple NULL move enhancement, checks in qsearch

Postby Tord Romstad » 16 Apr 2006, 14:22

mjlef wrote:Thanks. Looks easy enought o implement.


Yes, it is really easy, especially when you consider that you don't have to implement all features at once. You can safely omit things like Multi-PV mode and fixed-node searches in the beginning (actually I think rather few UCI engines support those).

Is there a good public domain UCI display program/auto tester you would recommend?


I am probably not the right person to ask, because I don't run Windows. The most popular UCI compatible GUIs for Windows seem to be Arena (free), Fritz (and other programs from ChessBase, it seems they all use the same GUI) and Shredder. I know that Arena supports engine vs engine matches (and multi-engine tournaments), I am not sure about the others.

You can also use Winboard to run UCI engines, with the PolyGlot adapter, which can be found at the WBEC site. The Winboard+PolyGlot combination requires somewhat more technical competence to get running and tends to look a bit less pretty than the alternatives, but has the advantage of being fast, light-weight and stable.

It would be nice to have a non-GUI tool for running automated matches between UCI and/or Winboard engines, but unfortunately such a program does not yet exist (at least not in the public domain).

What I have done in the past is have a set of say 50 standard openings. The auto player lets each program play once as white and once as black, with the game reuslts going in a file. I have a simple utility to tally the results. What is everyone using now (back in the ealry 90's, me and other prrogrammers just came with with a scheme using files).


That's basically what I do, too. I use XBoard (which is essentially exactly the same as Winboard, except that it runs in the X Window System) and PolyGlot for this. XBoard does not have any built-in facilities for running a match from a pre-defined set of positions, but it allows you to select a single initial position at startup (by a command line argument). What I do is to use a small Python program which loops through my 50 opening position, and starts XBoard once for each position.

There are probably easier ways to do this in other GUIs.

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: Simple NULL move enhancement, checks in qsearch

Postby Tord Romstad » 16 Apr 2006, 14:27

mjlef wrote:ZOG supports external engines for any game (very simple format using DLL calls).


This sounds interesting. If I understand correctly, this means that I should be able to port my hexagonal chess engine to ZOG? This would be really nice, because my current GUI is for Mac OS X only. My program is fairly strong (at least I have never won or drawn against it), and the most recent version even supports 2 CPUs.

If you ever write something like this, it would be cool. You could use the Zillions Rules Files to let people write a game, then your utility could compile it on the fly. It would run a lot faster, though our node rate is not too bad.


OK, I'll let you know if I do it. Don't hold your breath, though - I have too many other things to work on. At the moment I am having a break from chess programming, and when I start again my first priority will be to make a GUI which works on the new Intel Macs.

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: Simple NULL move enhancement, checks in qsearch

Postby GeoffW » 16 Apr 2006, 23:50

Hi Mjlef

If you are looking for a GUI, I really like Chess Arena

http://www.playwitharena.com/

Nice features are

1) Free :D
2) supports UCI and Winboard
3) Has its own tournament manager (and manages lots of engines too)
4) Supports Round Robin, Swiss, Gauntlet tourneys
5) If you want to do some testing with fixed openings that is easy to set up too, plays alternate white then black games from a pgn you specify. You can also set how many moves it plays from the pgn file before switching to engine moves
6) it looks pretty nice too, customisable interface
7) Tournament results are available as a web page table, no messing with files or utiliites to see results
8) Supports lots of time controls

Avoid the latest beta as personally I thought that was a backward step, version 1.1 is fine though

Regards Geoff
GeoffW
 
Posts: 37
Joined: 01 Oct 2004, 18:36

Re: Simple NULL move enhancement, checks in qsearch

Postby mjlef » 17 Apr 2006, 09:14

Tord Romstad wrote:
mjlef wrote:ZOG supports external engines for any game (very simple format using DLL calls).


This sounds interesting. If I understand correctly, this means that I should be able to port my hexagonal chess engine to ZOG? This would be really nice, because my current GUI is for Mac OS X only. My program is fairly strong (at least I have never won or drawn against it), and the most recent version even supports 2 CPUs.


Yep, pretty easy. See this link:

http://www.zillionsofgames.com/progsample.html

Someone also wrote winboard plug in, so if anyone wants to use ZIllions of Games as the display/control for their engine, it should be easy:

http://www.zillionsofgames.com/progsample.html

Oh, there are lots of Hex chess variants (and other hex games) on our site. Here is a search for "hex":

http://www.zillionsofgames.com/cgi-bin/ ... chgame=hex
mjlef
 
Posts: 64
Joined: 29 Mar 2006, 22:04

Re: Simple NULL move enhancement, checks in qsearch

Postby mjlef » 17 Apr 2006, 09:16

Sounds perfect! Thanks!
mjlef
 
Posts: 64
Joined: 29 Mar 2006, 22:04

Re: Simple NULL move enhancement, checks in qsearch

Postby Ross Boyd » 18 Apr 2006, 11:05

That's basically what I do, too. I use XBoard (which is essentially exactly the same as Winboard, except that it runs in the X Window System) and PolyGlot for this. XBoard does not have any built-in facilities for running a match from a pre-defined set of positions, but it allows you to select a single initial position at startup (by a command line argument). What I do is to use a small Python program which loops through my 50 opening position, and starts XBoard once for each position.

There are probably easier ways to do this in other GUIs.


Hi Tord,

Always interesting to hear how the successful programmers go about their engine testing....

Testing is absolutely critical to gauge improvement... and it is horrendously time consuming. Fabien emphasises testing one change at a time. This requires excrutiating patience and an equally exquisite amount of intuition about which factors to test.... I bet there are a few developers who can identify with the difficulties I'm talking about.

I was using Arena to run tournaments to gauge progress but lost faith in it
. Admittedly, I was running only 150 game gauntlets and this is just not enough to get any accuracy (especially after studying Joseph's statistics).

Now I'm writing scripts to automate Winboard+Polyglot tournaments on my home network. One machine is the tournament controller and has a generated text file with all the proposed games to be played. Each workstation polls this shared file to get instructions on what game to run next. Using this topology I can add work stations (at any time) and with little or no effort have them churning out results.

Over the long weekend I built a 4th PC to add to my 'humungous' :D network. I think 10 PC's is probably about the sweet spot... so a 500 game gauntlet can be played reasonably quickly to test a new engine version.

I get the impression that Winboard is somehow fairer in sharing CPU cycles but I could be sincerely mistaken. WB is certainly faster and less resource hungry.

I figure the best way to get a consistent test environment is to write it myself and de-couple dependance on GUI's that I don't have control over.

Btw, keep up the great work with Glaurang... its not that far from the top now. :-)

Ross
User avatar
Ross Boyd
 
Posts: 83
Joined: 26 Sep 2004, 23:07
Location: Wollongong, Australia

Re: Simple NULL move enhancement, checks in qsearch

Postby Tord Romstad » 18 Apr 2006, 13:21

Hi Ross,

First of all, I would like to inform all readers that I won't be able to read any posts in this or other threads during the next three weeks. I'm leaving for a 3-week holiday in less than half an hour.

Ross Boyd wrote:Testing is absolutely critical to gauge improvement... and it is horrendously time consuming. Fabien emphasises testing one change at a time. This requires excrutiating patience and an equally exquisite amount of intuition about which factors to test.... I bet there are a few developers who can identify with the difficulties I'm talking about.


Yes. I have never been very patient, and never test changes very carefully. I am also frustrated that my test results usually turn out to be confusing, contradictory and non-reproducible.

Now I'm writing scripts to automate Winboard+Polyglot tournaments on my home network. One machine is the tournament controller and has a generated text file with all the proposed games to be played. Each workstation polls this shared file to get instructions on what game to run next. Using this topology I can add work stations (at any time) and with little or no effort have them churning out results.


That sounds nice. Unfortunately I have only one computer (but with two CPUs) available for testing right now, and because I use it for other purposes as well I can't let it run test matches 24 hours/day.

I get the impression that Winboard is somehow fairer in sharing CPU cycles but I could be sincerely mistaken. WB is certainly faster and less resource hungry.


I can't say much about that, because I have almost no experience with other GUIs. I am mostly happy with XBoard, except that it is terribly annoying that it jumps to the top of the desktop for each new game (remember that I run XBoard numerous times from a script, looping through a list os positions).

I figure the best way to get a consistent test environment is to write it myself and de-couple dependance on GUI's that I don't have control over.


Some type of command-line tool like the one I described earlier in the thread? That would be really cool. I hope to write such a program myself some day, but of course there are countless other projects which compete about my rather limited programming time.

Btw, keep up the great work with Glaurang... its not that far from the top now. :-)


Thanks! Trace is also gettting rather strong. :)

I don't expect to spend much (if any) time on Glaurung in the next half year or so, but I'm sure I'll start working on it again some time in the future.

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: Simple NULL move enhancement, checks in qsearch

Postby Uri Blass » 18 Apr 2006, 20:34

Tord Romstad wrote:Hi Ross,

First of all, I would like to inform all readers that I won't be able to read any posts in this or other threads during the next three weeks. I'm leaving for a 3-week holiday in less than half an hour.

Ross Boyd wrote:Testing is absolutely critical to gauge improvement... and it is horrendously time consuming. Fabien emphasises testing one change at a time. This requires excrutiating patience and an equally exquisite amount of intuition about which factors to test.... I bet there are a few developers who can identify with the difficulties I'm talking about.


Yes. I have never been very patient, and never test changes very carefully. I am also frustrated that my test results usually turn out to be confusing, contradictory and non-reproducible.

Now I'm writing scripts to automate Winboard+Polyglot tournaments on my home network. One machine is the tournament controller and has a generated text file with all the proposed games to be played. Each workstation polls this shared file to get instructions on what game to run next. Using this topology I can add work stations (at any time) and with little or no effort have them churning out results.


That sounds nice. Unfortunately I have only one computer (but with two CPUs) available for testing right now, and because I use it for other purposes as well I can't let it run test matches 24 hours/day.

Tord


Unfortunately my situation is even worse.

I use only one computer with one cpu for testing and most of the time it is not used for testing.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Simple NULL move enhancement, checks in qsearch

Postby Tom Likens » 18 Apr 2006, 20:45

Ross Boyd wrote:Now I'm writing scripts to automate Winboard+Polyglot tournaments on my home network. One machine is the tournament controller and has a generated text file with all the proposed games to be played. Each workstation polls this shared file to get instructions on what game to run next. Using this topology I can add work stations (at any time) and with little or no effort have them churning out results.

Ross

Hello Ross,

Are you running Windows or Linux? Also how do you ensure that the conditions are the same from test to test? What I mean, is how do you ensure that the experimental versions use equal CPUs, memory etc., so that you're making an apples to apples comparision?

regards,
--tom
Tom Likens
 
Posts: 41
Joined: 27 Oct 2004, 05:03

Next

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 4 guests

cron