Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Symbolic: From bitboards to ideas

Author: Christophe Theron

Date: 12:00:44 03/14/04

Go up one level in this thread


On March 13, 2004 at 11:52:07, Steven Edwards wrote:

>Consider the position BWTC.0025:
>
>[D] r1bq1r1k/ppp1N1p1/7p/2bp1pN1/2Bn1B1Q/8/PP3PP1/R3R1K1 w - - 0 1
>
>It's a mate in three starting with 1. Qxh6+; however, I picked it for an example
>as it also has a number of possible knight forks for White.
>
>A traditional chess programs can discover knight forks only by search.   A goal
>for Symbolic is to recognize tactical motifs via pattern matching, use these
>ideas for plan formation, and then use the plan to guide a very narrow search to
>produce a verification of the plan.



I do not want to criticize your efforts to conduct a narrower, smarter search,
because I believe that there is something to be gained from this.

However I would like to point out that using a classical alpha-beta approach
improved by state-of-the-art selective search techniques, current top chess
programs have a branching factor that is clearly below 3.

That means that at any point in the search tree, the average number of moves
searched is somewhere between 2 and 3.

And that's for all the positions, including quiet positions where no tactical
move(s) are obvious and endgame positions where ANY move including the most
unexpected one can lead to a win.

And that's without having to list every possible pattern (fork, checks, pins,
and so on, this list can be extremely long).

And current programs based on alpha-beta and selective search will miss very
rarely a tactical shot, be it an "obvious" move (a fork) or not.

You say that one of your goals would be to "use the plan to guide a very narrow
search".

I do not believe that this goal will produce anything better than what current
chess programs are able to do. I even believe that it will produce results
inferior to what current chess program can do (more tactical holes), and it will
be much slower.

Think about it: what do you want to do? You want to write a large number of
small algorithms, each being able to generate a list of potentially interesting
(threatening) moves, and then search only those moves.

There is another way of doing this: instead of generating only the interesting
(threatening) moves, just generate all the moves, look at the resulting position
and decide if the side to move is threatened. Or in other words, do all the
moves, play a null move and call the quiescence search in order to decide if you
are going to search this move deeper or not.

This is already known as doing a null-move search with a big value for R (the
reduction factor after the null move). This is known to produce very bad
results.

So you can work for several months, listing all the possible ways to make
threats, write all the individual algorithms belonging to all those classes, and
you will end up with something worse than a classical null move search with a
big R. It will be worse because it will have more holes (if it does not have
then it might have a worse branching factor) and it will be much slower in term
of NPS. At the very best, it will produce similar results but much, much slower.

The conceptual difference between your approach and a standard null-move search
with a big R value is that you do not generate all the moves. You can say that
your approach is an additive one (I start with an empty list of moves and add
those that are interesting) while the null-move search is a substractive one (I
start with the list of all moves and I remove those that are not interesting).

I admit that an additive approach looks more like what a human player does.

However, by being more "human-like" you are already making a big sacrifice. You
know right from the start that you are not going to produce anything better than
a more "mechanical" approach. Worse, you know that it will be much slower.

It's clearly not a very motivating path.

I would suggest to use "pattern recognition" in a different way: build a
standard alpha-beta chess program in LISP. Let it have a simple evaluation
function, just based on pawn structure and piece centralization (you can simply
use piece square tables).

When it works, add pattern recognition to achieve the following:
* better evaluation: identify special patterns to evaluate successfull king
attacks, outposts, bad bishops, blocked/locked pieces...
* selectivity: when the position does not feature any interesting tactical or
positional pattern, cut the branch or just reduce its search depth.
* extensions: when some special patterns are found, increase the search depth.

Maybe I have misunderstood what you are trying to do. Maybe your goal is to do
what I suggested above.

Or maybe you have an even better idea.

I just wanted to give you my ideas on the subject.



    Christophe





>So, here's some sample test code to recognize, without search, potentially
>interesting knight forks.  It's an example of bridging the gap between bitboards
>and ideas.
>
>(defun SKF (MyFEN)
>    "Interactive tester for SuggestKnightForks"
>    (let* ((PosVal (PosValFromFEN MyFEN)) (MoveVals (GenerateVal PosVal)))
>        (SuggestKnightForks PosVal MoveVals)))
>
>(defun SuggestKnightForks (MyPosVal MyMoveVals)
>    "Return a list of potential knight fork ideas"
>    (let*
>        (
>            (Ideas nil)
>            (AColor (ActiveColorFromPosVal MyPosVal))
>            (PColor (OtherColor AColor))
>            (VictimBB
>                (BBAndNot
>                    (BBLocByColorPV MyPosVal PColor)
>                    (BBLocByManPV MyPosVal (ManFromColorPiece PColor Knight))))
>            (MoveVals
>                (SelectMoveValsByFrMan
>                    MyMoveVals
>                    (ManFromColorPiece AColor Knight)))
>        )
>        (dolist (MoveVal MoveVals)
>            (let ((Idea nil) (VictimManSqList nil))
>                (setf VictimManSqList
>                    (SortRevManSqList
>                        (ManSqListFromPosValBB
>                            MyPosVal
>                            (BBAnd
>                                (AttackByKnightBB (ToSqFromMoveVal MoveVal))
>                                VictimBB))))
>                (when (> (length VictimManSqList) 1)
>                    (setf Idea
>                        (list
>                            (list 'try MoveVal)
>                            (list 'escape (first VictimManSqList))
>                            (list 'capture (second VictimManSqList))))
>                    (format t "Idea: %u %n" Idea)
>                    (push Idea Ideas))))
>        Ideas))
>
>Running the above with BWTC.0025 produces:
>
>Idea: ((try Nxf5) (escape (BlackPawn h6)) (capture (BlackPawn g7)))
>Idea: ((try Ng6+) (escape (BlackKing h8)) (capture (BlackRook f8)))
>Idea: ((try Nf7+) (escape (BlackKing h8)) (capture (BlackQueen d8)))
>Idea: ((try Ne6) (escape (BlackQueen d8)) (capture (BlackRook f8)))
>Idea: ((try Nc6) (escape (BlackQueen d8)) (capture (BlackPawn a7)))



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.