| |
Main
Date: 08 Feb 2008 09:41:26
From: Guy Macon
Subject: Improving upon perfect computer play
|
Imagine that you have a computer that plays perfect chess
because it has reached the point where it is playing from a
tablebase.
The common assumption is that such a computer should choose a
line that leads to mate as quickly as possible, while the losing
side should choose a line that delays the end as long as possible.
Is this really the best way to program such a computer?
Even if it is, it doesn't help the computer to choose
between lines that lead to a win in the same number of
moves. What's the best choice in such cases?
It isn't best if the computer knows that it is playing
another perfect computer. In that case the losing side
should resign rather than dragging things out.
It does not maximize the odds of winning against a human.
The losing side might do better by choosing a line that
has the most available blunders available for the winning
side. A really advanced computer might be able to choose
a line with many available blunders that look like good
moves to a human.
It does not always lead to the shortest win against a human
for the winning side. The winning side might do better by
choosing a slighly longer line that has the many available
blunders for the losing side that lead to quick kills.
Whether the opponent is running out of time also comes
into play; In such a case the winning side might end the
game quicker by chosing unexpected but still winning moves
rather than obvious moves with obvious replies.
Even with large tablebases, there are ways to improve the
computer's play against humans.
--
Guy Macon
<http://www.guymacon.com/ >
|
|
| |
Date:
From: Martin Brown
Subject: Re: Improving upon perfect computer play
|
|
| | |
Date: 12 Feb 2008 16:19:43
From: David Richerby
Subject: Re: Improving upon perfect computer play
|
tin Brown <
|
| | | |
Date: 13 Feb 2008 14:01:37
From: Guy Macon
Subject: Re: Improving upon perfect computer play
|
David Richerby wrote:
>
>tin Brown wrote:
>
>> Guy Macon <http://www.guymacon.com/> wrote:
>>
>>> It does not maximize the odds of winning against a human. The
>>> losing side might do better by choosing a line that has the most
>>> available blunders available for the winning side. A really
>>> advanced computer might be able to choose a line with many
>>> available blunders that look like good moves to a human.
>>
>> Indeed for optimum play against a human or an imperfect computer you
>> want as many pinch points as possible along the game tree where the
>> smallest number of good lines are offered to the opponent. And in an
>> ideal world the right move should not be obvious.
>
>I believe that `conspiracy number search' does something like this.
>I'm not fully up on the details but the basic idea is to score a node
>by the number of subnodes that would have to change their value in
>order to alter the result of the search. I don't have time to look
>into this right now but would be interested to read anything that
>people might post on the subject.
>
>For attempting to swindle with EGTBs, though, you might want to look
>at the proportion of nodes rather than the absolute number. (Or,
>perhaps, some slightly more complex function of the number of legal
>moves and the number of winning moves.)
...
>consider the case where [the perfect player is] losing.
>The tablebase just shrugs and says "Every move loses,"
>but we want to come up with something better, based on
>the assumption that the opponent will make mistakes.
>Essentially, we want a program that plays perfectly
>when it can win and attempts to swindle when it can't.
I wasn't aware of conspiracy numbers. Fascinating idea!
From [ http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html ]:
"Yet another idea is to extend by using 'conspiracy numbers.' The
conspiracy number of a node is the number of subnodes whose value
would have to change to upset the current evaluation. Crudely,
the idea is that if there are lots of ways in which you seem to
be winning, then if some of them are wrong you have a good chance
that one of them will still work, whereas if there is just one
line that seems to work, you are in trouble if it goes wrong.
So you should concentrate your efforts on the nodes with the
smallest conspiracy numbers at high levels.
and
"Complication vs. simplicity: If you are losing, then sometimes
the best plan is to battle on and on playing 'correct' moves in
the hope that your opponent will make a mistake. But sometimes
it is to seek complications, making objectively inferior moves
that nevertheless make it more likely that the opponent will
blunder. Conversely, when winning, quite often the best plan
is to 'sacrifice' some of your advantage in order to simplify
the position and prevent your opponent from having swindling
chances. Computers find this concept very difficult! An
occasional manifestation of this in chess programs occurs
when, for no apparent reason, the program throws away a rook,
say, into a totally lost position; when you analyse to find
why it did this, you discover that if it had played the
'correct' move, there was a horrendously obscure plan that
you had completely missed that would have won even more
than a rook if you had seen it. Programs need to learn
when 'I hope you miss it' is more productive than 'Oh dear,
I'm obviously losing.'"
(There are lots of other interesting comments on that page.)
--
Guy Macon
<http://www.guymacon.com/ >
|
| |
Date: 09 Feb 2008 06:54:39
From: Paolo
Subject: Re: Improving upon perfect computer play
|
Yes but imagine trying to store all those positions in the tablebase!
Nearly impossible! Our technology as it stands today cannot solve
chess.
|
| | |
Date: 09 Feb 2008 19:39:08
From: Guy Macon
Subject: Re: Improving upon perfect computer play
|
Paolo wrote:
>Yes but imagine trying to store all those positions in the tablebase!
>Nearly impossible!
Not needed. The tablebase allows the computer to play perfectly
from positions in the tablebase and to do so almost instantly.
Imagine a computer playing from a positon that the tablebase
says is as sure loss, against a human opponent who might not see
the win or who might blunder. The computer playing from the
losing position doesn't have to instantly pick one of the
various losing moves available. It can spend half a minute
analysing the alternatives and picking the one losing move
that it calculates to contain the most opportunities for a
human error.
>Our technology as it stands today cannot solve chess.
Irrelevant. Our technology as it stands today has solved
that subset of chess that occurs after the players trade
down to six men total on the board, and my suggestions as
to inproving the chances of a computer against a human are
valid in such positions.
--
Guy Macon
<http://www.guymacon.com/ >
|
| |
Date: 08 Feb 2008 18:12:11
From: johnny_t
Subject: Re: Improving upon perfect computer play
|
Guy Macon wrote:
> Imagine that you have a computer that plays perfect chess
> because it has reached the point where it is playing from a
> tablebase.
>
> The common assumption is that such a computer should choose a
> line that leads to mate as quickly as possible, while the losing
> side should choose a line that delays the end as long as possible.
>
> Is this really the best way to program such a computer?
> Even if it is, it doesn't help the computer to choose
> between lines that lead to a win in the same number of
> moves. What's the best choice in such cases?
>
> It isn't best if the computer knows that it is playing
> another perfect computer. In that case the losing side
> should resign rather than dragging things out.
>
> It does not maximize the odds of winning against a human.
> The losing side might do better by choosing a line that
> has the most available blunders available for the winning
> side. A really advanced computer might be able to choose
> a line with many available blunders that look like good
> moves to a human.
>
> It does not always lead to the shortest win against a human
> for the winning side. The winning side might do better by
> choosing a slighly longer line that has the many available
> blunders for the losing side that lead to quick kills.
>
> Whether the opponent is running out of time also comes
> into play; In such a case the winning side might end the
> game quicker by chosing unexpected but still winning moves
> rather than obvious moves with obvious replies.
>
> Even with large tablebases, there are ways to improve the
> computer's play against humans.
>
All of these points have been discussed ad nauseum in the quest to
solving checkers.
You can find the history, and result of many of the discussions in
One Jump Ahead. Available on Amazon.
These exact same problems came up in checkers. They are even further
down the path, because of cooks, the existing preprinted knowledge, and
because the game was weakly solved rather than just solved by tablebase.
|
|
