Null Move in Quiescent search

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.
lauriet
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Null Move in Quiescent search

Post by lauriet » Wed Dec 09, 2015 1:59 am

Hey Bob,
There doesn't look like there is any null move code in Crafty's quiescent search.
Comments ?
Explanations ?
Insights ?
Testing ?

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null Move in Quiescent search

Post by bob » Wed Dec 09, 2015 3:28 am

lauriet wrote:Hey Bob,
There doesn't look like there is any null move code in Crafty's quiescent search.
Comments ?
Explanations ?
Insights ?
Testing ?
Not sure how you would use it. Null-move is a reduced depth search, where the quiescence search is already depth=0 so there's nothing to reduce...

I suppose you could consider the "stand pat" option as a null-move since you just instantly back up the evaluation if it is good for you... No moves (captures/checks) made at all.

AlvaroBegue
Posts: 919
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Null Move in Quiescent search

Post by AlvaroBegue » Wed Dec 09, 2015 4:03 am

Don Beal's thesis has an idea of null move in the quiescent search (section 10.6): https://project.dke.maastrichtuniversit ... thesis.pdf

I don't know if any successful programs ever used that idea, but it's not mainstream.

Michel
Posts: 2040
Joined: Sun Sep 28, 2008 11:50 pm

Re: Null Move in Quiescent search

Post by Michel » Wed Dec 09, 2015 8:42 am

It's interesting to read the first chapter of that thesis. It confirms Nau's observation that minimax search is often pathological. The deeper you search the worse you play, even with a good static evaluation.

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Null Move in Quiescent search

Post by mvk » Wed Dec 09, 2015 10:27 am

Michel wrote:It's interesting to read the first chapter of that thesis. It confirms Nau's observation that minimax search is often pathological. The deeper you search the worse you play, even with a good static evaluation.

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).
I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.
[Account deleted]

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null Move in Quiescent search

Post by bob » Wed Dec 09, 2015 2:36 pm

mvk wrote:
Michel wrote:It's interesting to read the first chapter of that thesis. It confirms Nau's observation that minimax search is often pathological. The deeper you search the worse you play, even with a good static evaluation.

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).
I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.
I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Null Move in Quiescent search

Post by mvk » Wed Dec 09, 2015 4:45 pm

bob wrote:
mvk wrote:
Michel wrote:It's interesting to read the first chapter of that thesis. It confirms Nau's observation that minimax search is often pathological. The deeper you search the worse you play, even with a good static evaluation.

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).
I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.
I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???
I think he was just postulating how a heuristic search might produce human level moves. But he had no theory and no empirical evidence. He had some idea of the relation between critical move sequence length, end point evaluation and resulting skill. A correlation that Thomson would later find to be both very strong and very steep in chess. So strong that it came to dominate the field, pushed it into an engineering challenge and out of the interest of AI research. He had likely no idea of the minimax pathologies that would be uncovered in other games. Evidence of the latter is that Type A and Type B don't differentiate on the back-propagation mechanism but on the tree shaping.
[Account deleted]

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null Move in Quiescent search

Post by bob » Wed Dec 09, 2015 5:08 pm

mvk wrote:
bob wrote:
mvk wrote:
Michel wrote:It's interesting to read the first chapter of that thesis. It confirms Nau's observation that minimax search is often pathological. The deeper you search the worse you play, even with a good static evaluation.

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).
I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.
I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???
I think he was just postulating how a heuristic search might produce human level moves. But he had no theory and no empirical evidence. He had some idea of the relation between critical move sequence length, end point evaluation and resulting skill. A correlation that Thomson would later find to be both very strong and very steep in chess. So strong that it came to dominate the field, pushed it into an engineering challenge and out of the interest of AI research. He had likely no idea of the minimax pathologies that would be uncovered in other games. Evidence of the latter is that Type A and Type B don't differentiate on the back-propagation mechanism but on the tree shaping.
I am not sure why they would/should differ there. Only in making the decision "is this deep enough for this branch?" assuming a zero-sum game of course.

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Null Move in Quiescent search

Post by mvk » Wed Dec 09, 2015 6:07 pm

bob wrote:
mvk wrote:
bob wrote:
mvk wrote:
Michel wrote:It's interesting to read the first chapter of that thesis. It confirms Nau's observation that minimax search is often pathological. The deeper you search the worse you play, even with a good static evaluation.

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).
I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.
I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???
I think he was just postulating how a heuristic search might produce human level moves. But he had no theory and no empirical evidence. He had some idea of the relation between critical move sequence length, end point evaluation and resulting skill. A correlation that Thomson would later find to be both very strong and very steep in chess. So strong that it came to dominate the field, pushed it into an engineering challenge and out of the interest of AI research. He had likely no idea of the minimax pathologies that would be uncovered in other games. Evidence of the latter is that Type A and Type B don't differentiate on the back-propagation mechanism but on the tree shaping.
I am not sure why they would/should differ there. Only in making the decision "is this deep enough for this branch?" assuming a zero-sum game of course.
Exactly! So what are alternatives to transcend Shannon? PDS is promising for certain positions, especially deep tactical ones. It is neither type A nor B, because it has no minimax. (But it has other issues.). Other ideas? The top chess engines of today have morphed into an application of minimax that appears now more monte-carlo like than about establishing a credible PV, judging from their PV tail contents. Maybe they have unknowingly already unearthed something new about back propagation that exceeds type A/B as well. With a theory we wouldn't need decades to stumble into such things which we then still don't understand. At least, I believe that is the point Michel tries to make whenever he kindly reminds us that we are lacking a theoretical foundation for what we are doing.
[Account deleted]

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null Move in Quiescent search

Post by bob » Wed Dec 09, 2015 7:38 pm

mvk wrote:
bob wrote:
mvk wrote:
bob wrote:
mvk wrote:
Michel wrote:It's interesting to read the first chapter of that thesis. It confirms Nau's observation that minimax search is often pathological. The deeper you search the worse you play, even with a good static evaluation.

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).
I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.
I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???
I think he was just postulating how a heuristic search might produce human level moves. But he had no theory and no empirical evidence. He had some idea of the relation between critical move sequence length, end point evaluation and resulting skill. A correlation that Thomson would later find to be both very strong and very steep in chess. So strong that it came to dominate the field, pushed it into an engineering challenge and out of the interest of AI research. He had likely no idea of the minimax pathologies that would be uncovered in other games. Evidence of the latter is that Type A and Type B don't differentiate on the back-propagation mechanism but on the tree shaping.
I am not sure why they would/should differ there. Only in making the decision "is this deep enough for this branch?" assuming a zero-sum game of course.
Exactly! So what are alternatives to transcend Shannon? PDS is promising for certain positions, especially deep tactical ones. It is neither type A nor B, because it has no minimax. (But it has other issues.). Other ideas? The top chess engines of today have morphed into an application of minimax that appears now more monte-carlo like than about establishing a credible PV, judging from their PV tail contents. Maybe they have unknowingly already unearthed something new about back propagation that exceeds type A/B as well. With a theory we wouldn't need decades to stumble into such things which we then still don't understand. At least, I believe that is the point Michel tries to make whenever he kindly reminds us that we are lacking a theoretical foundation for what we are doing.
Not sure about the relevance of a comment about lacking theoretical foundation. One could refer to Knuth for a bit of theoretical foundation on minimax and alpha/beta. Whether other search techniques exist or not is another issue for discussion. So far, no. But possibly in the future.

Meanwhile, what we have is working so much better than anyone thought possible...

Post Reply