Null Move in Quiescent search

[lauriet]

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

[bob]

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]

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]

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).

[mvk]

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.

[bob]

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]

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.

[bob]

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]

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.

[bob]

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...