In this paper a problem of optimal stopping of the discrete time Markov process by two decision makers in a competitive situation is considered. The zero-sum game approach is adopted. The gain function depends on the states chosen by both decision makers. The random assignment mechanism is used when both want to accept the realization of the Markov process at the same moment. The construction of the value function and the optimal strategies for the players are given. Examples related to the generalization of the best choice problem are solved.