Hey Bob,
There doesn't look like there is any null move code in Crafty's quiescent search.
Comments ?
Explanations ?
Insights ?
Testing ?
Null Move in Quiescent search
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Null Move in Quiescent search
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...lauriet wrote:Hey Bob,
There doesn't look like there is any null move code in Crafty's quiescent search.
Comments ?
Explanations ?
Insights ?
Testing ?
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.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Null Move in Quiescent search
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.
I don't know if any successful programs ever used that idea, but it's not mainstream.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Null Move in Quiescent search
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).
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.
Without ideas there is nothing to simplify.
-
- Posts: 589
- Joined: Tue Jun 04, 2013 10:15 pm
Re: Null Move in Quiescent search
I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.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).
[Account deleted]
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Null Move in Quiescent search
I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???mvk wrote:I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.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).
-
- Posts: 589
- Joined: Tue Jun 04, 2013 10:15 pm
Re: Null Move in Quiescent search
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.bob wrote:I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???mvk wrote:I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.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).
[Account deleted]
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Null Move in Quiescent search
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 wrote: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.bob wrote:I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???mvk wrote:I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.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).
-
- Posts: 589
- Joined: Tue Jun 04, 2013 10:15 pm
Re: Null Move in Quiescent search
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.bob wrote: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 wrote: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.bob wrote:I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???mvk wrote:I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.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).
[Account deleted]
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Null Move in Quiescent search
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.mvk wrote: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.bob wrote: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 wrote: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.bob wrote:I think Shannon knew there were issues. Why do you think he described type-A and type-B minimax searches???mvk wrote:I'm expecting someone to drop in and claim that Shannon understood this in the 1950s and kill the topic that way.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).
Meanwhile, what we have is working so much better than anyone thought possible...