Re: A Crime by a Board of Old Imposters

Robert Hyatt wrote:

> [snip]
>
> > However, this is not strictly mandated by alpha/beta; the algorithm 
> > basically needs valuations (scores) from a set S, and comparison 
> > operators to compare any two members of the set. I.e., mathematically, 
> > it has to be a poset.
>
>
> There I don't follow.  Alpha/Beta is specifically formulated to back up
> (and compare) a _single_ score, not a set of values.  

I'm trying to say that the ability to compare scores does not preclude 
an implementation where scoring has more information than a single 
number (as long as the scores are comparable). A single score wouldn't 
be a set, but a tuple (two values).

> > The classical metric used (e.g. centipawns) is essentially the 
> > evaluator's estimate yielded for one of the leaf nodes in its search 
> > tree, with the special property that it is on the most "conservative" 
> > move path found (assuming best play by me and the opponent).
>
>
> > Now suppose instead that I would express valuation of a position as a 
> > two-tuple (a,b), where 'a' is this classical metric, but 'b' is the 
> > distance of the selected leaf node (having valuation a) from the current 
> > position.
>
>
> > Now if we define comparison of two valuations (a1,b1) and (a2,b2) as 
> > follows (here I define arbitrarily that a1 high means "good for me":
>
>
> Sure, but look at what you are doing.  You have just made the entire
> search much more complicated.  All the search needs to do is find the
> move that leads to the best score, _period_.  It doesn't care if it
> is a draw by repetition after this immediate move, or a 50-move-rule
> draw, or anything else.  That's not something the engine needs to care
> about at all.  

Not in the setup in use by the engines today. Perhaps the idea is viable 
and could be picked up in a couple of years. Perhaps, of course, not.

> The GUI (or UI if you don't have graphics) is concerned with interfacing
> with the human, which means it is the right place to detect actual
> drawn games...
>
>
> > (a1,b1)<(a2,b2), if a1<a2
> > (a1,b1)>(a2,b2), if a1>a2
> > (a1,b1)=(a2,b2), if a1==b1 and a2==b2
> > (a1,b1)<(a2,b2), if a1==a2>0, b1<b2
> > (a1,b1)>(a2,b2), if a1==a2>0, b1>b2
> > (a1,b1)<(a2,b2), if a1==a2<0, b2>b1
> > (a1,b1)>(a2,b2), if a1==a2<0, b2<b1
>
>
> Again, that is not alpha/beta.  Or, if you think about it, you are
> collapsing all that data into one value.  But it adds no new functionality
> into the engine that doesn't already exist naturally in the GUI...

I think it's not the natural place. To any objective observer, of 
course, your opinion is to be valued much higher than mine, given your 
experience. However, the things you write below about having tried 
something yourself a couple of years ago are encouraging. Perhaps it's 
not complete nonsense.

> > Effectively, the whole score system is augmented with a "in ... plies" 
> > metric, which does allow you to distinguish between different wins, 
> > losses, and draws.
>
> Not quite.  Endgame tables don't say "draw in N plies".  Endgame tables
> say this position is a draw, _period_.  Maybe drawn by stalemate, or
> by repetition, or by 50 move rule, or by insufficient material...  So
> you don't have that information everywhere.  The transposition has this
> same problem.  It stores scores and positions, but no information about
> the path to that position, because it would be too big to store.  And
> again you run into the _same_ problem.

Yes, current tablebases don't say anything about draw positions, other 
than that they are draws. However, it may be possible to generate 
tablebases that do. I'd have to think about that.

Surely, there are a lot of problems to overcome, much of the existing 
infrastructure would have to be re-engineered.

> > Best of all, the entire alpha/beta framework is intact.

> No.  See above. You wreck endgame tables, hash tables, to name two.

Yes. "entire" was the wrong word to use; that should've been "basic". 
Alpha/beta searching would still be the algorithm of choice, but much 
peripheral infrastructure would not fit.

> > > You need to carefully study the alpha/beta algorithm.  All we get from
> >
> > > the search is a best move, and a score we expect if we play that move.
>
>
> > I know this, but the concept of "score" could easily be extended as per 
> > above.

> Again, you are not really that familiar with a real working search it
> seems.  The hashing problem drives us all nuts because of the problem
> you are trying to solve...

My lack of hands-on experience does indeed prevent me from seeing all 
consequences. My prime consideration was to discuss the possibility that 
there are no principal barriers to having an engine decide whether to 
claim a draw or not. I can understand why, in practice, it is convenient 
to separate these functions in two layers (you call this the GUI, I'd 
say its an engine function that sits on top of the move-generation and 
evaluation algorithms - but we're essentially talking about the same 
thing I think).

> > > We don't get information like "this is a draw _NOW_."  or "This will
> > > end in a 3-fold repetition 30 moves in the future" or whatever.
>
>
> > But that's because current engines don't do this; it's quite conceivable 
> > that they will in the future. I think this could make the basis of a 
> > fine engine (it wouldn't be too different from current algorithms).

> Not if they continue to use hashing.  That is a big problem.

I cannot judge that, but I can imagine it is.

> > In such a scheme, there is no need to have a layer on top of the 
> > alpha/beta algorithm responsible for claiming draws (be it the engine or 
> > the GUI); this in fact could be handled by the engine.
>
>
> > > Therefore your idea is simply impossible within the alpha/beta
> > > framework.  The engine simply decides "the best I can do is to take one
> > > of these moves that leads to a 0.00 score."
>
>
> > I hope to have shown that this claim depends on the premise that scores 
> > are currently represented by just a single scalar value (which is not a 
> > necessity).
>
>
> I hope I have shown that it is an impossibility to do it otherwise unless
> you lop off endgame tables, and lop off the hash table completely.

ok.

> [snip]
>
> The problem is that mate and draw are different.  Draws already have a 
> known problem with respect to hashing...  I even tried to do the thing
> you mention a few years ago (See The draw heuristic in Cray Blitz, in the
> JICCA).  However, it has lots of "artifacts" and the GUI _still_ has to
> be the one to say absolutely "this is a drawn position."

I'll look it up.

> [snip]
>
> > Yes (neat trick, by the way). I think (apart from tablebases, that do 
> > not contain information on the drawn positions other than that they are 
> > a draw) you would find that you would get swindling for free using the 
> > augmented score metric.
>
>
> Yes, as I tried that.  But as I said, it is not exact due to hashing,
> which means that the engine can not absolutely say "draw in 23 moves"
> as it might be more or less because of the hashing issue.  That's why
> the GUI needs to make the real decision, to avoid pissing an arbiter
> off in a real event.  :)

Ok. The GUI is then basically acting as a sentinel, guarding against 
uncertainty arising in the imperfect draw assessment of the engine. I 
can see that it's useful in practice; I don't see that it's strictly 
necessary in theory.


Anyway, I think it's best for me now to claim a draw on repetition in 
this discussion, as your arguments from years of experience are 
pounching on my defense. It is clear that I am in short supply of a lot 
of the knowledge that you have gained over the past several decades.

Although my all-out attack on your solid position has failed, I still 
hope to find I missed a good line in post-discussion analysis :)

Thanks for sharing your views, I learned a lot.

Best regards,

  Sidney