Tablebase Computation in Real Time

[Pio]

Hi James!

You might find this thread interesting http://www.talkchess.com/forum/viewtopic.php?t=46993

Good luck!

[jiHymas]

It could turn out that in an inferior position, it would be optimal to prefer evaluation vectors that have a lot of contradictory elements; in human terms this might (might!) be referred to as 'seeking complications'.

That's expressed badly - it could be read as just being a penalty applied to the evaluation and as such would not be incompatible with collapsing the evaluation into a scalar for propogation.

I am seeking to express the hypothesis that changing the fundamental characteristics of a position is Riskier than maintaining them; and this Risk should influence the evaluation of Reward when selecting variations.

[kbhearn]

There are of course alternative algorithms to alpha-beta that could make use of evaluation functions returning more data than just a 'mean' score, but as the top programs for decades have used alpha-beta centred algorithms, interest in exploring other ways is limited.

There was a discussion not long ago about using a non-scalar static eval for decision making purposes on reductions/pruning which would fit into the alpha beta algorithm, but at the end of the day alpha-beta only propagates one value, if you want to deal with distributions instead of scalars you're going to have to find your own way to make a reasonably strong engine, which could be fun or frustrating depending on your outlook on things :)

[Edmund]

So it's the propogation of scalars in computerchess that I find of interest. Why only scalars? Why not the entire vector (or perhaps some reasonably condensed version)?

Most of the time modern engines search with null-windows. They first establish a certain principal variation and then just confirm that there is no better alternative. It is not interested by what margin the other moves are worse. Using a tight window in an alpha beta framework guarantees the maximum number of cut-offs.

There are alternative algorithms (some of which I pointed you to), but none have stood a chance in tournaments.

I forgot to link you to: http://webdocs.cs.ualberta.ca/~tony/OldPapers/joa89.pdf
This is one of my favorite papers on the topic. However I agree with you that Junghanns Paper explains quite well the concept of the risk-aversion/seeking in chess engines. I particularly like the visualisations.

By the way, I am coming from an economic background.

[jiHymas]

if you want to deal with distributions instead of scalars you're going to have to find your own way to make a reasonably strong engine, which could be fun or frustrating depending on your outlook on things :)

Fun!

Most of the time modern engines search with null-windows. They first establish a certain principal variation and then just confirm that there is no better alternative. It is not interested by what margin the other moves are worse. Using a tight window in an alpha beta framework guarantees the maximum number of cut-offs.

I'm not in a position to have an opinion on any of this, since at this point I'm not even a wannabe - I'm just filing away the idea that building a chess engine would be a worthy retirement project, much more enjoyable than throwing peanuts to squirrels or becoming the worst bridge player in Toronto.

All I can really say is what I've said before: my career has revolved around quantitative portfolio management. Each security in the portfolio has a vector of attributes - some fundamental, some market, many mixtures - and can be swapped for another security having another vector of attributes.

In that sense, it's like the chess problem: you have a position, and you have a vector of attributes and the objective is to swap those attributes in a long chain until you have achieved checkmate.

And, what I have found in the investment field is that you can't conduct your swaps successfully with scalars. Most of my work is in fixed-income, but the concept is better conveyed with an example from equities: I can compare one bank stock to another bank stock with a good degree of success. Comparing a bank stock to oil-company stock ... not so good. Comparing a bank stock to cash (i.e., market-timing) ... not at all.

This leads me to speculate that perhaps the same thing might be true of chess. It's a similar problem: we can't solve the problem, but we can apply heuristics to indicate probabilities; and if our heuristics are better than the opposing heuristics, that's a very good thing indeed.

So that's got me thinking about precisely the view you stated above: "It is not interested by what margin the other moves are worse". In portfolio management, that's a matter of great interest; both because there are costs to trading and - importantly - because you know your heuristics aren't accurate.

So say we are evaluating a security with two attributes, (X, Y) and we have the opportunity two swap it into one of two other securities, which have the attributes (at current prices) of (X + d, Y) and (0, X+Y+2d) [where d>0]. If we evaluate this choice by summing the attribute values to a scalar, we will choose the second, but that is not necessarily the best choice. Trading into the first choice is less risky because we can have more confidence in the relative value, since we are using the heuristics that calculate the attribute values in pretty much the same way, whereas the evaluation of the second security relies very heavily on the second heuristic. For those two securities, at that given time in market, those heuristics may return answers that do not reflect value in the same way.

And, more insidiously, if you trade in accordance with the scalar, you are quite likely to fall into situations where that second heuristic doesn't work as planned, where its error relative to the (unknown) true value, is what is driving the trade.

So that's what interests me about the chess engine problem: how well does this logic translate into the selection of candidate positions that are returned by search? If my advantage consists of a backward pawn, am I better off maintaining and improving that precise advantage while trying to improve the other attributes a tiny bit (X + d, Y), or am I better off allowing my opponent to liquidate that weakness in exchange for the bishop pair (0, X+Y+2d)?

A problem with this is that search is so good: in an open position, the end of the search pattern is typically so far removed from the beginning that all the candidate vectors are completely different. In such a case, it makes sense to use a scalar. However, comparison of vectors could help inform the search and reduce the probability (to continue the example) that you allow liquidation of the backward pawn in exchange for the bishop pair in a position in which your bishop-pair evaluation heuristic gives an unduly optimistic answer.

This response seems to have grown into something rather longer than I intended, and I apologize for it: as I stated at the beginning, it is impossible for me to have an informed opinion on this matter, because I've nevery gotten my hands dirty.

Maybe the whole idea has been thoroughly investigated and rejected long ago. Maybe the whole idea is just garbage. Maybe it's a decent enough idea, but implementation would impair efficiency of search by a sufficent margin to make the drawbacks outweigh the benefits. I don't know. And I suspect I'd like to find out for myself.

Another consideration is that I'm not really all that interested in search. It's necessary, of course, but I don't find the topic as interesting as the heuristic part of the equation.

And thank you for all the links!

[jiHymas]

Hi James!

You might find this thread interesting http://www.talkchess.com/forum/viewtopic.php?t=46993

Good luck!

Yes, it is an interesting thread! The underlying idea - that the heuristics are imprecise - also underlies my 'Risk' speculation.

[jiHymas]

I see that my original question has been addressed, at least in part, by the product FinalGen at http://www.mtu-media.com/finalgen/home_ing.php

The computation time seems - in general - too long for a practical game, but perhaps implementation by sequentially running "search for draw" followed by the full solution would help; multiple cores might also help.