Author: Bruce Moreland
Date: 10:17:34 11/06/00
Go up one level in this thread
On November 06, 2000 at 11:59:49, Christophe Theron wrote:
>Tiger uses several different pruning mechanisms (some are well-known, some are
>more obscure) in combination with each other. Usually when you do that you
>weaken your program. Part of my work has been to teach these pruning algorithms
>how to live together without burning the house.
>
>In the past 5 years I have worked 80% of the time on search, and I believe I
>have "invented" several interesting pruning mechanisms. I'm pretty sure however
>that other programmers have "invented" them as well, but maybe nobody else
>managed to have all of them working together?
I think you are probably on the right track with this.
>I do a little of root processing for obvious things. But most of my evaluation
>is done in the leaves. For example, king attack evaluation is done in every
>node.
>
>My make/unmake routines update evaluation terms incrementally instead of
>computing everything from scratch at each node. It is much more difficult to
>work like this, because your make/unmake routines become pretty complex.
>
>Just one example: evaluation of "rooks on open files". The term is re-evaluated
>if the program sees that the move:
>* moves a rook
>* moves a pawn on another file
>* captures a rook
>* captures a pawn
>
>So you can imagine what a mess it is when you add 20 or 30 additional terms...
>But it works. This is also why bitboards would not help me much.
I tried a simple form of this recently. If you hash pawn structures you can get
that information pretty quickly, so it is easy to write an incremental evaluator
if you evaluate pieces only via their location and relationship with pawns. But
that kind of eval is very simple and misses a lot of nuances. For instance,
rook on the 7th should be more potent based upon the location of the enemy king.
It sounds like you are talking about something more complex.
I've thought about building some sort of dependency tree but I couldn't figure
out a fast and manageable way to implement this. That would be really cool if
it could be done, because you could add terms, hook up a few wires, and the
program could manage the whole thing itself.
As of now mine is a tip evaluator, it just goes through the piece lists and does
it, mostly. Some stuff is kept incrementally but it's not important stuff.
>I almost don't use lazy eval. Obviously, it would not be work with Gambit
>Tiger's huge positional evaluation of king safety.
I did have working lazy eval until recently. I had some big-term unavoidable
stuff I did at the beginning, but some other stuff was pretty expensive but
couldn't produce really big terms. So if I knew that I was out of the window,
and the rest of the eval couldn't get me back within it, I could prune out some
pretty expensive stuff.
As of now I'm doing king safety last, so that does sort of throw the lazy eval
idea out.
>> Are you winning games because you
>>are ungodly fast or is it some other reason? Everyone's eval terms look great
>>when they outsearch the opponent by four plies.
>
>
>
>I'm not that fast, but it's true my trees are rather small due to massive
>pruning.
>
>So I can go pretty deep. But it is not enough to go deep. Your evaluation has to
>be reasonnably accurate, or else you'll lose anyway. Of course you know that.
>
>A program that wins by outsearching its opponents is rather easy to "detect":
>it's a program that is able to play senseless moves ("playing with no idea"),
>and still win in the end. Reminds you of some famous program? Is it the way
>Tiger plays in your opinion?
I have no negative impressions of Tiger, it seems to be very strong even on slow
processors. That I found this to be true is a major reason I have been working
on my program recently.
>>In this particular position, what are you seeing? The position can be viewed in
>>any of several ways:
>>
>>1) One way is a very blunt approach, which involves detection of open lines
>>without being very interested in what is on the open lines. It's typical for a
>>program to award a bonus for an open file into the enemy king position, without
>>bothering to see if there is a rook on the file.
>>
>>2) You can be more sophisticated and say, here are some open files into the
>>king, and here are some open diagonals into the king, and here are some pieces
>>on those files and diagonals, and these pieces seem pretty close to the opposing
>>king, and here are the defenders. You can mash this all up and produce a value.
>>
>>3) You can be even more sophisticated and try to determine which points are
>>vulnerable to being overcome through direct attack, perhaps even explore some
>>means of increasing attack or defense of those points.
>>
>>I have made numerous tries with Ferret. Versions up until now have been
>>somewhere between #1 and #2.
>>
>>The original version just took into account structural defects, it would add and
>>subtract various numbers of centipawns for open files into the king position, or
>>various defects in the pawn structure, without taking into account whether the
>>open files were inhabited, and without noticing queen location or open diagonals
>>or whether the board was bisected by locked central pawns and so on. This
>>worked OK, but then again almost everything does. It was vulnerable to getting
>>ripped by humans, but computers didn't give it much trouble since they didn't
>>attack.
>>
>>I tried to add much of this stuff into versions of my program that have been
>>seen publicly over the past few years. The program still didn't have any
>>knowledge of open diagonals, and it didn't check to see if rooks inhabited open
>>files, but it did try to figure out where the queen was, and if there were any
>>pieces planted on strategic squares like f5, and it tried to figure out if there
>>was a central pawn configuration that it needed to be concerned about.
>>
>>My intent was several-fold:
>>
>>1) Try to create a speculative attacker.
>>2) Try to avoid getting munched by aggressive humans.
>>3) Try to create something that was sensibly aggressive with pawns.
>>
>>I had some successes with this, and a few times the program generated nice
>>attacks, against both humans and computers, but I wouldn't call it sensibly
>>speculative. It was probably quite successful against humans, not that it got
>>much chance to try.
>>
>>Within the last few days I've redone king safety again. The newer version knows
>>about rooks and bishops striking into the king position, and it can handle rook
>>lifts and so on. It divides the minors into primary and secondary attackers, a
>>primary attacker being right in there, and a secondary attacker having a good
>>chance of swinging over into attack, but not necessarily attacking right now.
>>It also figures out if a rook has a clean line into the king position, and if so
>>it regards that as a primary attacker.
>>
>>It figures out the status of the queen, which is also given the status of a
>>primary or secondary attacker. After everything is counted, I convert the above
>>into a score. The score can be huge, like five or six pawns, mostly based upon
>>the presence of a supported queen.
>>
>>This version attacks a lot more than older versions, and seems to be making good
>>decisions. It got a lot of pieces around the enemy king and blew through a
>>couple of times today, and it sacrificed pawns a few times and the exchange once
>>or twice. It's only played 12 games but it won 8 of them, against apparently
>>pretty tough computer opponents, and I think I can make it quite a bit better
>>with a bit of messing around. Also, I used it to watch games in the CCT2
>>tournament today, and it seemed to be spotting attacks there pretty fast.
>>
>>There are some obvious things it doesn't understand, that I think I can make it
>>understand, like for instance it doesn't have any particular fear of playing ...
>>g6 and trading off its dark-square bishop. But I think te basic idea of
>>identifying real attackers, and creating a compounded bonus based upon several
>>of these attackers, is pretty sound.
>>
>>How are you getting three pawns of comp in this position? What are the elements
>>of this compensation, according to Tiger?
>
>
>
>I cannot tell you what I do exactly (you understand why, don't you?), but what I
>can tell is that I have studied the way 1700-1800 elo human chess players
>attack. I have plenty of games against earlier versions of Tiger, played on
>rather slow hardware (which is interesting because Tiger did not outsearch his
>opponents too badly), where the human player completely destroys my program in a
>king attack.
>
>From these I have extracted some general knowledge (some common themes) and
>implemented them in my program. It's not very well tuned at this time, but when
>you put this "biologic" knowledge on top of a "mechanical" deep search, the
>result is surprising.
I can understand this.
bruce
>
>You see more wild (maybe incorrect) attacks in games of average chess club
>players, that's why I have found them more interesting to study than GM games.
>
>Next step is to find the weaknesses in the current knowledge, and add knowledge
>extracted from stronger human players (GMs).
>
>
>
> Christophe
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.