Bidding Tic Tac Toe

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