Is there a way to rank the drawing moves?

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Is there a way to rank the drawing moves?

Postby andytoh » Sun Feb 22, 2015 4:42 am

At present, I assume they are listed randomly. But shouldn't it be possible for there to be an algorithm that computes the probability that a drawing move leads to a win through mistakes by the opponent? Simply take the number of paths that lead to a win and divide by the total number of paths after that move? I know that such numbers would be astronomical, but I'm sure there is some sort of recursion or inheritance method that would avoid having to deal with such big numbers. We must agree that in practical play, not all drawing moves are equal. After a drawn position, it may be very difficult for one side to maintain the draw, with the smallest of inaccuracies turning the draw position to a losing position. Often there is only one move out of many possible moves that will maintain the draw.

Would any programmer be interested in ranking the drawing moves based on these criteria? It could be an interesting experiment to play using it against an unassisted human, starting with a drawn endgame. The side with the tablebases can play the "best recommend drawing move" at all times, and see if the opponent, no matter how good an endgame player he is, crumble because the moves made leave him struggling more and more to maintain the draw.
andytoh
 
Posts: 9
Joined: Mon Jul 17, 2006 3:24 pm

Re: Is there a way to rank the drawing moves?

Postby guyhaw » Fri Feb 27, 2015 8:24 pm

Yes, certainly there are ways to rank the drawing moves.

First, one could count the percentage of first responses that draw - and pick the move that minimises this. An extreme case of this, if one looks at 'draw studies', is that Black probably chooses a drawing move that forces a unique response from White (who has been challenged to draw).

With more finesse, one could attach a probability to drawing moves, and other probabilities (less) to moves that 'lose in m moves' (with smaller probabilities for smaller 'm').

http://centaur.reading.ac.uk/4550/ refers to this idea.

it would be interesting to run an algorithm that distinguishes between drawing moves on this basis. Some endgames which are drawn are
thought to be 'harder to defend than to win' etc.

g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Is there a way to rank the drawing moves?

Postby syzygy » Sat Feb 28, 2015 12:05 am

andytoh wrote:Often there is only one move out of many possible moves that will maintain the draw.

And often that is the obvious move that any newbie would play anyway.

I don't think trying to derive information from the number of drawing paths is going to work well. In addition, even if it is possible to compute the information in a relatively efficient way, storing it is going to increase storage requirements considerably.

To rank drawing moves, just let the engine do a regular search on (only) those moves without probing TBs and rank them according to score. That should do the trick in the large majority of cases.
syzygy
 
Posts: 161
Joined: Sun Aug 03, 2008 4:02 pm

Re: Is there a way to rank the drawing moves?

Postby guyhaw » Sat Feb 28, 2015 11:07 am

I wasn't proposing to store recommended drawing moves in a database.

Much prefer the forward-search with backed-up 'probability of being chosen' instead.

g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Is there a way to rank the drawing moves?

Postby andytoh » Sat Feb 28, 2015 3:49 pm

That's right. I never suggested increasing the file sizes to support this feature, which should be executable during run-time. Engines are not running during tablebase look-up anyway, so what would be the loss really? Simply list the drawing moves in a special order through some algorithm that the programmers should be able to figure out. As it is right now, the drawing moves are listed so that if you always choose the first drawing move listed you may even run into a threefold repetition, i.e. they are not listed in any special way at all (at least I don't see that it is). What I'm not sure of is who would write that code, the Chessbase programmers, or the endgame tablebase programmers.

Perhaps run a test algorithm for KRRvKQ only (or something like that) just to see if the idea is really useful or not against a fallible opponent in a drawn position?
andytoh
 
Posts: 9
Joined: Mon Jul 17, 2006 3:24 pm

Re: Is there a way to rank the drawing moves?

Postby guyhaw » Sat Feb 28, 2015 5:55 pm

My thought was that the code to choose between drawing moves would be on the search-engine side ... but maybe it's not a clear case.

