Slow Searchers?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michael Neish
Posts: 68
Joined: Wed Apr 05, 2006 7:22 am

Re: Slow Searchers?

Post by Michael Neish » Sat Nov 02, 2013 3:40 pm

jdart wrote:It is probably worth a try.

I also forgot to mention Steven Edwards' program Symbolic (http://chessprogramming.wikispaces.com/Symbolic). I do not know much about the internals (it is not open source) but it appears to have a search significantly different from other programs and (as I understand it) also more knowledge-based. It is a reasonably strong engine.

--Jon
Thanks. Pity it isn't open source. I remember one or two engines of this kind 10+ years ago that were open source, but sadly they seem to have perished or else changed name and evolved into altogether different beasts ...

flok

Re: Slow Searchers?

Post by flok » Sat Nov 02, 2013 8:46 pm

Uri Blass wrote:I do not think that you can describe pos as a knowledge based program.

pos is an extremely weak program and every serious chess program has more knowledge than pos.
...
It seems that pos does not use search and does not use a serious evaluation.
It does not search, yes, but what makes an evaluation serious...?
It has 71 algorithms that were determined by statistical analysis of chess games.

Michael Neish
Posts: 68
Joined: Wed Apr 05, 2006 7:22 am

Re: Slow Searchers?

Post by Michael Neish » Sun Nov 03, 2013 12:10 am

Okay, let's say that in Eval(), the side to move happens to be suffering a knight fork of queen and rook, and will certainly lose one of them on the very next move.

If other aspects of the position are favourable, Eval() may return a good score for the position, and if this happens to be at the first Quiesce() node, the score may even fail high at this point.

A more complex (slower) Eval() may be able to detect the fork and either adjust the score downwards or else return a flag to Quiesce() making it continue the search to try to resolve the tactics.

This is an example of what I was referring to in my first post. There are of course many tactical possibilities, most of which are more subtle than this, and one surely cannot detect all of them statically without bogging down the search terribly. But maybe there's a middle ground somewhere or some other way to deal with it that perhaps someone has already explored.

gladius
Posts: 538
Joined: Tue Dec 12, 2006 9:10 am

Re: Slow Searchers?

Post by gladius » Sun Nov 03, 2013 5:36 am

I think all modern strong evaluations understand forks and piece threats. Most probably understand pins as well. They will even search for known mating patters in the eval.

Modern evals are fast yes, but also very knowledgable. The search is also guided by the eval. Moves that look good to the eval at low depth get a lot of preference, and are used to guide deeper searches.

Yes, there is a lot of statistical pruning, but one of the strongest parts of modern chess programs is that as depth goes up, pruning goes down. So, eventually, the program will search the move, even if at low depth.

Uri Blass
Posts: 8765
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Slow Searchers?

Post by Uri Blass » Sun Nov 03, 2013 8:35 am

flok wrote:
Uri Blass wrote:I do not think that you can describe pos as a knowledge based program.

pos is an extremely weak program and every serious chess program has more knowledge than pos.
...
It seems that pos does not use search and does not use a serious evaluation.
It does not search, yes, but what makes an evaluation serious...?
It has 71 algorithms that were determined by statistical analysis of chess games.
These algorithms are very poor in this case and I can see also poor positional moves of POS.

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Slow Searchers?

Post by tpetzke » Sun Nov 03, 2013 9:37 am

Hi

I think there are a couple of current programs that have a rather heavy eval. Some statements from Don let me think that Komodo is one of them. I would count my own engine (although much weaker) also in that category.

It is just personal preference. I enjoy working at my eval more than working at the search.

The things that I experienced are

1. If you go beyond the basic stuff chess knowledge coding is tricky. The chess books are not written for programmers. Reading a chapter about the isolated queens pawn doesn't necessarily help you to capture that in code.

2. Most written chess knowledge and rules deal with reasonable positions that you might encounter at the board. The engine processes most of the times positions that you will never see at the board. Your eval must deal with those efficiently as well.

3. nps and search depths don't bother me anymore. If've seen iCE win against engines that searched 4 times as fast or 2-3 plies deeper and also see it losing against engines that were even slower. Those KPI are interesting when it comes to to comparing different similar versions of one engine to learn about the impact of a change. It is rather meaningless between different engines.
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

Michael Neish
Posts: 68
Joined: Wed Apr 05, 2006 7:22 am

Re: Slow Searchers?

Post by Michael Neish » Sun Nov 03, 2013 2:27 pm

Thanks. I didn't now that more recent programs have this kind of evaluation, but that's probably because it's been a few years since I last examined any source code.

I don't believe there is any of this in Toga or Crafty, but I stand to be corrected.

Cheers,

Mike.

PK
Posts: 861
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Slow Searchers?

Post by PK » Sun Nov 03, 2013 8:24 pm

it's possible that deep searchers need different kind of knowledge than shallow searchers. at low depths, the benefit of human-like heuristics is bigger. as search becomes deeper, it is forced to compare positions that are increasingly different from each other, so it might be necessary to remove some chunks of knowledge for the sake of eval consistency. yet knowledge about removing stuff, knowledge how a decent eval parameter should look like (i.e. that it should trigger often enough and differentiate positions meaningfully) is also knowledge. it only ceases to resemble how we humans play chess.

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Slow Searchers?

Post by tpetzke » Tue Nov 05, 2013 2:26 pm

I think that "deep" and "shallow" are relative terms here. Even if I consider my engine a knowledge based program, it still searches 20 plies deep in a mid game position and longer TC, its selective depth is even much bigger.

20 plies + extensions + QS change the board a lot.
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

PK
Posts: 861
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Slow Searchers?

Post by PK » Wed Nov 06, 2013 12:27 pm

Thomas, my point was not to denigrate search depths of modern "slow" programs. To prove they are awesome it is sufficient to compare them with good old Fruit 2.1 that once was near the top, and now is relatively easy to outsearch.

The thing is, human knowledge has been devised to help and guide our ways of searching - slow and relying on pattern recognition for pruning entire branches, and thus comparing far fewer positions.

For example, as a human player I may know a bunch of plans associated with fianchettoed bishop, especially that I played a lot of Pirc Defence in my school days. Pirc is tricky, sometimes it requires regrouping this bishop via f8, sometimes after playing g6 one needs to keep Bf8 on its starting square basically forever and then castle queenside (in 4.f3 or 4.Be3 lines). Needless to say, I have never succedeed in actually coding even a tiny part of this knowledge in a way that is meaningful for my engine.

However, I might claim some small successes with generalizations, for example not awarding fianchettoed bishop directly, but giving a bonus for a bishop that defends squares near own king. I don't know if it still counts as a "slow", "knowledgable" approach, but it seems better than trying to copy human knowledge on 1 to 1 basis.

Post Reply