Thoughts On Planning
mclane
Graham Douglass wrote:
>This knowledge should then be made available to a chess program. In carrying out
>its evaluation at leaf nodes, the program would be looking to get to positions
>where it can easily get to a theme that wins for white (or black).
>Do people think that these methods would produce human style play? Is this
>anything like the human planning process?
I know a couple of programs that use this method !
Goliath e.g., Rexchess had a kind of rule-base, also good old
super-constellation and i suspect Virtual-chess to use a kind of
planning algorithm, but I am not sure HOW they do it, by using
patterns generated out of databases (the quantity approach) or
different methods (more qualitively).
>Is this similar to the way CS-Tal works? (Chris has already demonstrated he
>likes to work with chess databases by producing a belter of an opening book for
>CS-Tal).
Definetely NOT the way CSTal works. Chris has NOT collected patterns
from massive databases !
That would be a quantitive effort, and this is the opposite of what he
tries. Each knowledge he implemented came by hand and was tuned by
hand. No knowledge was implemented using a statistic or database stuff
way. Sorry.
But this would be against our principles. When CSTal sacs something,
it is because of one of chris' strange knowledge stuff he has
implemented when he was drunken, tired ot in very high mood.
The program sacs without believing in the search. It would sac without
a search tree. But the sac is NOT coming out of knowledge that is
preprocessed.
It uses the same knowledge in the root (static without tree-approach)
in the tree-leaves too.
So it is full-evaluating.
The static/dynamical evaluations direct the programs' moves. The tree
is only used to outcompute the opponent chess-programs (cause THEY use
a tree) !!
This is - of course - my point of view. Chris has maybe a different...
I would call chris knowledge approach very similar to human's
prejudices.
You call somebody an asshole although it is maybe NOT true.
You use the search to find evidence that fullfills your prejudice !
BMeanwhile the other programs have to find evidence against the
prejudice-move.
If they don't find evidence, they are guilty. And lose the game.
If they find evidence that the prejudice-move of CSTAL was a bluff,
and the bluff was not deep enough, they win the game.
Often it was NOT a bluff and the sac was ok, but cstal was unable to
win the winning game cause the tree-abilities of CSTAL are not
magnificant, as you can imagine a forward pruning program doing 4000
NPS on a 200 MHz machine does not create enough tactical tree to
always win against the tree-approach-programs.
The prejudice-knowledge is NOT preprocessed knowledge !
It is NOT a rule-base !
The program does not rely on the search but on the evaluation.
I can understand this sound a little crazy, but when you see it sac
and evaluate in real you will see that it sometimes thinks a sac is
+3,55 and does it, and later finds out, oh - it is only a draw.
A normal chess program would call this a horizont problem. But a
forward pruning program has problems with the word HORIZONT because
almost any moves and any iteration is forward-pruned-horizont.
I think the term prejudice is a better word, because prejudices are
like the "horizont" of a forward-pruning program.
Chris allows CSTAL to have prejudices. And not to rely only on a
search tree.
This is what humans do. They do not generate a search tree. They
mainly play with prejudices, feelings and
"forgotten" (forgotten by the conscious parts of the brain) mistakes.
Mchess, Hiarcs, Crafty and other programs have also a very high
positional evaluation. But what CSTAL does is not a degree difference
to that. CSTAL is NOT evaluating with a higher positional score. It
works different.
I have tried to show examples and to compete with normal programs like
crafty / ferret here to show that it works.
And it does not only work in positions where you have to Bxh7 or Nxf7
or this stuff. It works in many other areas too. Also in games.
But it is NOT the kings-way (= the one and only way to heaven).
It is just a different approach.
It is NOT important how strong the results of this approach are, but
it is very funny for me to compete CSTAL with normal programs.
show me a test-suite and I will let it run with CSTAL and we see if it
works.
I would not exactly say that CSTAL plans from the knowledge. the plan
comes from using the knowledge into the tree. But sometimes the tree
has no influence to the plan/game because the evaluation of the
knowledge is much higher than the tree-evaluation. In this moments the
program plays only using chris strange knowledge implementations.
In these move-sequences it could play without search tree. Therefore
the moves were found <0 seconds and the tree is only confusing the
program about the move.
How can we call this, bruce called it sniffing program. You can also
call it speculative evaluation, I call it prejudice.
A prejudice is the opposite of a set phrase/idiom/expression.
Normally an idiom/expression is an experience generalized and melted
together in an expression.
A prejudice is also a melted stuff, i don't call chris's implemented
knowledge expression to stress that CSTAL does not know if it works.
Also often it is very difficult to differenciate between
idioms/expressions and prejudices.
I think humans have experiences, prejudices and expressions/idioms and
feelings. Also an analytical tool to follow a special logic.
If you call the search-tree the logical-analysis-instrument, I would
call the evaluation-function the place of the prejudices/expressions
and experiences.
brucemo
Graham, Douglass wrote:
>
> Firstly, a couple of quickies about the WMCCC in Paris. Is there a Web site for
> it? Do spectators have to buy tickets in advance? What are the dates?
If it is like the last two, tickets will not be needed. The only web site that I
know of is the ICCA's main site, which is at http://www.dcs.qmw.ac.uk/~icca/
Here is an excerpt from that site:
"The ICCA is pleased to announce that the 1997 World Microcomputer Chess
Championship (WMCC) will take place at the Stock Exchange in Paris, France,
thanks to the most generous sponsorship of SBF - Bourse de Paris and Titus
Software. The dates are October 26 through November 3. This provides for arrival
on Saturday the 25th, with the final round on Sunday November 2. Monday November
3 is reserved for an official speed Microcomputer Chess World Championship, and a
special Gala closing ceremony, including a match between six selected computers
and six humans."
The sponsors of the event may set up another page, who knows.
bruce
brucemo
Graham, Douglass wrote:
> Supposing you took a database of high quality chess games, and devised a data
> mining technique that would allow you to extract from the database 5000 types
> (or patterns) of position (I will refer to these as "themes").[remainder snipped]
Just write a human brain, and send it to a GM for lessons. :-)
I think that is not too much more complex that what you suggest.
A visionary, a manager, and a guy with a toolbox are out walking in the jungle.
They come to a tremendous river valley with vertical sides and a rushing torent
at the bottom, and stop to figure out how to get across.
The visionary says, "We need to build a bridge."
The manager stops and thinks about this for a moment, and says, "Yeah, we need to
build a bridge. There is a mountain over there that can be mined for iron, and
there is a forest over there that can be used as a source of lumber."
The guy with the toolbox doesn't say anything, he just looks at the other two guys,
his mouth hanging open and his eyes wide.
The visionary says, "What are you looking at?"
The manager says, "Yeah, what are you looking at, we've already done 2/3 of the
work."
:-)
bruce
Jay Scott
In article <5vqnjk$2...@drn.zippo.com>, Graham Douglass wrote:
>Supposing you took a database of high quality chess games, and devised a data
>mining technique that would allow you to extract from the database 5000 types
>(or patterns) of position (I will refer to these as "themes").
>
>occur at the beginning of the game, and row 25 are themes that occur at the end
>of the game.
>
>Now you can analyse the database again, and discover, for each theme in row 1,
>how many times it links to each theme in row 2. For each theme in row 2, how
>many times it links to themes in row 3 etc. Thus, a picture of the pattern of
>chess games could be built: moreover, you know how likely you are to get from a
>given theme in one row to a given theme in the next row.
>
>This knowledge should then be made available to a chess program. In carrying out
>its evaluation at leaf nodes, the program would be looking to get to positions
>where it can easily get to a theme that wins for white (or black).
This isn't an idea yet, it's the sketch of an idea. You haven't said
what the themes would look like or how they would be used. There
are lots of different ways to fill in the sketch, and it may be that
the only thing they have in common is that the fully worked-out idea
is much more complicated than the original sketch. :-)
Nobody knows how human chess knowledge is organized, so asking whether
this is human-like may be in vain. Personally, I suspect that human
knowledge is more abstract and more flexible than this model.
That said, I think your general plan is a good one. Before we can
figure out how to use large amounts of chess knowledge, we have
to figure out what the knowledge is, and an investigation like the
one you suggest might get somewhere on that.
Jay Scott <j...@forum.swarthmore.edu>
Machine Learning in Games:
http://forum.swarthmore.edu/~jay/learn-game/index.html
Komputer Korner
Every programmer generates an opening book from databases. This is not
something unique. The question is are all the lines sound? Because of that
Ed Schroder has a specialist to manually tune all the lines for the
program's special tournament book and I suspect that all the other top
programs have someone specializing on this too. I haven't seen the
production version of CSTAL but unless Chris manually tuned the book, any
openings book created from a database will have a lot of bad lines in it.
This discussion is vastly different from your idea on themes which has
merit which I hope you pursue.
--
- -
Komputer Korner
The inkompetent komputer
If you see a 1 in my email address, take it out before replying.
Please do not email both me and the r.g.c.c. at the same time. I read all
the postings on r.g.c.c.
Graham Douglass wrote in article <6059ee$o...@drn.zippo.com>...
> In article , brucemo says...
> >Just write a human brain, and send it to a GM for lessons. :-)
> >
> >I think that is not too much more complex that what you suggest.
>
> I feel the urge to disagree with this. There are many data mining tools
on the
> market right now. People are doing some remarkable work on manipulating
the
> information locked deep inside big databases.
>
> Also, CW, the author of CS-Tal, has already demonstrated in practical
terms the
> possiblility of manipulating chess databases, by producing for CS-Tal,
from
> chess databases, an opening book which consistently leaves it well ahead
in the
> opening/middlegame.
>
> Would I be right in thinking that databases are not Bruce's area of
speciality?
>
> To programmer's who haven't done it, the building of a program to
generate legal
> chess moves, and evaluate them at high speed using selective search,
alpha-beta,
> and all the other things that Bob keeps telling us we need would seem
like a
> daunting task.
>
> >
mclane
"Komputer Korner" <kor...@netcom.ca> wrote:
>Every programmer generates an opening book from databases. This is not
>something unique. The question is are all the lines sound? Because of that
>Ed Schroder has a specialist to manually tune all the lines for the
>program's special tournament book and I suspect that all the other top
>programs have someone specializing on this too. I haven't seen the
>production version of CSTAL but unless Chris manually tuned the book, any
>openings book created from a database will have a lot of bad lines in it.
>This discussion is vastly different from your idea on themes which has
>merit which I hope you pursue.
>--
>- -
>Komputer Korner
>The inkompetent komputer
Tuning an opening book, as (opening)-experts like Cock de Gorter,
Jeroen Noomen, Alexander Kure, Eric Hallsworth, Dirk Frickenschmidt,
and and and
are doing is a qualifying way. You have massive data, and you
fintetune manually with the evaluating terms of a human beeing.
Cause humans are involved this is a very time-costing job.
CSTal has not used this approach.
The games were melted into a tree, the statistics of the followers
will be recognized in the nodes of the tree.
This is mainly what ChessBase has done, with some exceptions.
Chris invented a new data-format for the opening-books.
I would not very much call the opening book a planning tool.
It is mainly a mechanistic instrument to come into a good position.
But i think SIZE of a book does NOT say anything towards the quality
of a book. And a good book cannot be exchanged from ONE program into
usage for another program, cause the programs would not be able to
play the positions of the others as succesful.
Example ?
Johan de Konings The King 2.2 book in relation to 2.5 book.
If you change the style of the engine, the book tuning gets disturbed.
I have the feeling that many people make illusions about the sense of
a big book. I can (as a computer or as a killer-book) create very
easily a line to throw out famous big books with 2nd best or 3rd best
moves and prepare this line further to lead into a winning position
for my program. As David Levy said completely knowledged about these
questions in Computer-Schach & Spiele:
it was wrong how Kasparov played against Deep Blue.
He should have played 1...a6 and later c5 and e6 to get a kind of
sicilian.
Thoughts on planning in the evaluation function of the engine is
another thing.
The question: will search-programs be victorious over slow-evaluating
programs is a competition. Each year when programmers meet each other
whereever, they have a great joy of finding out about their programs.
As any competition, the results are not known before and anything can
happen.
This makes championships or any competitions so amazing.
During the games there is much exchange, both programmers study the
screen-output of the opponent and relate it with their programs
analysis.
What can be more interesting than an important game, that decides who
gets the title, with many kibitze sitting arround and during the game
interesting questions and discussions of all, how to evaluate the
position, good for white, for black or questions like: how do you
count the chances yourself (to the programmer).
No - that is the main difference between computerchess and
chess-matches. The participants can openly discuss live during the
game without disturbing the programs !
Dan Thies
On 22 Sep 1997 23:38:23 GMT, j...@forum.swarthmore.edu (Jay Scott)
wrote:
>In article <5vqnjk$2...@drn.zippo.com>, Graham Douglass wrote:
>>Supposing you took a database of high quality chess games, and devised a data
>>mining technique that would allow you to extract from the database 5000 types
>>(or patterns) of position (I will refer to these as "themes").
>>
>>Now, suppose you divide these themes into 25 rows, where row 1 are themes that
>>occur at the beginning of the game, and row 25 are themes that occur at the end
>>of the game.
>>
>>Now you can analyse the database again, and discover, for each theme in row 1,
>>how many times it links to each theme in row 2. For each theme in row 2, how
>>many times it links to themes in row 3 etc. Thus, a picture of the pattern of
>>chess games could be built: moreover, you know how likely you are to get from a
>>given theme in one row to a given theme in the next row.
>>
>>This knowledge should then be made available to a chess program. In carrying out
>>its evaluation at leaf nodes, the program would be looking to get to positions
>>where it can easily get to a theme that wins for white (or black).
>
>This isn't an idea yet, it's the sketch of an idea. You haven't said
>what the themes would look like or how they would be used. There
>are lots of different ways to fill in the sketch, and it may be that
>the only thing they have in common is that the fully worked-out idea
>is much more complicated than the original sketch. :-)
Problem 1: Define 5000 themes - potentially a life-long endeavor.
Problem 2: Deciding how to time-sequence things that happen at
different rates.
Problem 3: Determining where one theme ends and another begins,
since in practice you have several important concepts in play at any
given time.
Problem 4: Once you've solved the first three problems, did your
solution leave you any way to use this in a search? If it did, then
the problem is implementing it. If not, then it's back to #1....
This leaves off the question of whether any of this would be worth
doing in the first place. "Themes" may be winning or losing,
depending on whether they're right for the actual position.
>Nobody knows how human chess knowledge is organized, so asking whether
>this is human-like may be in vain. Personally, I suspect that human
>knowledge is more abstract and more flexible than this model.
We have a lot of good clues about how human knowledge is organized,
and how we reason. For example, the position-recall tests where the
chess-playing subjects were much better at real chess positions that
they were at arbitrary groupings. This indicates knowledge of
patterns, so that common groupings can be stored in memory as a single
chunk.
>That said, I think your general plan is a good one. Before we can
>figure out how to use large amounts of chess knowledge, we have
>to figure out what the knowledge is, and an investigation like the
>one you suggest might get somewhere on that.
Anyone who can find a way to develop rules and knowledge automatically
is going to impress the heck out of me.
Dan (Knowchess)
Dan Thies
On 22 Sep 1997 01:15:10 -0700, Graham Douglass wrote:
>In article , brucemo says...
>>Just write a human brain, and send it to a GM for lessons. :-)
>>
>>I think that is not too much more complex that what you suggest.
>
>I feel the urge to disagree with this. There are many data mining tools on the
>market right now. People are doing some remarkable work on manipulating the
>information locked deep inside big databases.
I've been trying to figure out a way to use large-scale data mining
for quite a while. Probably before anyone started calling it data
mining. Perhaps you could give an example or two of what kind of
information you think you could extract, and how it might be done.
So far I haven't seen you put forward any concrete scheme.
A few years ago there was a paper in the JICCA about using a database
to try to get a better scoring of knight vs. bishop. This kind of
thing could be done in other ways, too.
I have used databases as a diagnostic for Knowchess, by
hand-classifying the positions and then seeing how many it missed,
writing rules for the ones that got missed, etc.
When I had an a-b program going, I tried using database positions to
develop tuned evaluation functions for different openings, so that the
piece/square tables were different out of a Sicilian than out of a
QGD. Results were OK, but the larger the book, the bigger the
classification problem gets and the smaller the book, the bigger the
problem of early book exits becomes.
>Also, CW, the author of CS-Tal, has already demonstrated in practical terms the
>possiblility of manipulating chess databases, by producing for CS-Tal, from
>chess databases, an opening book which consistently leaves it well ahead in the
>opening/middlegame.
Everybody does this. You think somebody sits down and does a 200,000
position opening book by hand?
>Would I be right in thinking that databases are not Bruce's area of speciality?
I'd be surprised if he didn't know as much as you...
>>A visionary, a manager, and a guy with a toolbox are out walking in the jungle.
>>They come to a tremendous river valley with vertical sides and a rushing torent
>>at the bottom, and stop to figure out how to get across.
>>
>>The visionary says, "We need to build a bridge."
>>
>>The manager stops and thinks about this for a moment, and says, "Yeah, we need
>>to
>>build a bridge. There is a mountain over there that can be mined for iron, and
>>there is a forest over there that can be used as a source of lumber."
>>
>>The guy with the toolbox doesn't say anything, he just looks at the other two
>>guys,
>>his mouth hanging open and his eyes wide.
>>
>>The visionary says, "What are you looking at?"
>>
>>The manager says, "Yeah, what are you looking at, we've already done 2/3 of the
>>work."
>
>So - what was the workman's solution?
Swimming lessons.
Dan (Knowchess)
brucemo
Graham, Douglass wrote:
>
> In article , brucemo says...
> >Just write a human brain, and send it to a GM for lessons. :-)
> >
> >I think that is not too much more complex that what you suggest.
>
> I feel the urge to disagree with this. There are many data mining tools on the
> market right now. People are doing some remarkable work on manipulating the
> information locked deep inside big databases.
I don't think chess will respond to this approach. Sometimes you will see a
position that is in a class, and a strong player can make a statement such as,
"The key to winning such positions is ..." However there is even then enough
uniqueness that to really grok a position would require in-depth understanding of
the tactical nuances of *that* position.
A reason chess can captivate a person for an entire lifetime is that the game
constantly provides something new.
> Also, CW, the author of CS-Tal, has already demonstrated in practical terms the
> possiblility of manipulating chess databases, by producing for CS-Tal, from
> chess databases, an opening book which consistently leaves it well ahead in the
> opening/middlegame.
This is a different kind of thing entirely. CST's opening book generator isn't
going to be solving any Nolot positions.
I think I can write something that makes a fairly good book, but I haven't done
it. I have a mixture of machine- and human-generated lines in my book, and I
didn't have the foresight to differentiate between the two. So to make a new
book will be a difficult and risky undertaking for me.
I think I may start doing this after Paris, though.
> Would I be right in thinking that databases are not Bruce's area of speciality?
I am a software engineer with experience in a lot of areas. My number one area
of specialty would have to be, by far, computer chess. Second to that would be
information retrieval (as in full-text boolean search relevancy ranking
nonsense), I originated two trivial patents in this area, and wrote a couple of
systems that shipped to lots of people.
I was in a member of the "Access" (database) team at Microsoft for a while, but I
didn't do anything non-trivial.
Currently, I am doing computer chess, because that is what I want to do.
bruce
Dan Thies
On 23 Sep 1997 09:49:38 -0700, Graham Douglass wrote:
>In article , rt...@wt.net says...
>>I've been trying to figure out a way to use large-scale data mining
>>for quite a while. Probably before anyone started calling it data
>>mining. Perhaps you could give an example or two of what kind of
>>information you think you could extract, and how it might be done.
>>So far I haven't seen you put forward any concrete scheme.
>
>Guilty as charged. I fully understand that to implement my ideas would take a
>great deal of effort, time and commitment.
>
>Have you attempted to extract info from a database using a data mining tool?
What I tried to do was to classify middlegames by pawn structure, so
that I could develop different evaluation function parameters for
different middlegames. That all went in the "try later" file when I
had this sudden rush of insight into how I could use an expert-system
instead.
I still think classification by pawn structure is probably the best
way to start looking into it, or maybe by the ECO codes of the
opening. Some ECO codes will map to openings that lead to vastly
different middlegames, though. The QGD, for example, so you'd have
to get into finer classifications than that with openings. It sure
got tricky when I started trying to do diifferent evals based on the
opening.
>>Everybody does this. You think somebody sits down and does a 200,000
>>position opening book by hand?
>
>Some chess computer opening books are written by hand. If everybody is using the
>same techniques to build opening books, why is CS-Tal's book reputed to be so
>much stronger than all of the others?
Everybody starts with a database, then they tune it by hand, or they
let the program learn in some way. Chris has had CST in development
for some years now, so who knows? Reputation is just reputation, and
Chris is a pretty good self-promoter. When (if) it is released
commercially, the opening book will be open to greater scrutiny than
is now possible. Right now, we see the few games they play in
tournaments, and those that they choose to release.
>>>Would I be right in thinking that databases are not Bruce's area of speciality?
>>
>>I'd be surprised if he didn't know as much as you...
>
>OK, I didn't mean to insult Bruce's intelligence, and I apologise if that's how
>it came across (better be nice to him or he won't buy me a beer in Paris :-) )
>
>I work with large databases as a major part of my job, and I take a special
>interest in the area of obtaining knowledge from them.
>
>The point I was trying to make was that I think that somebody who had no
>programming experience in either area might well find it as easy to implement my
>idea as to write a "Ferret". The skills required, however, would be different.
Point is taken - it's my experience with playing chess that tells me
this is a huge undertaking - you might discover that there are
thousands of important concepts and that they combine in very amazing
ways to make chess a very interesting problem.
Dan