2
$\begingroup$

Assume there are two players A and B who play a game on a finite game board (you can imagine it is some chess game or the position game. The key point is the total number of feasible sequences of choices can be large but finite and bounded.)

The rule is that in each turn, Player A make his choice first, then Player B makes his choice. All the information a player knows when he makes his choice in a turn is all the choices already made by both Players in the history of the game.

Now, if Player A has a randomized strategy to win with probability at least 1/2, no matter what strategy Player B applies. Does it imply that there is a deterministic strategy of Player A to win for sure?

If not, how high the probability (greater than 1/2 and can be close to 1 and may related to the total feasible choices) should be to imply this wining for sure strategy?

(A deterministic strategy can be viewed as a sequence of functions depending only on the information in the history.)

$\endgroup$
2
$\begingroup$

In a finite game with perfect information and no random elements, there are only three possibilities. The game, if perfectly played, is a win for the first player, a draw, or a win for the second player. This can be seen by considering the game tree. All the leaves can be labeled as win, loss or draw (from the perspective of the first player, say) then the minimax and maximin can be used to label the nodes immediately above the leaves, and so on. Eventually, the root of the tree (the initial position in the game) is labeled win loss or draw, which is the outcome if both players play as well as possible.

If some strategy give A a positive probability of winning, then the game cannot be a loss for the first player, because B has a strategy that will win no matter what A does. Similarly, the game cannot be a draw, because B has a strategy that forces at least a draw, no matter what A does. Therefore, there is a deterministic strategy by which A can force a win.

So yes, the game is a win for the first player, and there is a deterministic strategy that accomplishes it.

EDIT

This is in response to the OP's comments.

You say that the game is like chess. Chess has no random elements, but a player may elect to play a randomized strategy. Every now and then, he rolls some dice to decide which of several moves to make. This is what your question describes, or so it seems to me.

An example of a game that does contain random elements is backgammon. The moves available to a player at any point are determined by chance. An accomplished backgammon player will still use a deterministic strategy, at least in theory. Every time he is confronted with the same situation (the pieces on the same points, the same dice roll) he will make the same move.

Of course, once the player adopts a randomized strategy, it makes perfect sense to speak of the probability of a win. Consider a game that has been fully analyzed, for instance nim. This is a hard game to play if you don't know the analysis, so you may move at random in some fashion. Now we could discuss the probability that you win, assuming your opponent knows the analysis. In the ordinary version of nim with piles of $3$,, $5$, and $7$ the game is a win for the first player, and he will lose the first time he makes a mistake. If he just chooses a move uniformly at random from all the legal moves available, we can compute the probability that he wins, which will be substantially smaller that $\frac12.$

$\endgroup$
  • 1
    $\begingroup$ What do you mean a perfectly played game? $\endgroup$ – Connor Aug 22 at 2:02
  • $\begingroup$ As the randomized strategy for Player A only wins with probability at least 1/2, is it possible for Player B to have a strategy to win with probability 1/2 (or even smaller, say 1/4)? $\endgroup$ – Connor Aug 22 at 2:07
  • 1
    $\begingroup$ You are talking about a game like chess with perfect information and no random elements right? The game has a definite outcome if neither side makes a mistake. Probability has really nothing to do with this. $\endgroup$ – saulspatz Aug 22 at 2:24
  • $\begingroup$ Yes, you can assume perfect information, but it does contain random elements that come from the Players' strategy (otherwise it makes no sense to say what is probability 1/2 for a player to win). $\endgroup$ – Connor Aug 22 at 2:56
  • $\begingroup$ Yes, the randomness comes from the players’ randomized strategies. You mention some well-studied games. But if the game is very complicated, at a first try, we could only design a randomized strategy for Player A to win with probability at least 1/2 (or even worse, some smaller constant). Does it imply there exists a deterministic strategy for Player A to win for sure? $\endgroup$ – Connor Aug 22 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.