CHESS 4.5 (1973)
Robert Hyatt
Craig Shoemaker (craig.s...@his.home) wrote:
: Here are some restatements and questions from the article CHESS 4.5--The Northwestern University chess program by David Slate and Lawrence Atkin.
: I hope eventually to look at some parts of the Crafty chess playing code, but as a preliminary step I was doing some reading. Because I plan to eventually look at some of the Crafty code, some of my questions deal specifically about Crafty (since the author is kind to let everyone study his source code).
: -----
: 1) The article says that the basic data element of the program is the bit board: that is, a string of 64 bits where each bit represents a square of the board. Is a similar bit representation used in Crafty? The reason I ask is so that when I look at the code and documentation I'll have some general overview of what to expect and look out for.
yes, exactly... except crafty does not maintain the "attacks_to" and "attacks_from"
stuff, but computes them instantly upon demand by table lookups now...
: -----
: 2) In the conclusion section of this article, it states: "We conjecture that the better f already is, the more it will benefit from a deeper search. If this is true, then we should work on improving the quality of evaluation functions, rather than on small increments in search efficiency."
: So, my question is, how did history play out on this topic? Which was more important, the evaluation function or the depth of the search as the computers got more and more powerful? Or, would it be more
: accurate to say that it was a combination of the two? Or perhaps the addition of other considerations, such as "conceptual thinking and strategic implementations" carried out by the computer?
Hard to say, because no one has run the experiment. Monty Newborn and I are working
on this right now to see if the difference between 12-13 or 13-14 plies is really
almost nothing as has been suggested in the past, or if it still is producing
measurable performance gains in playing chess. More later... after I have some
results to discuss...
: -----
: 3) "This lack of programming tools has plagued the whole field of computer chess."
: Now that C is widely available, is that powerful enough to program chess concepts in? Would C++ be better (or is it not relevant because C++ is really emphasizing code reusability, but as far as conceptual program schemes it
: doesn't really change things)? Is another programming language in order to help push the currently very strong programs (such as Deep Blue and Deep Thought) to a higher level of accomplishment?
yes and no. C is not what is needed, but for efficiency's sake, it is about as
good as can be done at present. It is just difficult to ask some questions in
C (related to chess) efficiently...
: -----
: 4) Aside. This is an aside comment related to another post. When in another newgroup posted article mention was made about the opening, I quickly stated,
: being a novice, that there was no reason to teach a computer to play the opening and one could just tell it to use an opening book. However, in my readings I have learned that there might be a difference between what the computer thinks of the position it receives at the end of the opening book and what the
: grandmaster human was thinking when he reached that opening position. Thus, the computer might spend or waste a few moves repositioning it forces so that the position makes sense to its internal evaluation function. The article also went on to say that it would be a good idea to add positional features to the opening database. I would add that once positional and strategic plans are added to
: each node in the opening database, and the computer new what type of positions it wanted to head for (let's say it wants to head for open, highly tactical positions), then it could do a mini-max search of the opening library! And, it could determine the best opening for it to use. Anyway, this is an idea which went though my head when I read the article.
common idea/problem discussion. It's less of a problem than you'd suggest, but
you can't ignore the opening as humans will kill you if you do. For example
I've seen a *lot* of d4 nf6 Nd2 to take crafty out of book. If it doesn't handle
that correctly it will meet a Stonewall attack quickly. :)
: Bye,
: Craig
: In the computer chess newsgroup I am a novice poster; often ideas I say are already known, but I enjoy talking & thinking about them.
: ------------
: My notes on Monet and Symmetry are available for a short time from April 1 through about April 7, 1997 at http://www.his.com/~esoteric/interests/art/
: -----
: http://www.his.com/~esoteric/ then click on the "What's New" link.
: You must visit my page to send me e-mail.
Valavan Manohararajah
In article <craig.shoemaker-ya023...@news.wap.org>,
Craig Shoemaker <craig.s...@his.home> wrote:
>
>-----
>
>3) "This lack of programming tools has plagued the whole field of computer chess."
>
>Now that C is widely available, is that powerful enough to program chess concepts in? Would C++ be better (or is it not relevant because C++ is really emphasizing code reusability, but as far as conceptual program schemes it
>doesn't really change things)? Is another programming language in order to help push the currently very strong programs (such as Deep Blue and Deep Thought) to a higher level of accomplishment?
Many chess programs are already being written in C. C++ can make for some
very interesting constructs, at least from a chess standpoint. IMHO, it may
even make for a more clear representation of the different structures and
operations. As long as you don't get fancy with things like virtual functions
inside the search function, I think a C++ implementation should perform just
as well as a C implementation.
--
-------------------------------------------------------------------------------
man...@ecf.utoronto.ca | 3rd year Comp Eng., University of Toronto
Valavan Manohararajah |
-------------------------------------------------------------------------------
Robert Hyatt
Valavan Manohararajah (man...@ecf.toronto.edu) wrote:
: In article <craig.shoemaker-ya023...@news.wap.org>,
: Craig Shoemaker <craig.s...@his.home> wrote:
: >
: >-----
: >
: >3) "This lack of programming tools has plagued the whole field of computer chess."
: >
: >Now that C is widely available, is that powerful enough to program chess concepts in? Would C++ be better (or is it not relevant because C++ is really emphasizing code reusability, but as far as conceptual program schemes it
: >doesn't really change things)? Is another programming language in order to help push the currently very strong programs (such as Deep Blue and Deep Thought) to a higher level of accomplishment?
: Many chess programs are already being written in C. C++ can make for some
: very interesting constructs, at least from a chess standpoint. IMHO, it may
: even make for a more clear representation of the different structures and
: operations. As long as you don't get fancy with things like virtual functions
: inside the search function, I think a C++ implementation should perform just
: as well as a C implementation.
I believe (unless Joel has rewritten it recently) that ChessGuru, which
won the French computer chess tournament this year, was written in C++.
Joel and I have exchanged lots of bitmap ideas, and looked at each other's
code over time. It does make some things cleaner to read...
Joel Rivat
Bob Hyatt wrote:
>I believe (unless Joel has rewritten it recently) that ChessGuru, which
>won the French computer chess tournament this year, was written in C++.
>Joel and I have exchanged lots of bitmap ideas, and looked at each other's
>code over time. It does make some things cleaner to read...
I have not changed anything in ChessGuru except correcting minor bugs.
It is written in C++, because "C++ is a better C": inline functions,
easier parameter passing, etc...
I don't use any object oriented programming...
With a good compiler we should not see any difference with C,
but I don't know if this is true in practice...
Sometimes I think that my inline functions would be faster as macros...
Anyway the biggest problem is the evaluation function...
Joel Rivat
Valavan Manohararajah
Joel Rivat wrote:
I think that for the Microsoft Visual C++ compilers, macros and inline
functions
are about the same speed. I converted some low level functions from a
macro
to an inline function and didn't seem to get a hit.
Has anyone written a complete chess program, the object oriented way?
Right
off the top of my head, I can think of classes like
Class Piece {
}
Class Bishop : virtual public Piece {
}
Class Rook : virtual public Piece {
}
Class Queen : public Bishop, public Rook {
}
etc., possibly one can overload several operators in interesting ways.
Maybe a searcher class can give rise to a full width searcher class
and quiesce searcher class. Functions may use searchers without
knowing whether they are full width or quiesce....all they know is that
they search. etc. One can do the same for evaluation functions...
Class Evaluate giving rise to Class Evaluate_Opening,
Class Evaluate_Middle, Evaluate_End.
Although with C++, there might a lot of function call overhead, one can
possibly iniline a lot of stuff and get away with a fast program.
It might be interesting to discuss ways of "object-orienting" a chess
program.
Valavan Manohararajah
Remi Coulom
Valavan Manohararajah wrote:
>
[...]
> Has anyone written a complete chess program, the object oriented way?
> Right
> off the top of my head, I can think of classes like
>
> Class Piece {
> }
>
> Class Bishop : virtual public Piece {
> }
>
> Class Rook : virtual public Piece {
> }
>
> Class Queen : public Bishop, public Rook {
> }
>
> etc., possibly one can overload several operators in interesting ways.
>
> Maybe a searcher class can give rise to a full width searcher class
> and quiesce searcher class. Functions may use searchers without
> knowing whether they are full width or quiesce....all they know is that
> they search. etc. One can do the same for evaluation functions...
> Class Evaluate giving rise to Class Evaluate_Opening,
> Class Evaluate_Middle, Evaluate_End.
>
> Although with C++, there might a lot of function call overhead, one can
> possibly iniline a lot of stuff and get away with a fast program.
>
> It might be interesting to discuss ways of "object-orienting" a chess
> program.
>
> Valavan Manohararajah
I do not use OO techniques the way you suggest. In The Crazy Bishop,
the search looks like a very classical search (one function for normal
search and one for quiescence). I think that if you succeed in having
a search engine work with tricks like "Class Queen : public Bishop,
public Rook", then your move generation will be slower than a more
usal solution, because you'll have to call virtual functions virtually
and they could not be inlined.
I think OO techniques are very useful when it comes to writing
maintenable and reusable software. In TCB, I use them in the evaluation
function and in the user interface. I also use a very useful CEngine
class that allows me to write user interfaces and search tree analysis
tools that are completely independant from the chess engine. I have
already written 3 completely different chess engines that work with
exactly the same user interface code and C++ helped me a lot. Thanks to
this, I can develop the chess engine without having to think about
what it will be interfaced to. For instance, I am planning to add an
auto232 interface to my tools soon, and all my chess engines will
work with this auto232, without having to make any change in the code.
My classes work like this :
CEngine
/ \
CSpecialEngine CInterface
\ /
CSpecialEngineWithInterface
At the level of the CEngine class, I define virtual functions, some
to be re-defined by Engines, such as :
SetGear(gear) // gear = infinite, pondering, active, neutral
StopSearch()
SetTimeControl() ...
NewPosition()
and some others to be redefined by the interface, such as :
InfoMainLine()
OnOfferDraw()
OnProposeMove() ...
Then, I can mix different "special engines" with different
interfaces (console, GUI, xboard, auto232 ...) via multiple
inheritance. This also allows me to specialize the interface as needed.
If you want to understand better what I mean, you can have a look at
my C++ chess class library that is available from :
http://www-ensimag.imag.fr/eleves/Remi.Coulom/tcb.htm
TCB shows an example of how this generic engine interface can be
specialized.
BTW, a new release (0027) is planned for next monday, with some
corrections in pondering and a ~20% speed improvement.
Remi
Brian Sheppard
Craig Shoemaker <craig.s...@his.home> wrote in article
<craig.shoemaker-ya023...@news.wap.org>...
> 2) In the conclusion section of this article, it states:
> "We conjecture that the better f already is, the more it
> will benefit from a deeper search. If this is true, then
> we should work on improving the quality of evaluation functions,
> rather than on small increments in search efficiency."
The conjecture is false. Exactly the opposite is true: the *weaker*
the evaluation function, the more it benefits from deeper search.
Keep in mind that a weaker evaluation function starts from a lower
base skill level, so it *gains* more by search.
> So, my question is, how did history play out on this topic?
> Which was more important, the evaluation function or the depth
> the search as the computers got more and more powerful? Or, would
> it be more accurate to say that it was a combination of the two
> perhaps the addition of other considerations, such as "conceptual
> thinking and strategic implementations" carried out by the computer?
It is a combination of all the factors you mention, but projecting
pure speed gains shows that speed was the dominant factor over the
last two decades.
It is an open question whether further gains from speed alone are
possible. An ambitious 10-game match to study the question, where
one program got 100 times the CPU time of the other, was recently
abandoned, but we may yet have some data on this subject within
a year.
> -----
>
> 3) "This lack of programming tools has plagued the whole field of
computer chess."
>
> Now that C is widely available, is that powerful enough to program
> chess concepts in? Would C++ be better (or is it not relevant because
> C++ is really emphasizing code reusability, but as far as conceptual
> program schemes it doesn't really change things)? Is another programming
> language in order to help push the currently very strong programs (such
> as Deep Blue and Deep Thought) to a higher level of accomplishment?
I do not agree that the lack of programming tools has hurt computer
chess. We simply do not know how to proceed, and no number or quality
of tools will improve the situation.
Brian
Robert Hyatt
Brian Sheppard (bri...@mstone.com) wrote:
: Craig Shoemaker <craig.s...@his.home> wrote in article
: <craig.shoemaker-ya023...@news.wap.org>...
: > 2) In the conclusion section of this article, it states:
: > "We conjecture that the better f already is, the more it
: > will benefit from a deeper search. If this is true, then
: > we should work on improving the quality of evaluation functions,
: > rather than on small increments in search efficiency."
: The conjecture is false. Exactly the opposite is true: the *weaker*
: the evaluation function, the more it benefits from deeper search.
: Keep in mind that a weaker evaluation function starts from a lower
: base skill level, so it *gains* more by search.
Two arguments here. Certainly increased depth helps a stupid program
more than a smart program, at early plies. The smart program might
evaluate forks, while the stupid program has to stumble into them at
the right depth.
However, as depth increases, several experiments have shown that there
is a diminishing return for each additional ply. Berliner ran some
tests that seem to indicate this diminishing return is worse for
dumb programs, because all they get for each additional ply is better
tactics, while a strong positional program gets more knowledge about
how the pieces can be placed positionally.
The current crafty/hiarcs game is one interesting data point. The
upcoming ICCA article I'm helping Monty with will be another... One
thing is for sure, no one has yet tried to test this hypothesis at
the depths we are looking at (14 plies), so we should get some
interesting results for what machines might gain over the next 20 years
or more (100x may be doable, but we don't know.)
: > So, my question is, how did history play out on this topic?
: > Which was more important, the evaluation function or the depth
: > the search as the computers got more and more powerful? Or, would
: > it be more accurate to say that it was a combination of the two
: > perhaps the addition of other considerations, such as "conceptual
: > thinking and strategic implementations" carried out by the computer?
: It is a combination of all the factors you mention, but projecting
: pure speed gains shows that speed was the dominant factor over the
: last two decades.
: It is an open question whether further gains from speed alone are
: possible. An ambitious 10-game match to study the question, where
: one program got 100 times the CPU time of the other, was recently
: abandoned, but we may yet have some data on this subject within
: a year.
Note that a replacement match has started between Crafty and Nimzo.
Same basic idea. Times of the two opponents are from a P5/120 and
a P5/150, but have been scaled up to approximately what would happen
on a P6/200 if hiarcs 6 played at 40/120, and Crafty played at
40/12000. Note that both are actually playing at a longer time control
than this to bring those two machines up to P6/200 search depths....
So we do get the data eventually... but as before it is slow going when
Crafty is getting about 24 hours per move. That limits progress.. :)
: > -----
Joe Stella
Valavan Manohararajah <man...@bnr.ca> wrote:
>[...]
>Has anyone written a complete chess program, the object oriented way?
>Right
>off the top of my head, I can think of classes like
> Class Piece {
> }
> Class Bishop : virtual public Piece {
> }
>[...]
>Valavan Manohararajah
Yes, I did this a few years ago. My classes looked almost exactly like
what you have here. The program was *slow*.
I then did some experiments with classes vs. ordinary subroutines. I wrote
a routine that generated moves for a rook, and timed its execution by
calling in repeatedly in a loop. I then took the *same* code and
made it a member function of a move generator class. The result was
about 15% slower. I don't know where the extra overhead came from,
but I threw out the object-oriented idea after this.
This was all with Visual C++ version 1.5. Maybe the newer versions
have gotten better with object-oriented code, but I would test it
out first before I used this approach in a chess program.
Joe Stella
Jon Dart
In article <334BF0...@bnr.ca>,
Valavan Manohararajah <man...@bnr.ca> wrote:
>
>Has anyone written a complete chess program, the object oriented way?
Arasan (http://www.best.com/~jdart/arasan.htm) is written in C++ and
has the usual constructs you would expect (Board, Piece, Square, etc),
although I wouldn't put it forward as as a model of object-oriented
design.
--Jon