Not logged inRybka Chess Community Forum
Up Topic Rybka Support & Discussion / Rybka Discussion / Old CCC archives
- - By Rebel (****) Date 2013-09-04 15:31
For a better understanding who wrote what in the early days of Rybka I merged the old CCC postings of Sean Mintz of 2003 into one file for a better research. I type "Vasik" and Vas' first post on CCC appeared. Then I copy the message number [ 332204 ] to see the whole thread of Sean Mintz web-site. Doing so here is Vas first message and the reply is almost prophetic, it simply had to be.

Lemme know if anyone is interested, I can put 2003, 2004, 2005 and 2006 for download.

http://www.stmintz.com/ccc/index.php?id=332204

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Subject: 3 fold rep - are there no actual rules?!
From: Vasik Rajlich
E-mail: xxxxxxxx
Message Number: 332204
Date: November 30, 2003 at 10:32:26

It's hard to believe that after thirty+ years of computer chess tournaments this
situation isn't covered in the rules.

Personally I'd like to see the operator have the choice. Then the egos can get
involved, which at least makes for better theater, for example

Van der Wiel,J (2560) - Karpov,A (2750) [C92]
World Cup Rotterdam, 1989

1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.0-0 Be7 6.Re1 b5 7.Bb3 d6 8.c3 0-0 9.h3
Re8 10.Ng5 Rf8 11.d4 Bb7 12.Nf3 Re8 13.Ng5 Rf8 14.Nf3 Re8 15.Ng5 Rf8 16.Nf3 Re8
17.Ng5 Rf8 18.Nf3 Na5 19.Bc2 Nc4 20.b3 Nb6 21.Nbd2 Re8 22.dxe5 dxe5 23.Nxe5 Bd6
24.Nef3 Bxe4 25.Nxe4 Nxe4 26.Qd3 f5 27.Be3 Bf8 28.Rad1 ݭݍ

------------

Subject: Re: 3 fold rep - are there no actual rules?!
From: Robert Hyatt
E-mail: xxxxxxxx
Message Number: 332255
Date: November 30, 2003 at 12:52:55
  In Reply to: 3 fold rep - are there no actual rules?!
  Message ID: 332204
  Posted by: Vasik Rajlich
  At: xxxxxxxxxxxxxxxx
  On: November 30, 2003 at 10:32:26

On November 30, 2003 at 10:32:26, Vasik Rajlich wrote:

>It's hard to believe that after thirty+ years of computer chess tournaments this
>situation isn't covered in the rules.


It is.  Human rules apply except where specific computer rules supercede them.
For example, computers play under "blind human" rules.  That means they have
an operator to move the pieces, but the operator is _passive_ and can offer no
help nor make any decisions.

>
>Personally I'd like to see the operator have the choice. Then the egos can get
>involved, which at least makes for better theater, for example
>
>Van der Wiel,J (2560) - Karpov,A (2750) [C92]
>World Cup Rotterdam, 1989
>
>1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.0-0 Be7 6.Re1 b5 7.Bb3 d6 8.c3 0-0 9.h3
>Re8 10.Ng5 Rf8 11.d4 Bb7 12.Nf3 Re8 13.Ng5 Rf8 14.Nf3 Re8 15.Ng5 Rf8 16.Nf3 Re8
>17.Ng5 Rf8 18.Nf3 Na5 19.Bc2 Nc4 20.b3 Nb6 21.Nbd2 Re8 22.dxe5 dxe5 23.Nxe5 Bd6
>24.Nef3 Bxe4 25.Nxe4 Nxe4 26.Qd3 f5 27.Be3 Bf8 28.Rad1 ݭݍ

Parent - By Rebel (****) Date 2013-09-04 15:39
Vas' 3th post is interesting.

Message Number: 338249

Maybe I underestimate the size of a really good eval. (Mine is about 4 months old.)

Vas
Parent - By Rebel (****) Date 2013-09-04 21:15
http://www.stmintz.com/ccc/index.php?id=345143

On January 26, 2004 at 21:14:22, Volker Richey wrote:

>Hi,
>
>Does u knows something about the unknown engines
>Bodo and/or Rybka.
>
>Volker


Hi Volker,

Rybka is my program. I would be happy to answer any questions. At the moment I
am very busy with some last-minute changes, I hope that tonight I will make it
to ICC finally for some testing/demonstration games. (Have null modem cable, and
instructions from Thomas Mayer for auto232.) The account there as you know is
"Rybka".

Also, small info update: for the CCT I'll be using a P4 3 GHz with 1 G RAM.
Rybka searches with a variation of MTD (f) with 24 byte hash entries, and hashes
all nodes, and at the moment doesn't rehash, so the hash table for this time
control should probably be somewhere around 512 MB?! This needs to be checked -
I'll send another update later.

