| |
Main
Date: 28 Nov 2005 10:31:58
From: Major Cat
Subject: Computer "thinking" on opponent's time
|
There is a time-honored feature in most
mainstream chess programs that allows
a machine to "think" while waiting for
its OTB opponent to make his move. Terms
like "deep thinking" and "permanent
brain" have been coined in the past to
refer to this feature.
How is the machine doing this? I mean,
does it "assume" that the opponent will
play optimally or does it divide its
provisional analysis time to consider
optimal responses to sub-optimal moves
that its opponent might make?
Are "hashtables" important in the above
regard? By the way, are "hashtables" and
"transposition tables" terms that can be
used interchangeably? In opening theory, a
transposition has a specialized meaning...
Regards,
Major Cat
|
|
| |
Date: 28 Nov 2005 19:27:58
From: Alexander Belov
Subject: Re: Computer "thinking" on opponent's time
|
"Major Cat" <epikuros@istar.ca > wrote in message
news:438B4D1E.6F5A@istar.ca...
> How is the machine doing this? I mean,
> does it "assume" that the opponent will
> play optimally or does it divide its
> provisional analysis time to consider
> optimal responses to sub-optimal moves
> that its opponent might make?
Programs may vary their strategy for pondering. But IMHO the simplest way is
based on iterative deepening.
During own time engine performs iterative deepening and when the time for
move is elapsed it makes own move and and assumed opponent best move. If
program finished n-ply search, after move it has (n-2) ply search
information in hashtable and therefore it can continue "thinking" at
opponent time starting from (n-1) ply. When opponent responds with the move
we have to check either it was best move that we assumed when we were
pondering. If it is, we just continue "thinking" without interruption, if it
is not, we have to start "thinking" from the beginning using relevant
opponent response.
> Are "hashtables" important in the above
> regard? By the way, are "hashtables" and
> "transposition tables" terms that can be
> used interchangeably? In opening theory, a
> transposition has a specialized meaning...
Hashtables is more general term for any tables that keep pairs of (kay,
value). E.g. hashtables may include pawn structures evaluation, other
position attributes which can be extracted from position and worth storing
in hashtables to avoid recalculation. "Transposition tables" term is for
overall position evaluation. Also there may be several TT in the engine that
evict stored position values using different eviction schemes.
|
| | |
Date: 28 Nov 2005 13:23:45
From: Major Cat
Subject: Re: Computer "thinking" on opponent's time
|
Alexander Belov wrote:
>
> "Major Cat" <epikuros@istar.ca> wrote in message
> news:438B4D1E.6F5A@istar.ca...
> > How is the machine doing this? I mean,
> > does it "assume" that the opponent will
> > play optimally or does it divide its
> > provisional analysis time to consider
> > optimal responses to sub-optimal moves
> > that its opponent might make?
>
> Programs may vary their strategy for pondering. But IMHO the simplest way is
> based on iterative deepening.
> During own time engine performs iterative deepening and when the time for
> move is elapsed it makes own move and and assumed opponent best move. If
> program finished n-ply search, after move it has (n-2) ply search
> information in hashtable and therefore it can continue "thinking" at
> opponent time starting from (n-1) ply. When opponent responds with the move
> we have to check either it was best move that we assumed when we were
> pondering. If it is, we just continue "thinking" without interruption,
> if it
> is not, we have to start "thinking" from the beginning using relevant
> opponent response.
Are you saying that, when the computer gets
"surprised" by its opponent (who played a
move other than the one(s) the machine ex-
pected him to), the information already
stored in the "hashtables" becomes totally
useless to the machine in its future ponderings?
>
> > Are "hashtables" important in the above
> > regard? By the way, are "hashtables" and
> > "transposition tables" terms that can be
> > used interchangeably? In opening theory, a
> > transposition has a specialized meaning...
>
> Hashtables is more general term for any tables that keep pairs of (kay,
> value). E.g. hashtables may include pawn structures evaluation, other
> position attributes which can be extracted from position and worth storing
> in hashtables to avoid recalculation. "Transposition tables" term is for
> overall position evaluation. Also there may be several TT in the engine that
> evict stored position values using different eviction schemes.
By eviction, do you mean something
like updating the value assigned to
a position that already inhabits the
"hashtables" or a wiping out of such
a position together with all of its
hitherto stored attributes?
Regards,
Major Cat
|
| | | |
Date: 29 Nov 2005 11:23:24
From: Alexander Belov
Subject: Re: Computer "thinking" on opponent's time
|
"Major Cat" <epikuros@istar.ca > wrote in message
news:438B7561.5433@istar.ca...
> Alexander Belov wrote:
> > Programs may vary their strategy for pondering. But IMHO the simplest
way is
> > based on iterative deepening.
> > During own time engine performs iterative deepening and when the time
for
> > move is elapsed it makes own move and and assumed opponent best move. If
> > program finished n-ply search, after move it has (n-2) ply search
> > information in hashtable and therefore it can continue "thinking" at
> > opponent time starting from (n-1) ply. When opponent responds with the
move
> > we have to check either it was best move that we assumed when we were
> > pondering. If it is, we just continue "thinking" without interruption,
> > if it
> > is not, we have to start "thinking" from the beginning using relevant
> > opponent response.
>
> Are you saying that, when the computer gets
> "surprised" by its opponent (who played a
> move other than the one(s) the machine ex-
> pected him to), the information already
> stored in the "hashtables" becomes totally
> useless to the machine in its future ponderings?
No. Hashtables might still contain enough transpositions for another move,
but IMHO less than in case the program guess was correct. The main point is
to stop "thinking" about the irrelevant move and start search with the
opponent move. It is clear.
> By eviction, do you mean something
> like updating the value assigned to
> a position that already inhabits the
> "hashtables" or a wiping out of such
> a position together with all of its
> hitherto stored attributes?
I mean wiping it out of some or all tables. E.g. program may have two
tables. One keeps position values with "always replace" eviction scheme,
while the other keeps position values, which are replaced only with position
search value of the higher ply depth. "Always replace" table evicts position
into the second table.
|
| |
Date:
From: Martin Brown
Subject: Re: Computer "thinking" on opponent's time
|
|
| | |
Date: 28 Nov 2005 13:11:20
From: Major Cat
Subject: Re: Computer "thinking" on opponent's time
|
Martin Brown wrote:
>
> Major Cat wrote:
>
> > There is a time-honored feature in most
> > mainstream chess programs that allows
> > a machine to "think" while waiting for
> > its OTB opponent to make his move. Terms
> > like "deep thinking" and "permanent
> > brain" have been coined in the past to
> > refer to this feature.
>
> That is just the marketting people speaking. Basically it means not
> sitting there polling the keyboard and waiting for input like the
> earliest programs did. It essentially tries to second guess the N most
> likely responses from you (for some N) and explores each of them.
>
> This means that provided you do play down one of the lines it has
> already partially analysed the alpha-beta search has a head start.
Here is a practical situation. Say a
human player wants to practice OTB chess
against a computer opponent. Also, assume
that the human player does not mind
that his computer opponent plays fast...
To shoehorn more games into the time
slice that the human player reserves
for this kind of OTB practice, he adopts
asymmetrical time controls. For himself,
he chooses classical or neo-classical
time controls. However, for his computer
opponent, the human player chooses
something like "game in 30 minutes".
He does so under the assumption that
what with the ample time for "background
thinking" that the (neo-)classical time
controls governing human play would al-
low, the computer play would _still_
be quite formidable... Is this a reasonable
approach?
>
> > How is the machine doing this? I mean,
> > does it "assume" that the opponent will
> > play optimally or does it divide its
> > provisional analysis time to consider
> > optimal responses to sub-optimal moves
> > that its opponent might make?
>
> I don't know but I would expect it divides its time between the top 3 or
> 4 likely moves.
This may be of some import in the situation
that I have outlined above. That is, how
often the machine does get "surprised" and,
if so, if the "hashtables" can still help it
or not.
> >
> > Are "hashtables" important in the above
> > regard? By the way, are "hashtables" and
> > "transposition tables" terms that can be
> > used interchangeably? In opening theory, a
> > transposition has a specialized meaning...
>
> Hashtables are a quick way of obtaining a full depth evaluation for a
> given position and player to move. Hashtable describes how it is
> implemented - transposition is what it was called before computers.
>
> One thing I have noticed a few times is that allowing Fritz 8
> blundercheck to run immediately after a game that thrashes about a bit
> in the endgame the analysis is noticeably inferior if the cache is not
> cleared first. You get the odd bad move that goes unremarked upon.
>
> I suspect hashtable collisions may be responsible. Clearing the
> hashtables and restarting the blundercheck always fixes it.
Because there are so many caches around,
I want to make sure that I understand this
correctly. I assume that the "cache" you
are talking about is the dedicated software
cache that implememts the "hashtables" within
the context of a particular chess program,
right?
>
> Regards,
> Martin Brown
Regards,
Major Cat
|
| | | |
Date: 29 Nov 2005 11:23:11
From: Guy Macon
Subject: Re: Computer "thinking" on opponent's time
|
Major Cat wrote:
>Here is a practical situation. Say a
>human player wants to practice OTB chess
>against a computer opponent. Also, assume
>that the human player does not mind
>that his computer opponent plays fast...
>To shoehorn more games into the time
>slice that the human player reserves
>for this kind of OTB practice, he adopts
>asymmetrical time controls. For himself,
>he chooses classical or neo-classical
>time controls. However, for his computer
>opponent, the human player chooses
>something like "game in 30 minutes".
>He does so under the assumption that
>what with the ample time for "background
>thinking" that the (neo-)classical time
>controls governing human play would al-
>low, the computer play would _still_
>be quite formidable... Is this a reasonable
>approach?
If the computer considers several of your potential moves, yes.
Some only consider what rgey think is your most likely reply,
and thus are a lot more stupid when you do something unexpected.
|
| | | | |
Date: 29 Nov 2005 18:17:04
From: Bo Persson
Subject: Re: Computer "thinking" on opponent's time
|
"Guy Macon" <_see.web.page_@_www.guymacon.com_ > skrev i meddelandet
news:11ooeh29f16v569@corp.supernews.com...
>
>
>
> Major Cat wrote:
>
>>Here is a practical situation. Say a
>>human player wants to practice OTB chess
>>against a computer opponent. Also, assume
>>that the human player does not mind
>>that his computer opponent plays fast...
>>To shoehorn more games into the time
>>slice that the human player reserves
>>for this kind of OTB practice, he adopts
>>asymmetrical time controls. For himself,
>>he chooses classical or neo-classical
>>time controls. However, for his computer
>>opponent, the human player chooses
>>something like "game in 30 minutes".
>>He does so under the assumption that
>>what with the ample time for "background
>>thinking" that the (neo-)classical time
>>controls governing human play would al-
>>low, the computer play would _still_
>>be quite formidable... Is this a reasonable
>>approach?
>
> If the computer considers several of your potential moves, yes.
> Some only consider what rgey think is your most likely reply,
> and thus are a lot more stupid when you do something unexpected.
>
You can also see this from another point of view, of course:
If the program is really right about the best reply, it is to its
*advantage* if you chose another move. In that case, it can afford to
re-search for a reply to your inferior move!
If you generally outsmart the program on most move selections, it will
lose anyway!
Bo Persson
|
| | | | | |
Date: 29 Nov 2005 14:05:36
From: Major Cat
Subject: Re: Computer "thinking" on opponent's time
|
Bo Persson wrote:
>
> "Guy Macon" <_see.web.page_@_www.guymacon.com_> skrev i meddelandet
> news:11ooeh29f16v569@corp.supernews.com...
> >
> >
> >
> > Major Cat wrote:
> >
> >>Here is a practical situation. Say a
> >>human player wants to practice OTB chess
> >>against a computer opponent. Also, assume
> >>that the human player does not mind
> >>that his computer opponent plays fast...
> >>To shoehorn more games into the time
> >>slice that the human player reserves
> >>for this kind of OTB practice, he adopts
> >>asymmetrical time controls. For himself,
> >>he chooses classical or neo-classical
> >>time controls. However, for his computer
> >>opponent, the human player chooses
> >>something like "game in 30 minutes".
> >>He does so under the assumption that
> >>what with the ample time for "background
> >>thinking" that the (neo-)classical time
> >>controls governing human play would al-
> >>low, the computer play would _still_
> >>be quite formidable... Is this a reasonable
> >>approach?
> >
> > If the computer considers several of your potential moves, yes.
> > Some only consider what rgey think is your most likely reply,
> > and thus are a lot more stupid when you do something unexpected.
> >
>
> You can also see this from another point of view, of course:
>
> If the program is really right about the best reply, it is to its
> *advantage* if you chose another move. In that case, it can afford to
> re-search for a reply to your inferior move!
Yes; if the computer's time control is
set too restrictively though, it may mat-
ter to the program whether the "hashtables"
contain usable information to quickly assist
the new search...
>
> If you generally outsmart the program on most move selections, it will
> lose anyway!
Of course, one can "outsmart" the machine
with quite a few moves that are not _really_
bad and still lose the game! 8 >)
>
> Bo Persson
Regards,
Major Cat
|
| | | | | | |
Date: 29 Nov 2005 22:31:48
From: Bo Persson
Subject: Re: Computer "thinking" on opponent's time
|
"Major Cat" <epikuros@istar.ca > skrev i meddelandet
news:438CD0B0.1CF1@istar.ca...
> Bo Persson wrote:
>>
>> "Guy Macon" <_see.web.page_@_www.guymacon.com_> skrev i meddelandet
>> news:11ooeh29f16v569@corp.supernews.com...
>> >
>> >
>> >
>> > Major Cat wrote:
>> >
>> >>Here is a practical situation. Say a
>> >>human player wants to practice OTB chess
>> >>against a computer opponent. Also, assume
>> >>that the human player does not mind
>> >>that his computer opponent plays fast...
>> >>To shoehorn more games into the time
>> >>slice that the human player reserves
>> >>for this kind of OTB practice, he adopts
>> >>asymmetrical time controls. For himself,
>> >>he chooses classical or neo-classical
>> >>time controls. However, for his computer
>> >>opponent, the human player chooses
>> >>something like "game in 30 minutes".
>> >>He does so under the assumption that
>> >>what with the ample time for "background
>> >>thinking" that the (neo-)classical time
>> >>controls governing human play would al-
>> >>low, the computer play would _still_
>> >>be quite formidable... Is this a reasonable
>> >>approach?
>> >
>> > If the computer considers several of your potential moves, yes.
>> > Some only consider what rgey think is your most likely reply,
>> > and thus are a lot more stupid when you do something unexpected.
>> >
>>
>> You can also see this from another point of view, of course:
>>
>> If the program is really right about the best reply, it is to its
>> *advantage* if you chose another move. In that case, it can afford
>> to
>> re-search for a reply to your inferior move!
>
> Yes; if the computer's time control is
> set too restrictively though, it may mat-
> ter to the program whether the "hashtables"
> contain usable information to quickly assist
> the new search...
>
That is not exactly what I meant.
If the program is correct about your best move, and you chose another
one, you're toast. So, *if* the program is correct in predicting the
line of play, it should spend its time investigating it further. If
you then deviate from the best line, the program has an advantage, and
can afford not having checked out this particular line.
If the program is consistently *not* predicting your best move, it
will definitely lose. So, if you think about it, it is a good strategy
for the program to assume that it is correct, and that its opponent
will follow the predicted line.
Bo Persson
|
| | | | | | | |
Date: 29 Nov 2005 19:31:43
From: Major Cat
Subject: Re: Computer "thinking" on opponent's time
|
Bo Persson wrote:
> >> If the program is really right about the best reply, it is to its
> >> *advantage* if you chose another move. In that case, it can afford
> >> to
> >> re-search for a reply to your inferior move!
> >
> > Yes; if the computer's time control is
> > set too restrictively though, it may mat-
> > ter to the program whether the "hashtables"
> > contain usable information to quickly assist
> > the new search...
> >
>
> That is not exactly what I meant.
>
> If the program is correct about your best move, and you chose another
> one, you're toast.
Not necessarily. Not every move is _that_
critical.
> So, *if* the program is correct in predicting the
> line of play, it should spend its time investigating it further. If
> you then deviate from the best line, the program has an advantage, and
> can afford not having checked out this particular line.
If time is very, very short and the human's
"sub-optimal" response is not markedly inferior,
the machine may have to hurry up in the face
of an unhelpful "hashtable"...
>
> If the program is consistently *not* predicting your best move, it
> will definitely lose.
Agreed, provided the "human best" and the
"machine best" coincide more often than not.
> So, if you think about it, it is a good strategy
> for the program to assume that it is correct, and that its opponent
> will follow the predicted line.
This is where the floodgates open... You see,
it may make a difference to the human player
what kind of machine play he is faced with.
For example, Hydra, with all its prowess not-
withstanding, may not fit a human's practice
needs as well as, say, REBEL 12 (DOS)! 8 >)
>
> Bo Persson
Regards,
Major Cat
|
| | | | |
Date: 29 Nov 2005 08:53:17
From: Major Cat
Subject: Re: Computer "thinking" on opponent's time
|
Guy Macon wrote:
>
> Major Cat wrote:
>
> >Here is a practical situation. Say a
> >human player wants to practice OTB chess
> >against a computer opponent. Also, assume
> >that the human player does not mind
> >that his computer opponent plays fast...
> >To shoehorn more games into the time
> >slice that the human player reserves
> >for this kind of OTB practice, he adopts
> >asymmetrical time controls. For himself,
> >he chooses classical or neo-classical
> >time controls. However, for his computer
> >opponent, the human player chooses
> >something like "game in 30 minutes".
> >He does so under the assumption that
> >what with the ample time for "background
> >thinking" that the (neo-)classical time
> >controls governing human play would al-
> >low, the computer play would _still_
> >be quite formidable... Is this a reasonable
> >approach?
>
> If the computer considers several of your potential moves, yes.
> Some only consider what rgey think is your most likely reply,
> and thus are a lot more stupid when you do something unexpected.
I am starting to realize that the
technical aspects under discussion may
be important in the conceptualization
and coding of machine behavior that closer
emulates human OTB play. Humans have been
attempting to formulate and implement ef-
fective OTB "anti-computer" strategies for
some time now. How about programmers giving
some thought to countering human OTB play
with "human-like" (not merely "anti-human")
ploys _as if_ the machine is a human OTB
player itself? I speculate that, in this
context, programs able to (i) "cope" with
OTB "surprises" generated by human play _and_
(ii) "serve" their very own _human-like_ OTB
"surprises" would be something very worth-
while to shoot for.
Regards,
Major Cat
|
| | | |
Date: 29 Nov 2005 09:40:12
From: David Richerby
Subject: Re: Computer "thinking" on opponent's time
|
Major Cat <epikuros@istar.ca > wrote:
> Here is a practical situation. Say a human player wants to practice OTB
> chess against a computer opponent. Also, assume that the human player
> does not mind that his computer opponent plays fast... To shoehorn more
> games into the time slice that the human player reserves for this kind
> of OTB practice, he adopts asymmetrical time controls. For himself, he
> chooses classical or neo-classical time controls. However, for his
> computer opponent, the human player chooses something like "game in 30
> minutes".
The problem with this is that it doesn't give the human any chance to
think on his opponent's time. I think that's a good thing to practise as
I find that I think quite differently on my time and on my opponent's.
Typically, I think fairly concretely on my own time, looking at specific
variations, while, on my opponent's time, I tend to think more abstractly,
looking for weaknesses in the position and trying to come up with plans.
Dave.
--
David Richerby Happy Smokes (TM): it's like a pack
www.chiark.greenend.org.uk/~davidr/ of cigarettes that makes your troubles
melt away!
|
| | | | |
Date: 29 Nov 2005 08:19:55
From: Major Cat
Subject: Re: Computer "thinking" on opponent's time
|
David Richerby wrote:
>
> Major Cat <epikuros@istar.ca> wrote:
> > Here is a practical situation. Say a human player wants to practice OTB
> > chess against a computer opponent. Also, assume that the human player
> > does not mind that his computer opponent plays fast... To shoehorn more
> > games into the time slice that the human player reserves for this kind
> > of OTB practice, he adopts asymmetrical time controls. For himself, he
> > chooses classical or neo-classical time controls. However, for his
> > computer opponent, the human player chooses something like "game in 30
> > minutes".
>
> The problem with this is that it doesn't give the human any chance to
> think on his opponent's time. I think that's a good thing to practise as
> I find that I think quite differently on my time and on my opponent's.
> Typically, I think fairly concretely on my own time, looking at specific
> variations, while, on my opponent's time, I tend to think more abstractly,
> looking for weaknesses in the position and trying to come up with plans.
Thank you for highlighting this issue
again. I guess, there is no such thing
as a free lunch! 8 >)
>
> Dave.
>
> --
> David Richerby Happy Smokes (TM): it's like a pack
> www.chiark.greenend.org.uk/~davidr/ of cigarettes that makes your troubles
> melt away!
Regards,
Major Cat
|
| | |
Date: 28 Nov 2005 17:56:37
From: Simon Waters
Subject: Re: Computer "thinking" on opponent's time
|
On Mon, 28 Nov 2005 15:55:29 +0000, Martin Brown wrote:
> I don't know but I would expect it divides its time between the top 3 or 4
> likely moves.
Some authors suggest that it is simpler to assume the most likely reply,
and preanalyse just that.
Hopefully if your code is clean enough you can just analyse, and populate
the transposition tables, and other data, as appropriate.
When we made GNU Chess "ponder" (no guarantees we did it right) there were
terms in the evaluation which weighted to "side to move", when they should
have been "side(s) computer is playing", and similar little gotchas.
|
|
