3
$\begingroup$

I have some basic background in game theory, but still there are exist simple questions that I cannot answer for sure.

Whether Tic-Tac-Toe game has a dominant strategy? May be only one of the players has a dominant strategy? More interesting question , whether chess has a dominant strategy?

Regarding Tic-Tac-Tow, it is a game when the draw is always result playing with experienced player. Of course there is a game tree, but a "preferable" action is taken regarding the action of the opponent, there is no known beforehand a best dominant strategy, therefore I claim Tic-Tac-Toe doesn't have neither dominant not dominated strategy for any players.

As a chess exactly with the same reason there is no dominant strategy, because I don't beforehand which strategy is preferable over the others.

Is it correct?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by dominating strategy? $\endgroup$ – Michael Greinecker Jun 15 '13 at 18:17
  • $\begingroup$ @MichaelGreinecker, you are right, corrected. $\endgroup$ – com Jun 15 '13 at 18:36
  • $\begingroup$ we don't know if chess has a dominant strategy, the tree is finite but too big so that we didn't explored it entirely yet. and in your definition of a dominant strategy, you should take in account "how deep have I to explore the tree of the next possible moves to decide the optimal move", most humans have difficulties to explore more than 4-5 levels of the tree $\endgroup$ – reuns Jul 20 '15 at 9:22
1
$\begingroup$

Either one player can guarantee a win by a certain strategy or both players can guarantee a draw. That is what is often called Zermelo's theorem (historically not quite accurate). It applies to all zero-sum games of perfect information in which only a finite number of possible position of the game exists.

$\endgroup$
1
$\begingroup$

If your definition of strategy is one where players decide (at the start but covering the whole game) what their moves will be conditional on the moves their opponent actually makes, then there are certainly strategies which dominate others in Tic=Tac-Toe (or Noughts and Crosses).

The dominant strategies share the property that they guarantee at least a draw and if the opponent is not playing optimally may lead to a win.

There will also be dominant strategies in Chess, but the number of possibilities is so great that nobody has yet found an optimal strategy.

It might be worth reading Wikipedia's article on solved games

$\endgroup$
  • $\begingroup$ it means that there is no known beforehand dominant strategy? And any "preferable" strategy conditional on the opponent move is "dominant" in only this particular match, and according to the definition of dominant strategy I cannot call this "preferable" strategy as dominant strategy? Is it correct? $\endgroup$ – com Jun 16 '13 at 5:10
  • 1
    $\begingroup$ For Tic-Tac-Toe, there are a finite number of possible games and of possible positions. A known beforehand strategy would be one which sets out what move to make in every possible position: there are fewer than $10^{1316}$ strategies for the first player and fewer than $10^{1306}$ for the second player, many fewer if you take symmetry into account. Some of these strategies dominate some others. $\endgroup$ – Henry Jun 19 '13 at 22:03
0
$\begingroup$

I generally depends on one's concept of dominance but generally in it is traditional, from that (philosophically/logically prior,

or pre-expected value/probabilistic) dominance, called conditional logic dominance or qualitative logic dominance.

It is presumed that by act-state, independent, not that the probabilities of the states would have been the same, but that in the somewhat circular sense, but that very same state $S$still would have been occurred, had I, or were I to act otherwise.

That is mod-ally or counter-factually independent. if state $S1$ Horse A wins, occurs and I bet on horse $A$, $S1: Horse A wins, still would have occurred were to have instead bet on horse $B$

It also does not require that literally the very same state, in some sense would still have occurred. Suppose that there are counter-factual dependencies, just so long as the statement result that 'I will would have been better off, remains in-variant-ly true'.

Where in some cases, degrees of dominance can be described as a result of the super-set, subset structure.

not the merely same number or rather more cases/states,, but the very same, same identical/counter-factually identical, single case scenarios plus more cases, - as well as more more , etc.

For example,some distinct state $ S2$ instead of $ S1$may have occurred, had I committed act $ B$ instead of $A$ .

Nonetheless, even under that state $S2$, given act act $A$ I still would have been better off doing $A$ than $B$, just as much as I was better off under $S1$ (which would have occurred instead) for whatever reason.

when I commit $A$ rather than $B$committing A .

It might be that $A1$ is better in both states, or changes the nature of the state, or;

Ont-ically somehow, makes it to the case, for whatever reason, that $S1$ would have occurred, if I committed $A$; and $S2$ would have obtained, if I commit $B$. So that $A$ might be worse off under $S2$ but that is irrelevant for whatever reason, because its nomi-cally impossible given the set up.

For example, it might be that $S2$ would not have occurred, had I instead bet on $A$, rather $S1$ would have, as a matter of some strange law of nature, and '$A$ under $S1$' is better than '$B$ under $S2$', where $S2$ would necessarily occur if I bet on $B$. IF this is true, this is still a form of conditional logic dominance.

Which gives it, dominance or logic/conditional logic dominance (or proper dominance, as I call it) a logical flavor, or a priori flavour/pre-probabilistic or monotonic flavor ,' that quantitative dominance lacks.

dominance, logic dominance:

'where you know that the 'truth values' of the states, $S$ are fixed/counter-factually fixed (would have been the same come what may, not what else I may have done or hypothetical could have done). Or, 'I would have done better on that same single case and more' statements; super-set of the same situations) invariant fixed in truth value .

I presume that this above, is what you mean by dominance, rather than 'quantitative dominance'- ringing it closer to logical reasoning rather than probabilistic based reasoning, and hence its use in the foundation

m

quantitative dominance- which looks identical, to the above when used. Often texts are not explicit and sometimes I think that some people do not care about the distinction.