Best regards,
Vas
Parent - By Rebel (****) Date 2013-09-04 21:35
http://www.stmintz.com/ccc/index.php?id=357652

Subject: Re: MTD(f) improvement?
Author: Vasik Rajlich

Date: 02:03:27 04/01/04

On March 31, 2004 at 20:02:26, Dann Corbit wrote:

>http://www.ipsj.or.jp/members/SIGNotes/Eng/29/2003/010/article001.html


Any way to get the paper? There are no email addresses there.

Anyway, 3% is consistent with what I have found. The key to MTD (f) is a good
fail soft - ie. dealing with all the "minor" issues, such as failing soft in
quiescence, failing soft on null move, failing soft with lazy eval, failing soft
on hash table hits. Once fail soft works, the choice of driver doesn't seem to
matter much.

Vas
Parent - By Rebel (****) Date 2013-09-04 21:37
http://www.stmintz.com/ccc/index.php?id=357933

Hi Uri,

One general comment: I've also had the idea to do both MTD (f) and PVS. Now I
realize that this is not feasible. Too many things are different.

The same holds true for a number of issues. Are you going to be essentially
selective, or essentially brute force? Are you going to be fast, or intelligent?

It makes sense to experiment a bit when you are starting, but I think you're
past that point.

Good luck.

Vas
Parent - By Rebel (****) Date 2013-09-04 21:39
http://www.stmintz.com/ccc/index.php?id=357934

Tord,

I thought you do this yourself (ie SEE rather than qsearch) when the position at
the start of qsearch meets certain criteria. (ie is quiet enough)

Qsearch is an ugly method.

One point is that it throws the balance of the search out of whack. At every
node, the remaining depth is search's way of specifying the importance of that
node, and the resources which it deserves. Depth == 0 means the node deserves no
resources and is not important - yet qsearch may then step in and decide to give
it more resources, not because it's important, but because it's messy.

I haven't been able to get rid of it, but I suspect the key issue is move
ordering - with qsearch your hash table moves are much better. In MTD (f) this
is really important
, because better move ordering gives you better fail soft -
if you fail high with a bad move, there's a good chance you'll eventually need
to re-search.

It may be that qsearch vs SEE should be chosen according also to how important
the node is for future move ordering.

Vas
Parent - By Rebel (****) Date 2013-09-04 21:52
http://www.stmintz.com/ccc/index.php?id=358630

This is absolutely correct. Good fail soft has a lot of subtle points, and you
just discovered one of them.

If you use PVS, then according to various stuff I've read here fail soft does
not offer any serious improvement over fail hard.

In MTD (f), fail soft is extremely important.

However, your idea, which I also have implemented, is even then still not
especially important. Usually, when you fail high, you are failing purely with
an open-ended bound. (Ie score to +infinity - or another way to say it is that
you can only set the lower bound.) There are some rare exceptions to this,
mainly from the q-search.

So, when you fail low at the next iteration, you generally are failing low with
another open-ended bound. (Ie -infinity to score, or only upper bound.) The
exceptions to this are when you had failed high with a true bound in q-search,
or when you had previous bound information.

Both are extremely rare.

I would suggest you first decide whether you will use PVS or MTD (f). This will
determine how much work fail soft merits.

Vas
Parent - By Rebel (****) Date 2013-09-04 22:04
http://www.stmintz.com/ccc/index.php?id=364893

Yes, this is normal, and it's the reason why MTD (f) is a reasonable alternative
to PVS
. The search is really good at doing the minimum amount of work.

Just glancing at the logs from my last run (I use MTD (f)), I see that 100% of
the fail-lows at the maximum depth returned the exact bounds value, and 73.3% of
the fail-highs did so.

These numbers are normal. It's also normal for soft fail-highs to be softer than
soft fail-lows, even at big remaining depths. (It's obvious why it should be so
at remaining depth == 0, but it also holds true throughout the search.)

Vas
Parent - By Rebel (****) Date 2013-09-04 22:06
Need more of such Bob?

Did Vas had his own MTD(f) version or not?
Parent - By Lukas Cimiotti (Bronze) Date 2013-09-05 07:22
Thank you, this is really interesting. :smile:
Parent - - By user923005 (****) Date 2013-09-05 07:40
From 2000, discussions about storing 2 bounds in both MTD(f) and non-MTD(f) searches{it is not just Vas and Fabian who found it useful}:
http://www.stmintz.com/ccc/index.php?id=143234
Smells like prior art to me.

