Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Teaching computers to think

Author: Vasik Rajlich

Date: 06:17:31 03/15/04

Go up one level in this thread


On March 15, 2004 at 08:47:38, Andrew Wagner wrote:

>	I got to thinking last night. This is a very bad idea for people like me who
>are not experienced at it. Folks, don't try this at home. So... what was I
>thinking about? Thinking. Bear with me here folks, this is kind of a long post.
>
>
>	Computers and humans really think in quite opposite approaches. In classic
>alphabeta, we start by generating all legal moves and throwing out the bad ones
>until (hopefully) we have the one good one left. But of course no human thinks
>like this. They start with NO moves, and use positional, tactical, and pattern
>considerations to generate just a few possible good moves. Then for each of
>those moves, they again generate just a few responses (rather than every legal
>response as alphabeta would), and so on.
>
>	Now, in one sense humans search much more efficiently than computers. Because
>they don't look at ridiculous captures like queen takes pawn which is defended
>by another pawn, they are saved a lot of time and effort. The flipside of this
>is that computers are ABLE to look at millions of these ridiculous captures in
>the time it takes a human to look at just a few moves.
>
>	However, if you think about it, human searching can hardly be called efficient
>most of the time. I mean really, for those of you who play, how often to you
>calmly, coldly calculate your way through a tree like described above? We tend
>to skip steps, jump around in our thinking, get distracted, and so on.
>
>	So, the question becomes...What if a computer could codifiy that thinking
>process, using existing techniques like pruning, extensions, hash tables, and so
>on, to change the shape of the tree **based on positional considerations**. Let
>me illustrate with a position here.
>[d]r1b1q1k/pQp/2p1p3/p1PpP3/P2N1P1B/2P1R3/6PP/3n2K1 w - -
>
>White has sacrificed a rook to reach this position, and now unleashes a surprise
>queen sacrifice for mate in 6. Qxg7+ Kxg7 Bf6+ Kg6 Bg7+ Kh5 Rg5+ Kh4 Nf3#.
>
>	So for any engine which has check extensions, this tactic should be easy,
>right? But, how many times will check extensions prove to be a waste of time? I
>mean, if the king is well-defended, it's silly to search a line where you
>sacrifice all your pieces to break open the king, only to discover that you have
>nothing left to mate him with.
>
>	But in this position, it's easy to see that check extensions are called for.
>Look at black's pieces. 4 of the 5 are on the first rank. Look at the center.
>It's completely closed, making fast movement of pieces to defend the king
>impossible, and white has more space. Look at white's pieces. They all point
>menacingly towards the black king. If you're well-trained to look for it, it
>should be easy to realize that some kind of sacrifice to drag the king into the
>open should be considered.
>
>	Many advances have been made in chess programming. We have some amazingly
>sophisticated techniques and shortcuts. But we're still brute-forcing our way
>through. Can't we instead start looking at the human thought process involved in
>chess, and define it in terms of these different techniques? This way, rather
>than simply trying every technique on a position and hoping one of them works
>and offsets all the time wasted on inadequate techniques and silly lines, we
>would have a toolkit to use, and can pick a tool based on the position, just
>like humans do.
>
>	Here are three ideas I had about how to "nail down" the way humans think:
>
>	1.) Show positions to a strong player, and have him say/write/type the first
>thing that comes to his mind. This "inkblot" sort of approach, repeated many
>times over, would give us some kind of indication as to what really the key
>factors are in a position.
>
>	2.) During the course of a series of games, have a strong player (or two strong
>players, playing each other) write down the first thing that comes to mind when
>a move is made by his opponent. This could give us tremendous insight into move
>ordering techniques.
>
>        3.) Take some classic books like Fine's Endgame book, or Vukovich's "Art
>of Attack" and translate them into terms of search techniques like extensions
>and pruning.
>
>
>	Now some may be thinking that these ideas would seem to be representative of
>the classic brute-force approach. But what I'm really suggesting is not only
>move-ordering, but move-list generation, based on positional considerations. Of
>course, some brute-force will still be required, just to make sure everything is
>tactically sound. But it seems to me that we are doing things backwards to use
>brute force, and prune from there, instead of to "un-prune" some moves first,
>and brute-force to see if we can beat that.
>
>	One final thing: I realize that I'm a young, naive, beginner chess-programmer,
>and suggesting these things is the equivalent of a 2-year-old questioning
>newtonian physics. So please, don't bother informing me of this, I already know
>it. I also realize that some or most of these ideas have probably been suggested
>before. But if nothing else, I hope this leads to an interesting discussion on
>why we do things the way we do. Thanks for reading, and I look forward to your
>responses.

Hi Andy,

I'm only a few months ahead of you - so take this too with a grain of salt. At
first glance, selective search looks like a fairly easy thing to do. Obviously,
there must be some good ways to conclude that in some positions, passed pawn
pushes, checks, sacrifices, etc, are dangerous, and in others they are not.
Furthermore, it must be good to search good moves more deeply than bad moves.
(ie. Rac1 moving rook to an open file, vs Rca1 moving the rook back to a closed
file.)

However, it's not easy to make this work. I have tried a number of selective
search ideas and have not gotten very far. (By selective search I don't include
null move, and stuff near the leaves or under the leaves, ie q-search, I mean
fundamental selective search.) The only selective searching which I've found
which clearly improves my engine is check extensions. I think there are two
principle which work against selective search.

1) If you invest some # of nodes X to extend a line, then cutting the same # of
nodes from another line will cost you more depth in that line.
2) Each subsequent ply of search is more important than the previous one.

So, any selective searching has to be fundamentally correct enough to overcome
the burden of these two issues.

Of course, selective search if done right will work, the commercial programs
prove this. At the moment, I am completely re-doing my evaluation. I think
selective search must be tied to the evaluation, and in particular the part of
the evaluation which measures the high-value aspects of a position. In the
middlegame, this is king safety. In the endgame, this is passed pawns.

Re. the issue of how humans do it, I think it's not so important. If humans
could calculate 1M nodes/second, they'd be doing things differently anyway.

Good luck with Trueno.

Vas



This page took 0.01 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.