Quantitative dominance, likewise, does not explicitly using probabilities or expected values either , uses the notion of causal or modal independence in many cases, and is distinct from stochastic dominance or expected value dominance, expected value maximization, or generalized dominance as well. Or at least Purports to be. Yet, Quantitative dominance,is ultimately based on probabilistic and expected utility reasoning and is subservient to it , unlike qualitative or logic dominance.

That is, 'quantitative dominance', does so implicitly, as a means of a tool when you know the probabilities are equal, but does not know what they are. As this does not imply that the truth values of the S1, states, are invariant under the counterfactual distinct acts. One has to be careful.

As at the end of the day this form of 'dominance, if it even deserves the name' is really expected utility reasoning in disguise ; yet it goes by the same name (as a form of non-stochastic or non-expected value maximization -dominance reasoning). Which is sometimes, infelicitous.

And if working on the foundations of probability , it tacitly invokes the probabilistic concept, just as much as the explicitly probabilistic forms, which could render ones account, in some sense circular, depending on what it is one is doing). Unlike the logic or qualitative form.

'had I bet on Horse $A$ and horse $A$ wins, then had I bet on Horse $B$, Horse $ A $still would have won'.

And, is a form of conditional logic reasoning, based on inclusion and the subset super-set structure of the situation (monotonicity).

Generally based on a kind of 'come what may', counter-factual certainty, where often nature makes it moves first (if the issue of in-determinism threatens).

Otherwise, it becomes difficult to employ/justify the semi-factual (morgen-besser like indicative conditionals' it used .

If for example statements, are not counter-factually definite, due to in-determinism, unless the state was determined in-deterministic ally beforehand).

There is another form called super-duper dominance, which is usable even under in-determinism. But one is hardly ever in a position to use it.

Which works, where regardless of the state-in determinism, the worst outcome of among-st all states,for act $A$, is better than the best outcome of act $B$

so that among-st all states, so that it does not matter if a distinct state $S2$ were to have been picked out under a distinct decision $A$ despite that given $B1$ S1 occurs instead, if $A S2 > B S2$, , $AS2, > S1 B.

$A S1 > B S2$, , $AS1, > S1 B. as below :

this is strict super-duper-dominance).

If one changes, the matrix to:

$$\quad S1\,\, S1$$
$$A1: 10\,, 20 $$
$$ A2:\,\,, 0 \,,0 $$

If one changes, weak super-duper-dominance**

$$\S1\,\, S2$$
$$A1:\,, 10,\, 20 $$
$$ A2:\,, 0\,, 10 $$

.

for example under all states.

standard conditional logic /qualitative dominance might be instead $$\quad, S2\,, S1$$
$$A1:\,, 10 ,\,, 20$$
$$A2:\,, 0 ,\,, 13 $$

So long that, 'if $S1$ occurs, if I bet on $A1$, $S1$ it still would have occurred, had I bet on $B$, instead' remains valid statement in that situation.

Then this form, still qualiifes, as 'pre-probabilistic'/(that is non-circular) and not 'quantitative dominance', For example, where, nature made its move in the backward light cone of the decision, before the act od decision, picking out $S1$ beforehand the decision act, so that it for given a distinct act, $S1$ would still have occurred.

Where quantitative dominance, on them other hand' is really just 'stochastic dominance, or expected value reasoning/generalized or expected value, or greater utility, same chance, dominance' in disguise, despite looking like conditional logic dominance, in form.

That is,quantitative dominance invokes, a principal of indifference reasoning, presuming the PP, born rule in disguise, kind of reasoning etc, and should not be really used in the foundations of probability when justifying equi-probability relation themselves.

It is, if it is valid, then it is, considered irrelevant that $AS is 13> $B, S1: 10$, on objective or nomic grounds given the nature of the set up.

This is as, $A$ still strictly conditional logic dominates $A1$ as $S1$, and $S2$, are both ,logically and mod-ally mutually exclusive, in the modal and actual sense of the word. (mod-ally -mutually exclusive).

If, $S1$, occurs, under $A$ where I gain ten dollars, then as $S2$ was physically impossible,on that single case,(somehow) then $S1$ still would have obtained, had I (hypothetically) bet on $B$ instead.

As I would have gained $0$ dollar not 13$ as $S1$ was somehow fixed,then had I bet on $B$, $S1$ still would have would have obtained nonetheless. and I would have worse off necessarily.

So, in some, sense the agent is contradicting themselves, if they want to make the best of the actual single case scenario, whether this is weak or strong, in a fashion stronger than one is (if at all) when ones uses quantitative dominance or expected value dominance, stochastic dominance, or expected value reasoning, or generalized dominance.

$\endgroup$
0
$\begingroup$

No, that is not the reason tic-tac-toe or chess does not have a dominant strategy.

I am pretty sure in tic-tac-toe, there is always a way for the second player to insure a draw. The game probably has an infinite number of Subgame Perfect Nash equilibria (https://en.wikipedia.org/wiki/Subgame_perfect_equilibrium) because players can mix between strategies. The strategy space for player 1 would have 9x7x5x3x1=945 elements and the strategy space for placer 2 would have 8x6x4x2=384 elements. You could definitely write a program to figure out the SPNE. Someone mentioned Zermelo's theorem and said it doesn't always work?! Theorems are proven and always work. Zermelo's theorem does not apply to games that can have draws. As for chess, it has more complicated rules but there are tons of books and papers written on game theory approaches to chess. Just google it and you should find a lot of interesting results.

$\endgroup$

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.