If the engine searches a few ply forward, and probabilities are applied to the leaf-positions of the search-tree (and then backed up as expected-values to indicate the best drawing move), that feels like an engine-search with 'expected values' instead of 'static evaluation' values.

Further, the probabilities should ideally include some perception of the fallibility of the opponent, not something visible to the author of an endgame table (EGT).

g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Is there a way to rank the drawing moves?

Postby andytoh » Sat Feb 28, 2015 11:59 pm

What about the endgame tablebase generator reordering the drawing moves during generation of the files? I haven't studied the codes for the generators, but suppose the drawing moves are stored in a std::list. Then during generation, instead of inserting the drawing moves at the end of each list, insert them according to their rank in probabilities for a win (against a fallible opponent). This will mean longer generation time of course, but as far as extra memory storage increase goes, it is zero because no extra data is being stored. Only the order of the std::list elements is being adjusted during generation. Ok, during generation, the probabilities will need to be stored temporarily in order to determine where in the std::list the next-found drawing move shall be inserted, but once all the drawing moves have been found and ordered properly, the probabilities can be discarded and then no extra memory footprint results at the end. Does this make any sense?
andytoh
 
Posts: 9
Joined: Mon Jul 17, 2006 3:24 pm

On the difficulty of drawing ...

Postby guyhaw » Mon Mar 02, 2015 11:43 am

I am looking for drawn positions which are harder for the defender to defend if they have the move than if they have not.

'Difficulty' needs to be quantified in some way, which relates to the above discussion.

Is this ... 3k4/1R6/3B4/3K4/8/8/8/r7 ... such a position?

There are probably positions where the defender can (without being 'on move') reach a drawn endgame with one man less more quickly.

Perhaps, the next phase is a very clear draw, e.g., KNNK.

g
guyhaw
 
Posts: 489
Joined: Sat Jan 21, 2006 10:43 am
Location: Reading, UK

Re: Is there a way to rank the drawing moves?

Postby syzygy » Mon Mar 02, 2015 9:42 pm

guyhaw wrote:I wasn't proposing to store recommended drawing moves in a database.

Much prefer the forward-search with backed-up 'probability of being chosen' instead.

That's how I read the OP's suggestion. Or at least that's how I would try to implement counting the number of paths. Calculating recursively without keeping track of intermediate results in an endgame database is of course possible, but so is calculating the winning move. In other words, doing this on the fly is not going to work very well.

I guess it's possible to do a limited search and collect statistics from that. My guess is still that doing a regular search (without probing) is going to give "better" results.
syzygy
 
Posts: 161
Joined: Sun Aug 03, 2008 4:02 pm

Re: Is there a way to rank the drawing moves?

Postby syzygy » Mon Mar 02, 2015 9:46 pm

andytoh wrote:Engines are not running during tablebase look-up anyway, so what would be the loss really?

My engine runs (and so does SF), as it does what I propose above :)

What I'm not sure of is who would write that code, the Chessbase programmers, or the endgame tablebase programmers.

My suggestion would be implemented by the engine programmer. Your suggestion probably as well, as you'll need to do time management if you don't want to risk losing on time.
syzygy
 
Posts: 161
Joined: Sun Aug 03, 2008 4:02 pm

Re: Is there a way to rank the drawing moves?

Postby syzygy » Mon Mar 02, 2015 9:48 pm

andytoh wrote:What about the endgame tablebase generator reordering the drawing moves during generation of the files?

That's not how tablebases work. They don't store moves. They only store values, e.g. mate-in-10 or draw. Given a chess position, the probing code calculates an index number N and then looks up the Nth value in the tablebase. To find a move to play, the engine probes all successor positions and picks the one with the best value ("best" from the right point of view).

So... if you want to do this in the TB, you'll need to increase its size.
syzygy
 
Posts: 161
Joined: Sun Aug 03, 2008 4:02 pm


Return to Endgame Tablebases

Who is online

Users browsing this forum: Google [Bot] and 1 guest

cron