Horizon Effect

[CRoberson]

If you don't understand the full extent of the horizon effect,
watch the movie "Next" with Nicholas Cage.

Quite entertaining how they demonstrate the horizon issues.

The writers either understood the issues or were lucky.

[Ovyron]

Another fact that I find interesting:

Nicholas is able to see all possible outcomes of events for the next two minutes, does that mean that it's possible for him to beat any other player at chess for a 2 minute game 100% of the time!? (Assuming the opponent doesn't play perfect chess.)

[hgm]

I guess not. Just that he knows he is going to lose...

[Ovyron]

I guess not. Just that he knows he is going to lose...

But he was able to dodge bullets by making all possible bullet dodging tries in his mind, and then picking the one that evaded the bullet, so you couldn't kill him (Unless you were shotting for more than 2 minutes nonstop, some combination of bullets that killed him after he dodged the first bullets and he was victim of the horizon effect.)

So, beating Kasparov at chess would be possible by finding the winning combination of moves before playing them, until the end of the game. You don't need to search the whole tree, as you stop when you find one that works (It works as long as the whole game lasts less than 2 minutes.)

[hgm]

It depends on his nps. If he is no good chess player, almost every sequence of moves he mentally tries, even with perfect preview of the opponent's reply, will see him checkmated. So he will discard that sequence of moves, and backtrack, to find if he can find a better one. So he will still have to search the tree spanned by his own alternatives. And he will not be able to search enough of that tree to find a branch where he is not checkmated, in two minutes. He will still be thinking about his first move to make when the two minutes are already over!

How big the tree is will depend on how many ply it will take on the average between making a bad move that will have to be retracted to not lose, and recognizing that the game is lost.

This in generally (size of the typical no-exit subtree upto the nodes that you can recognize as dead ends) determines the difficulty of a puzzle. Dodging bullets is not nearly such a complicated puzzle (in terms of depth and branching ratio) as playing Chess.

[Ovyron]

He will still be thinking about his first move to make when the two minutes are already over!

Don't forget that he can start calculating 2 minutes before the game starts

But, anyway, it seems you are right, perhaps 2 minutes is very few time, and Nicholas needs to be a very good chess player already for something like this to work (So, being able to know all the possible move replies from your opponent is not enough to ensure a win.)

[CRoberson]

Yes!

The total game time would have to be <= 2 minutes.
So, each side gets 1 minute on the clock.
Because he can see all events and permutations to all
events in a two minute window, he would be unbeatable.

Now, the question is: "Can a two minute perfect search of
events yet to happen for two minutes produce a guaranteed
non-loss in a game lasting longer than 2 minutes?"

They answered that quite well in the movie.

[Michael Sherwin]

It depends on his nps. If he is no good chess player, almost every sequence of moves he mentally tries, even with perfect preview of the opponent's reply, will see him checkmated. So he will discard that sequence of moves, and backtrack, to find if he can find a better one. So he will still have to search the tree spanned by his own alternatives. And he will not be able to search enough of that tree to find a branch where he is not checkmated, in two minutes. He will still be thinking about his first move to make when the two minutes are already over!

How big the tree is will depend on how many ply it will take on the average between making a bad move that will have to be retracted to not lose, and recognizing that the game is lost.

This in generally (size of the typical no-exit subtree upto the nodes that you can recognize as dead ends) determines the difficulty of a puzzle. Dodging bullets is not nearly such a complicated puzzle (in terms of depth and branching ratio) as playing Chess.

I have not seen the movie, but, it sounds as though his nodes per second is infinite and he just simply knows all possible outcomes in the next two minutes. His tree search would be way more efficient as well. He will just simply know the opponents reply to any move that he may make. And he can work backwards from a mate position since his search is not in real time.

[hgm]

This would not really put him in a much better position as a normal alpha-beta tree search...