Jump to content

Talk:Null-move heuristic

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Applicability to other games

[edit]

This technique can in principle be used in any competetive game, but as far as i know it is only useful in chess. Does anyone know another game where it works well? If so, this article should be reworded more generally and moved to the 'Game artificial intelligence' category Bouke 12:47, 23 February 2007 (UTC)[reply]


Null-move heuristic and zugzwang scenarios

[edit]

Better explaining why the null-move heuristic does something and why it is useful seems like it would be worth the time. I am not an expert on programming or this particular topic (though I have an education in game theory and know C++ from once upon a time majoring in CS), but as I understand it, from a practical perspective, what happens is:

1.) Before we look at our position, we assume that we pass our turn and look at what the best minimax score of the best sequence of moves is from a 'passed' position, with less depth, which is assigned a minimax score.

2. All moves with a worse immediate position score than doing nothing, are pruned. This saves a lot of time.

Now what concerns me about my understanding here is that, if this is correct, a problem with zugzwang could be that it prunes all possible moves because they fail the test for being better than passing the move, which can be fixed by simple coding identifying said situations as zugzwang... but does not lead to any disaster after the error correction. In other words, if it looked far enough ahead to see all positions pruned by the null-move heurstic, you could add code to identify that as zugzwang and do a standard search, right?

It could immediately identify that with all positions pruned the position was zugzwang by definition, and see that ahead. But apparently the flaw of this program is that it causes blindness to zugzwang, which suggests something is wrong about my understanding here. Would be happy to expand the article if I could find some clarification.

71.145.159.2 07:31, 13 July 2007 (UTC)[reply]

Old post, but I was curious and wanted to reply. Point 1 is correct. Point 2 however, depending on what you mean by "immediate position score", might be incorrect. In the most common notion of the null-move heuristic, the maximizer node-- which received a value for beta from it's parent node--searches the path that starts with the null move albeit with a reduced depth. If the search hits a few levels deep and clearly this the max value of the position is still higher than beta, it knows it can stop searching (ie. it can prune itself). The null-move heuristic is applied as a quick dirty check whether a node can prune itself, rather than as a way to filter possible next moves. As in, if it already knows that the minimizer had a better path elsewhere (a smaller beta) is the position so good for the maximizer that even if it gives up a move it still has a score higher than beta? So, with this definition, the scenario that you talk about--where all moves are pruned besides the null move--just can't happen. Pruning after a null move doesn't prune the siblings of the null move. It prunes the parent of the null move. Hope that adds more clarity than subtracts. Eremgumas (talk) 06:59, 13 August 2016 (UTC)[reply]

Unclear wording in "Implementation" section

[edit]

"This approach makes two assumptions. First, it assumes that the disadvantage of forfeiting one's turn is greater than the disadvantage of performing a shallower search."

The wording of this sentence seems misleading to me. The confusion stems from the word "disadvantage" being used once in reference to the player's disadvantaged position but then later being used to refer to the reduction in certainty as a result of the search. These are inherently two different quantities and thus cannot be compared directly. I suggest rewording it to something like "First, it assumes that when evaluating a position for the best move, the disadvantage to the player in the hypothetical forfeiting of their turn is large enough to offset the increased uncertainty from performing a shallower search." It is more wordy but it also more correct so therefore less confusing, at least to me. Thoughts?

Eremgumas (talk) 05:06, 13 August 2016 (UTC)[reply]