From 2004 Vas and Fabian discussing MTD(f) at length.  Vas is the teacher here, IMO.  Of course, Fabian is a blazing fast learner:
http://www.stmintz.com/ccc/index.php?id=377240

A word about code and structures.
Once you have decided on a struct to hold the hash data (the bag of valuable goo tacked onto the hash code) the access routines write themselves.
You will have a set and a get for each atom in the struct/class.
After all, you store what? Depths, bounds, scores, and the left over part of the hash, ages, flags --> everybody puts pretty much the same stuff in them {though some store the whole hash -- a bit wasteful}.
So don't act all that shocked if the stuff that reads and writes to the hash looks rather similar.  Think about it, for goodness sake.
Parent - - By user923005 (****) Date 2013-09-05 07:47
1990:
Leen Ammeraal tries two bounds, not sure if he wants to use them or not:
http://www.stmintz.com/ccc/index.php?id=143435
Leen's last post on the topic, a bit later:
http://www.stmintz.com/ccc/index.php?id=143436
"I think things are actually more complicated if you
store two bounds and only one depth. I am now implementing
storing a depth for each of the bounds (lower, upper).
Leen Ammeraal"

Bo Persson says it works great for him:
http://www.stmintz.com/ccc/index.php?id=143545

Dave Gomboc uses two bounds, but in Awari:
http://www.stmintz.com/ccc/index.php?id=143653
Parent - - By bob (Gold) Date 2013-09-05 17:31
You miss key points.

1.  aging.  everybody doesn't do it the same way.

2.  Fruit and Rybka have FOUR depth values stored.  Not just two.

3.  replacement is done dozens of different ways.

4.  we are not talking "looks rather similar".  We are talking "looks rather identical".
Parent - - By user923005 (****) Date 2013-09-05 19:26
1.  aging.  everybody doesn't do it the same way.
No, but there are only a few distinct ways.
Direct replacement, with no aging of any kind
Replacement 100% for deeper, no aging of any kind
Replacement using a counter.
Maintain a list of K slots, and push the older things out the back end.
Maybe one or two others.
If any of the common schemes is chosen, then no surprise there.

2.  Fruit and Rybka have FOUR depth values stored.  Not just two.
You make the assumption that Rybka copied from Fruit.  That is not necessary.  Clearly, Vas and Fabian talked about MTD(f), and if one or the other or both thought it was a good idea, there is nothing wrong with that.
If you think that how many depth values used is copyrightable then I think that is strange.  If I looked at Fruit and said to myself, "Look at how clever these 4 depth values are." and then I used them, do you think it is something bad?

3.  replacement is done dozens of different ways.  No it isn't.  There are only a few replacement schemes.  I challenge you to show one dozen (let alone dozens) of different schemes.  Can you demonstrate that the replacement scheme of Fruit is nearly unique (e.g. no other program except Fruit and Rybka use that scheme.)?  And if I choose a replacement scheme, does someone else do wrong by choosing the same scheme?

4.  we are not talking "looks rather similar".  We are talking "looks rather identical".
With a vivid imagination, perhaps.  Much of the similarity can be manufactured in the mind of the person doing the composition from assembly.  I clearly showed that different implementations of the same algorithms produce the same assembly language.  So much of the magical "sameness" boils away when you do not use the target program as a "lens" to figure out what the other program's source might have looked like.
Parent - - By bob (Gold) Date 2013-09-06 00:48
There are plenty of other issues.

Buckets or no buckets?

how big are the buckets?  1 entry?  2 entries (Belle, older Crafty versions), 4 entries (current crafty) 8 entries (Cray Blitz and others)

How big are the entries?  From a low of 8 in later rybkas, to 12 in Cray Blitz, to 16 in crafty and others, to 20 or 24 for those that also store a static eval.

one table or two.

Always replace or use depth-preferred exclusively.

For your "challenge"  here you go:

1.  Directly choose one entry and store there.

2.  Directly choose one entry and overwrite based on depth.

3.  Directly choose one entry and overwrite if old OR if not, based on depth.

4.  address one entry in each of two tables.  In the first table, store the entry with the biggest depth.  Move that entry to the other table if the depth is better than that entry also (this is the belle and old Crafty algorithm)

5.  Address a bucket of 4 entries and choose from among those based on depth.

6.  Address a bucket of 4 entries and store over an old entry, if one is not found store over the one with lowest depth.

7.  Address a bucket of 4 entries and store first based on TYPE (EXACT overwrites any non-exact entry).  If TYPEs are all the same, use depth.

