Computer Chess Planning
Mike Stoker
As a very interested newcomer to computer chess programming, I was wondering if
anyone has implemented the following idea / has any thoughts on its feasability.
The architecture is based on the premise that the best move in a given position has
a "reason" behind it i.e. it is a logical conclusion of the features of the
position, and forms part of a larger plan.
I am currently toying with the idea of attempting to implement a neural network
type system, (It would be large, and probably need to be self learning), in which
each node represents a "plan" or a "feature" of the position. Each of these nodes
is composed of sub-nodes. For instance a node representing "checkmate the king"
would be composed of sub-plans "ensures that king cannot move to any surrounding
square" and then a sequential plan of "deliver check on a square where the piece
cannot be taken". At the very lowest levels, the nodes would represent such things
as "obtain white pawn on e4" - this would feed into a feature such as
"obtain control of centre squares", etc etc. (note that "control of centre squares"
is a feature, "obntain control of centre squares" is a plan - are the two
interchangable in all circumstances?). Each plan would have a weight atteched to
it, which represents its value (i.e. obtain checkmate is far more valuable than "win
a weak pawn"). The activation of the plan would be determined by the number of
sub-plans feeding into it which have already been completed, combined with the
difficulty of completing the sub-plans.
If anyone has any suggestions as to where I can find recent research papers into
computer chess planning, then I would be very grateful for the information.
Mike Stoker
Mike Stoker
Andrew Tridgell
Mike Stoker wrote:
>
> As a very interested newcomer to computer chess programming, I was wondering if
> anyone has implemented the following idea / has any thoughts on its feasability.
>
[interesting ideas on chess planning deleted]
I think there is a lot of potential for chess programs
to improve by adding some sort of planning code. But
I think they should augment, rather than replace the
existing tree-search methods.
I've been thinking of adding a simple planning module
to KnightCap. I would dedicate one CPU to the planner,
which would then communicate its results to the other
nodes by modifying a piece-square table. Thus the
planner would influence the search but not replace it.
For example, if the planner decides that a attack on the
queen side is appropriate it would increase the board control
and piece-square values on the queen side. The more
confident it gets that this is the right plan, the more
it would increase the value.
I've also done a few experiments on search-depth and positional
play. I took a couple of the "positional" test suites from
the gnuchess CHESSTEST directory and tried them on KnightCap
with different time controls. KnightCap got a lot more
of them right with longer time to think. This supports
the theory that strategy is just deep tactics :-)
On a different front I've also tried increasing the
"piece-trapped" penalty in KnightCap to see if it
can overcome the common flaw of not being able to
extricate a trapped piece (which KnightCap has
suffered from several times). I upped the penalty
to over a pawns value. The game against gkMM (another
computer) in journal slot J on FICS illustrates the
result. KnightCap actually went out of its way to trap gkMMs
queen side pieces and succeeded! They were never able
to develop and KnightCap won, despite being materially
down most of the game.
Cheers, Andrew
Chris Whittington
--
http://www.demon.co.uk/oxford-soft
Andrew Tridgell <Andrew....@anu.edu.au> wrote in article
<332D014C...@anu.edu.au>...
> Mike Stoker wrote:
> >
> > As a very interested newcomer to computer chess programming, I was
wondering if
> > anyone has implemented the following idea / has any thoughts on its
feasability.
> >
>
> [interesting ideas on chess planning deleted]
>
> I think there is a lot of potential for chess programs
> to improve by adding some sort of planning code. But
> I think they should augment, rather than replace the
> existing tree-search methods.
>
> I've been thinking of adding a simple planning module
> to KnightCap. I would dedicate one CPU to the planner,
> which would then communicate its results to the other
> nodes by modifying a piece-square table. Thus the
> planner would influence the search but not replace it.
>
> For example, if the planner decides that a attack on the
> queen side is appropriate it would increase the board control
> and piece-square values on the queen side. The more
> confident it gets that this is the right plan, the more
> it would increase the value.
This is done by quite a few programs already (pre-processing).
It's obviously better than nothing at all, but suffers from the drawback
that the further the position gets from the root position the more the
assumptions made at the root (in filling the piece-square tables) become
invalid.
So its a perfetcly good strategy for a chess program when hardware/software
status is relatively 'backward', but fails more and more as processors get
faster and algorithms become more refined.
>
> I've also done a few experiments on search-depth and positional
> play. I took a couple of the "positional" test suites from
> the gnuchess CHESSTEST directory and tried them on KnightCap
> with different time controls. KnightCap got a lot more
> of them right with longer time to think. This supports
> the theory that strategy is just deep tactics :-)
One problem here is that test suites are often created to be on the
borderline between what current chess program technology can solve and what
it can't.
Or, alternatively, what deeper search can find.
So, curiously, the test suites support the 'just one more ply' approach.
>
> On a different front I've also tried increasing the
> "piece-trapped" penalty in KnightCap to see if it
> can overcome the common flaw of not being able to
> extricate a trapped piece (which KnightCap has
> suffered from several times). I upped the penalty
> to over a pawns value. The game against gkMM (another
> computer) in journal slot J on FICS illustrates the
> result. KnightCap actually went out of its way to trap gkMMs
> queen side pieces and succeeded! They were never able
> to develop and KnightCap won, despite being materially
> down most of the game.
Neat :)
But this sort of strategy will lose you games as well. Whenever the
over-bias happens to be inappropriate.
That's the problem with trying to be positional and speculative with an
evaluation function.
Chris Whittington
Vincent Diepeveen
>As a very interested newcomer to computer chess programming, I was wondering if
>anyone has implemented the following idea / has any thoughts on its feasability.
>
>The architecture is based on the premise that the best move in a given position has
>a "reason" behind it i.e. it is a logical conclusion of the features of the
>position, and forms part of a larger plan.
>
>I am currently toying with the idea of attempting to implement a neural network
>type system, (It would be large, and probably need to be self learning), in which
>each node represents a "plan" or a "feature" of the position. Each of these nodes
>is composed of sub-nodes. For instance a node representing "checkmate the king"
>would be composed of sub-plans "ensures that king cannot move to any surrounding
>square" and then a sequential plan of "deliver check on a square where the piece
>cannot be taken". At the very lowest levels, the nodes would represent such things
>as "obtain white pawn on e4" - this would feed into a feature such as
>"obtain control of centre squares", etc etc. (note that "control of centre squares"
>is a feature, "obntain control of centre squares" is a plan - are the two
>interchangable in all circumstances?). Each plan would have a weight atteched to
>it, which represents its value (i.e. obtain checkmate is far more valuable than "win
>a weak pawn"). The activation of the plan would be determined by the number of
>sub-plans feeding into it which have already been completed, combined with the
>difficulty of completing the sub-plans.
>
>If anyone has any suggestions as to where I can find recent research papers into
>computer chess planning, then I would be very grateful for the information.
>
>Mike Stoker
>
>sto...@logica.com
>
If you want to implement ideas, using a self learning network,
then think of this: every human is a self learner. They are the best
example (although much more complex and although one cannot really compare
them as humans are intelligent and computers are not).
There are millions of people which learn the rules of chess,
and only very few of them play well. So this gives a learning network a
small chance.
Second, no network so far has
by accident shown good chessplay, so i would even decrease that 0.0000001
chance that a selflearning neural network will be great success. Furthermore,
the time a human needs before (s)he plays chess quite well is measured
in years. This means that every network would require many years of development
and i guess you don't have the time for this, as most of the people who
try neural networks try to let them play considerable good chess within
few weeks/hours. They should use more determination!
Last but not least, the network should contain enough room
to store all complex patters a grandmaster uses when playing chess.
How can you conclude the same about a positions strategics if you don't
consider the same amount of knowledge; if your neural network is not
able to store all the 'useful' knowledge it learns about, how can it
when it plays the decisive match against K (Kramnik or so) restore
the same plan/concept/strategy from memory?
Good luck with it!
Don't think too long!
Vincent.
--
+----------------------------------------------------+
| Vincent Diepeveen email: vdie...@cs.ruu.nl |
| http://www.students.cs.ruu.nl/~vdiepeve/ |
+----------------------------------------------------+
Komputer Korner
Andrew Tridgell wrote:
>
> > I am currently toying with the idea of attempting to implement a neural network
> > type system, (It would be large, and probably need to be self learning), in which
> > each node represents a "plan" or a "feature" of the position. Each of these nodes
> > is composed of sub-nodes. For instance a node representing "checkmate the king"
> > would be composed of sub-plans "ensures that king cannot move to any surrounding
> > square" and then a sequential plan of "deliver check on a square where the piece
> > cannot be taken". At the very lowest levels, the nodes would represent such things
> > as "obtain white pawn on e4" - this would feed into a feature such as
> > "obtain control of centre squares", etc etc. (note that "control of centre squares"
> > is a feature, "obntain control of centre squares" is a plan - are the two
> > interchangable in all circumstances?). Each plan would have a weight atteched to
> > it, which represents its value (i.e. obtain checkmate is far more valuable than "win
> > a weak pawn"). The activation of the plan would be determined by the number of
> > sub-plans feeding into it which have already been completed, combined with the
> > difficulty of completing the sub-plans.
> >
> > If anyone has any suggestions as to where I can find recent research papers into
> > computer chess planning, then I would be very grateful for the information.
> >
> > Mike Stoker
> >
> > sto...@logica.com
This whole argument seems to be suspiciouly like the argument between
root processors and tip processors. So far the tip processors are
winning and they always have, but that is not to say that a combination
of the 2 might not triumph in the end. However root processing by itself
will never replace AlphaBeta thus end of argument. Therefore the
discussion should focus on what plans are best - most practical and
how can they be incorporated along side the alpha beta.
--
Komputer Korner
The inkompetent komputer.
Anders Thulin
In article <5ggr5s$b...@romeo.logica.co.uk>,
Mike Stoker <sto...@logica.com> wrote:
>I am currently toying with the idea of attempting to implement a neural network
>type system, (It would be large, and probably need to be self learning), in which
>each node represents a "plan" or a "feature" of the position.
Each input node, I assume. But what is the output of the NN? The
next move? Or plans/features that would be useful to pursue?
Each of these nodes
>is composed of sub-nodes. For instance a node representing "checkmate the king"
>would be composed of sub-plans "ensures that king cannot move to any surrounding
>square" and then a sequential plan of "deliver check on a square where the piece
>cannot be taken".
Now you've lost me. Are you talking about input or output?
As I understand NN's, input nodes can only provide information if a
particular feature is present in the position or not. Thus it would
be possible to have a node for 'king mobility'. An output node could
wery well be connected to the idea of 'decrease king mobility'.
As regards input nodes, a self-learning system would probably need
to be able to dynamically extend both the number of input nodes (and
thus the size of the hidden layers), and possibly even the number of
hidden layers.
I assume you know of some way to do so without destroying the
existing network. I would expect a complete retraining would be
necessary if such a modification took place, but I'm not an expert on
NNs.
>interchangable in all circumstances?). Each plan would have a weight atteched to
>it, which represents its value (i.e. obtain checkmate is far more valuable than "win
>a weak pawn"). The activation of the plan would be determined by the number of
>sub-plans feeding into it which have already been completed, combined with the
>difficulty of completing the sub-plans.
Since there's no indication of just how to move from plan/sub-plan
to execution, I assume the NN output would be used as input to the
scoring function of a traditional chess engine, and modify the weights
of the scoring features. If it is important to reduce mobility,
opponent mobility would be re-weighted accordingly -- if it was
important to increase or decrease the 'load' on a particular piece,
other weights would be readjusted, etc.
Interesting idea. I don't at all see how the NN could be trained,
though, nor how it could be made extensible. But problems are to be
solved.
--
Anders Thulin Anders...@lejonet.se 013 - 23 55 32
Telia Engineering AB, Teknikringen 6, S-583 30 Linkoping, Sweden