Author: David Mitchell
Date: 13:33:37 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. Lots of major differences between human thought and computer "thinking". We explore things, computers "explore" exactly what we program them to, in the manner we program them to, right down to the nth degree. If they use fuzzy logic or any inductive abilities, they do so because we have taught them _exactly_ what fuzzy is and here's how to do it. Computers explore only on a leash, and in your "backyard", as it were. We don't have a clue how to build a computer that "thinks", and that's a good thing, or Isaac Asimov's fiction becomes a strong possibility for reality. Without really understanding thought, we can't really understand how strong chess players decide on a move, and studies have shown, the GM's don't really understand the process, at all, either. Is it something they remember studying? (surely so, occassionally), or just a strong pattern similarity? Certainly they do some "searching" along selected lines. With our current tools of programming, it's not productive to try and teach a computer what makes a position "analagous" to another position - why a pawn or king one square moved, may be an entirely different position to attack or defend, then another one. Whatever the computer does, we need to remember the chess clock is ticking, and computer resources (although larger today), are certainly limited compared to the human brain. It would be great if the computer could do _one_ thing, do it well, and play the right move. So far, exhaustive search, with various pruning methods, has given us that _one_ thing. Instead of trying to find hundreds of possible rules for smarter searching, which may or may not be applicable to the position at hand, we have a hundred improvements to _one_ search and evaluation. Puts the focus right on the nose. It surely seems not the smartest, but it may be the most efficient way to teach a computer to play chess. Some intelligence has been found useful however. Crafty is one example of this. When Crafty's king is in check, the move generator changes from pseudo-legal, to perfectly legal move generation, only. Having a separate pawn hash. How the king should deal with two separated, single, pawns, which are both free to run down and get promoted. Your idea's are good, but there has not been the ability to find lots of those elusive "terms" (from Fine's book or other's), which work in the vast majority of games, and provide an advantage in strength, as a result. Some very basic idea's have worked well, of course. Like driving the opponent's king to the edge or corner of the board. Again, basic stuff, that nearly always will apply to the position OTB. Perhaps programs like Symbolic will help lead the way to a smarter CC program. It is surprising though, how much just small incremental improvements, (and of course, much faster and more powerful computers), have improved CC play. dave
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.