Author: Christophe Theron
Date: 11:34:45 04/17/01
Go up one level in this thread
On April 17, 2001 at 10:30:00, Gordon Rattray wrote:
>Great article! (thanks for posting it)
>
>As a CT/GT 2.0 user I've been extremely impressed with the program. Getting
>some insight into its actual workings is very interesting indeed. Thanks to
>Christope Theron for all his great work.
>
>There were some aspects that I didn't fully understand...
>
>[snip]
>
>>Question: Does Tiger use the null move search algorithm?
>>
>>CT: Null move is not the major selective search algorithm of Tiger. There are
>>several selective algorithm working together. Think of them as “filters”. Each
>>is able to filter (prune away) some moves, and putting a filter after a filter
>>after a filter... gives in the end a very selective filter.
>
>Does this imply that there are some positions that will never be solved given a
>theoretically infinite amount of time? i.e. if something is wrongly
>filtered/pruned then no amount of extra time will allow the program to see it?
No, in the worst case Tiger will need a huge amount of time to solve one
particular problem, but it should solve it in the end.
There are some exceptions due to subtle zugzwang problems and some endgame
knowledge that is partially implemented. For example there are endgame positions
that Tiger will evaluate as draw and stop searching when actually one side can
mate in a few moves. But these cases are extremely rare.
BTW I expect to solve some of these problems in the next release of the Tiger
engines.
>[snip]
>
>>Question: Christophe, do you believe that programs can be tuned so to play best
>>on tournament levels. Which means that if they play for example 40 minute games
>>they will play worse against an opponent than if they play 120 minutes games?
>>
>>CT: No I don't think so. If a program does better at game in 120 than at games
>>in 40, then in my opinion it is simply poorly designed.
>
>OK, here's this is my main misunderstanding. Incidentally, I'm pretty sure this
>has been discussed before and disagreements probably still exist. So, I'll just
>try to state why I'm still puzzled and try not to start another discussion.
>
>I view chess programs as complex algorithms, and hence they have complexity
>graphs of data size versus time. So, for example, like "bubble sort" compared
>with "quick sort" we can visualise graphs of how quickly the time required goes
>up as we process more data. For chess programs, I'd guess depth of search
>determines the data size primarily.
>
>Now, this leads me to believe that it is possible to have two chess programs A
>and B where: A is better for time less than, say, 30 minutes, but B is better
>at times greater than 30 minutes. I can't see how it is possible to say that
>either is definitely poorly designed? Although I don't have any figures, I
>think that GT 2.0 requires a certain amount of time to stabilise its search and
>I'm convinced that some opponents will do better against GT at shorter time
>controls.
Of course I know that it is possible that some program performs better at a
given time control due to its internal structure.
What I claim is that it is not necessary for a good program to have such an
unbalanced perormance/time graph.
I believe that it is possible to write a program that will perform optimally at
any time control (in comparison to other programs designed to match it at a
given, fixed, time control), and I'm working in that spirit.
>[snip]
>
>>Question: What about five minute games. If I play Tiger against a program x in
>>blitz and get a 60% score for Tiger, would you be willing to bet that in
>>tournament games there would be approximately the same result?
>>
>>CT: I think that if Tiger makes 60% against program X in blitz it will make 55%
>>(or so) against the same program at tournament time controls. It is not because
>>Tiger is weaker at long time controls, it is because strength differences
>>decrease with longer time controls. This phenomenon is not a property of Tiger,
>>it happens with all top chess engines. Eventually, if you use even longer time
>>controls I guess the winning percentage will come closer to 50%, but you will
>>never see program X winning.
>
>This continues my misunderstaning.
>
>If I design a chess program somewhat "brute force" and simplimatic, it may be
>relatively ok for shallow searches during blitz games.
No, I guarantee that it will not be OK, even at shallow searches (except ply
depth 1).
> But this design will
>never scale up and I'd expect programs like GT to defeat it by an even bigger
>margin at longer time controls. Once again, my "complexity graph" thinking
>shows the divergence to increase with each extra ply.
>
>If you made the assumption that program X above is *well designed* (unlike my
>example), then I still think that GT may still scale up better.
In your example the key point is that you do not need to use very long time
controls to see that the brute force program is inferior.
What I mean is that the performance/time curves intersect in just one point,
which is very close to the origin (very very fast time controls).
Again, I do not claim that it is impossible to write on purpose a program that
would intersect a second time. For example you take a good program and you make
it weak on purpose at longer time controls and you get a second intersecting
point.
What I claim is that with a program that is well-designed enough it will not
happen.
I also say that there is another fact that has a major influence on the
performance/time curve, and it is the fact that at very long time controls the
differences between programs decreases due to the nature of the chess game.
So the compared curves come closer to each other, but that's not a reason for
them to intersect.
>[snip]
>
>>CT: Yes. CT14 and GT2 would play the endgame identically.
>
>Do you have any exact definitions of "endgame". For example, if I showed you a
>test position could you easily tell if CT and GT will handle it the same? I'm
>just curious as I sometimes give both programs the same position to analyse.
>I'd guess it is an involved expression.
Yes I know the condition which is used by Tiger to define the endgame.
It has to do with the number of pieces left on the board (not counting pawns)
and IIRC the queen counts double.
But in general if there are no more queens left on the board, then you can be
sure that Chess Tiger and Gambit Tiger will play the same moves.
Christophe
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.