8.  Hash to one specific entry.  The remaining members of the "bucket" are NOT consecutive entries in memory, but are, instead, indexed from the current entry, taking N bits of the current hash signature to produce this index.  Now when two different signatures hash to the same first entry, you don't check the same 8 entries for replacement, since each signature would differ in that "index bit field."  This was used in Cray Blitz, BTW.

9.  One can totally ignore age, which some do, using any of the above algorithms.

10.  One can use the current aging mechanism where you have a counter that is incremented each time a new search begins, and which is stored in any entry created by this search.

11.  one can use the old approach of ripping through the entire hash table, setting an "old flag", at the start of a new search.  Any entry with that flag set gets overwritten before any entry that doesn't have it set.

12.  One can use chaining, rather than buckets, so that you effectively have variable-length buckets to avoid localized thrashing. 

The above list is actually WAY more than 12, because some can be combined to produce multiple different approaches.  And that is JUST replacement.

So, point by point.

1.  There are a few ways.  But this is just one parameter.  For each replacement scheme, you can use any of the aging approaches, giving MxN choices.  Then there is the bucket choice, giving MxNxO choices.  Then the information stored, giving MxNxOxP choices.  It adds up in a HURRY.

2.  First, why don't you look at fruit to see "how clever those ages are"???  :)  I won't spoil it for you...

3.  I gave those above.  FAR more than 12, since each aspect of the TT is a new dimension in the state space. 

4.  Did you look at Richard's code?  Did you look at the post where I gave fruit and rybka tt code?  No "vivid imagination" needed. 

Note your "lens" is a bit distorted.   One can NOT project ANY asm onto the fruit source.  Doesn't work.  You either have left over asm or left over C.  Not for fruit and rybka, which says a lot about their semantic equivalence.

A final note.  If you look at my hashing code, I use 3 loops to choose the entry to replace.  Turned out to be faster (once the tt entry is in cache, assuming one does THAT correctly (Fruit does not, nor does rybka) to use the 3 loops rather than a complex chain of if-then-elses to choose the entry to replace.  Crafty and fruit use age, and depth.  The code looks NOTHING alike.  And there is no way you can take the rybka binary and project it onto Crafty and get any kind of match at all.
Parent - - By user923005 (****) Date 2013-09-06 00:50
All you did is rehash the methods I already mentioned.
Parent - - By bob (Gold) Date 2013-09-06 01:22
Show me the CB chaining approach in your "methods".  Show me the belle two-table approach.  Etc.

It is more complex than you want it to be, because if it really were simple, your argument might hold water.  It isn't that simple, so your argument doesn't hold water.
Parent - - By user923005 (****) Date 2013-09-06 01:27
RE: "Show me the CB chaining approach in your "methods". "
Maintain a list of K slots, and push the older things out the back end.

Show me the belle two-table approach.
"And a couple other methods"

I don't know what the belle two-table approach does, but if it simply uses two hash tables (one for white and one for black), Averno did that.
Parent - By bob (Gold) Date 2013-09-06 01:31
Sorry, a "list of k slots".  Not the same thing.  In my code, two different hash signatures can map to the same first entry.  each different signature however has a DIFFERENT set of 8 slots.  Not the same thing at all.

Again, a little reading goes a long way.  There's a nice advantage in handling hashing like that.  just NOT on a PC.
Parent - By bob (Gold) Date 2013-09-06 01:34
Nope.  one "depth-priority" and one "always store".  Already explained in my list...

handling black and white is just another degree of freedom.  Crafty, for example, complements the hash signature for wtm/btm positions so they do not get confused.  Some XOR the sig with a single random number if it is btw.  Some xor with one of two values depending on wtm or btw.  Etc...
Parent - By Rebel (****) Date 2013-09-07 08:16
I added a subject search to the ccc utility, for instance typing "MTD" gives all subjects regarding MTD(f).

The new version is in development and thus not yet available so if you have search requests just ask for the moment.
- - By oudheusa (*****) Date 2013-09-05 11:32 Edited 2013-09-05 11:38
Ed,
Thanks for bringing this back to life, very insightfull. Reading this it is hard to imagine that anyone can claim that Vas is not an original author with own, creative ideas. More sadly, it shows that CC was once a community where cameraderie and sharing ideas was the norm and competition did not prevent great authors to jointly search for progress. Much like science actually; building on each others ideas.
Parent - - By user923005 (****) Date 2013-09-05 15:19
Aye.
And that is the gist of the real tragedy.  Competition has driven men to insanity.
Parent - By oudheusa (*****) Date 2013-09-05 19:07
I'm afraid its not competition, but pure envy, even hatred :sad:
Up Topic Rybka Support & Discussion / Rybka Discussion / Old CCC archives

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill