13
$\begingroup$

In regular tic tac toe, both the players get alternate chances. This is a variant of that.

Player $A$ has $\$x$ amount and player $B$ has $\$y$ amount as initial balance. Assume that $y>x$.

Both the players bid some amount from the available amount to them. whichever bids higher will get the turn to put a mark on the board and the winner for that bid has to subtract the bidding amount from his/her available balance.

Player $A$ does not know the bidding amount of player $B$ and vice versa but a referee is there who will announce the remaining balance amount of each player after each move. Both the players know initial amount of each other.

Bidding can be done in fractions also.

For example:

Player $A$ is having $\$100$ and player $B$ is having $\$300.99$.

Player $A$ bids $\$40$ and player $B$ bids $\$100.33$. Player $B$ wins and puts a mark on the board. Player $A$ is left with $\$100$ and player $B$ is left with $\$200.66$ after this move.

Both the players are playing the same bidding amount in next two rounds and ultimately player $B$ wins.

The question: It is clear that if Player $B$ has $y>3x$ amount then he/she can surely win. What is the minimum amount of player $B$ (minimum $y$) such that he/she can develop a strategy where he/she always wins. Can we model this problem to any knows techniques of optimization?

I have tried the problem and pulled down the ratio of $y:x$ from $3 + \epsilon:1$ to $\frac{33}{28} + \epsilon :1$.

I don't know under which tag should I ask this questions so I am putting multiple tags.

Edit: If both the players tie in bidding then they re-bid until they come up with different bidding amounts. Ans since bidding amount is a real number, it is unlikely that will bid same amount in consecutive moves.

$\endgroup$
  • $\begingroup$ What happens if they tie in bidding? $\endgroup$ – ryagami Jan 6 '15 at 18:34
  • $\begingroup$ Yes, I forgot to mention that then they re-bid the amount. And since bidding is a real number, it is very unlikely that they will bid the same amount in consecutive moves. $\endgroup$ – Nimit Jan 6 '15 at 18:38
  • $\begingroup$ This question can hardly be answered without computational aid. For example, it may be an advantage for $B$ to allow $A$ to win the right to do the first move if that makes $A$ poor enough for the rest of the game ... The plan to solve this would be to check all $\approx 3^9/16$ situations and recursively calculate the break-even ratio. $\endgroup$ – Hagen von Eitzen Jan 11 '15 at 13:02
  • 3
    $\begingroup$ The Google knows several sources for "Bidding Tic-Tac-Toe", and bidding versions of combinatorial games in general. One reference is Develin and Payne, "Discrete bidding games" (2010), www.combinatorics.org/Volume_17/PDF/v17i1r85.pdf#sthash.tNk7JnoI.dpuf $\ $ which gives a game tree for bidding Tic-Tac-Toe on page 24 and credits T.Hwa with making the same computation independently in 2006. $$ $$ BTW Develin-Payne is also the only published math paper I've seen that contains the word "mindf**k" (see p.6; unfortunately some of the chess notation needs to be corrected, e.g. switch f3 and f6). $\endgroup$ – Noam D. Elkies Jan 11 '15 at 17:27
  • 2
    $\begingroup$ "Ans since bidding amount is a real number, it is unlikely that will bid same amount in consecutive moves." I don't get it. Are you assuming the players are bidding randomly? How can you assume that? Suppose there are two X's and two O's on the board, and whoever moves next will win. Obviously both players will bid all they've got. If they have equal amounts of money the tie will never be broken. $\endgroup$ – bof Jan 16 '15 at 3:54
7
+50
$\begingroup$

The paper by Develin and Payne referenced in the comments gives a very thorough treatment of this type of game, and in particular addresses the complicated nuances of breaking ties that arise during the bidding. However, in the Richman games they treat, the winning bid is given to the other player... this problem is slightly different. Glossing over the nuances of tied bids, we can see the following. (Assume that $B$ has one unit to bid with, and that both players will bid and play optimally.)

  • Every game state $G$ has a critical ratio $x(G)$ such that player $A$ can win if he has more than $x(G)$ to bid, and cannot win if he has less than $x(G)$ to bid.
  • A game state that is already won by player $A$ has $x(G)=0$; a game state already drawn or lost by player $A$ has $x(G)=\infty$.
  • Player $A$ can win with $x$ to bid when he has a winning bid, i.e., an amount $0 \le y \le x$ such that player $B$ loses if he bids more than $y$ (because $x(G_B) \le x/(1-y)$ for any state $G_B$ that player $B$ can move to; this applies only for $y<1$), and also loses if he bids less than $y$ (because $x(G_A) \le x - y$ for some state $G_A$ that player $A$ can move to).

We see two constraints on a winning bid for player $A$. First, $y \le x - x(G_A)$ for some state $G_A$ that player $A$ can move to; i.e., $y \le x - \min_{G_A} x(G_A)$. Second, either $y \ge 1$ (so player $B$ can't outbid it), or else $y\ge 1 - x / x(G_B)$ for all states $G_B$ that player $B$ can move to; i.e., $y \ge 1 - x / \max_{G_B} x(G_B)$. The latter constraint is never stronger than the former, so we have: $$ 1-x/\max_{G_B}x(G_B) \le y \le x-\min_{G_A}x(G_A). $$ This interval of winning bids shrinks as $x$ decreases, and vanishes (by definition) when $x=x(G)$. So setting the two endpoints equal to one another lets us solve for $x(G)$: $$ 1-x(G)/\max_{G_B}x(G_B) = x(G)-\min_{G_A}x(G_A) \implies x(G)=\frac{1+\min_{G_A}x(G_A)}{1+1/\max_{G_B}x(G_B)}. $$

At this point we can calculate. I'm pasting Python code to evaluate this recursion below. The result that I get for Tic-Tac-Toe is $x(G_0)\approx 1.018375$. I have modified the code to give an exact (rational) result (code not shown here, as it's not worth the extra space): it is $$x(G_0)=\frac{396925}{389763}=1+\frac{7162}{389763}.$$


g0 = '---|---|---'
NO = '-'
DRAW = 'x'

def legalMoves(g, player):
  ret = []
  for i in xrange(0, len(g)):
    if g[i]==NO: ret.append(g[:i] + player + g[(i+1):])
  return ret

def winner(g):
  for i in xrange(3):
    if g[i]==g[i+4] and g[i+4]==g[i+8] and g[i]!=NO: return g[i]
    if g[4*i]==g[4*i+1] and g[4*i+1]==g[4*i+2] and g[4*i]!=NO: return g[4*i]
  if g[0]==g[5] and g[5]==g[10] and g[0]!=NO: return g[0]
  if g[2]==g[5] and g[5]==g[8] and g[2]!=NO: return g[2]
  if NO in g: return NO
  return DRAW

def value(g, infty=10**12, cache={}):
  if cache.has_key(g): return cache[g]
  w = winner(g)
  if w == NO:
    amin = min(map(lambda(gg):value(gg, infty, cache), legalMoves(g, 'A')))
    bmax = max(map(lambda(gg):value(gg, infty, cache), legalMoves(g, 'B')))
    val = (1.0 + amin) / (1.0 + 1.0 / bmax)
  elif w=='A': val = 0
  else: val = infty
  cache[g] = val
  return val
$\endgroup$
  • $\begingroup$ Very interesting. Does this tell you what the opening bids would be? $\endgroup$ – Joffan Jan 17 '15 at 10:50
  • 2
    $\begingroup$ @Joffan: Yes, you can determine that too. Suppose player $A$ has more than the critical amount to bid (and player $B$ has one unit). Player $A$ can bid $0.293926480109$, leaving him with a mark in the center and more than $0.724448788965$ (the critical ratio for the A-in-the-center game) if he wins the bid; if he loses, then player $B$ takes the center mark (his best move), and less than $0.706073519891$ left to bid, so the ratio $A:B$ is more than $1.4423076923083187$ (the critical ratio for the B-in-center game). $\endgroup$ – mjqxxxx Jan 17 '15 at 18:48

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.