All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Tic-Tac-Toyola (Posted on 2008-04-26) Difficulty: 5 of 5

Tic-Tac-Toyola is a variation of Tic-Tac-Toe with money. Instead of naughts and crosses (0s and Xs for Americans) being placed at the whim of alternating players, players vie for placement control at each turn by bidding some amount in a currency from an account under their control. The high bid decides the placement, with that bid amount being deducted from the corresponding player's account. Bids are in continuous units, so we can neglect the possibility of tie bids as unlikely.

There are two players: C(rosser) and N(aughty). X is placed first, and player C is declared winner if 3 Xs appear in a row before 3 Os appear in a row. If neither player achieves three in a row, N is declared winner. Thus, a game of Tic-Tac-Toyola will always have a winner.

C and N have been playing for some time and have reached the position:


(1) Assuming players are following optimal strategies, show that the outcome is independent of whether bidding is conducted secretly (by sealed bids) or openly (with players offered at each turn the possibility to outbid their opponent).

(2) Show that a player who is following an optimal strategy would not change his bid if he were to learn his opponent's account balance.

(3) Show that N can force a win if and only if he has in excess of twice as much money as C.

Note: Anyone interested in learning more about the Tic-Tac-Toyola family of games is invited to visit http://www.diplom.org/Zine/S2007R/Mayer/tictactoyola.htm

  Submitted by FrankM    
Rating: 4.0000 (2 votes)
Solution: (Hide)

Here is the game tree from this position.

C bids with the objective of driving the game down the left branch and N bids to drive the game down the right branch. Childless nodes represent wins. Let's try to compute the "cut off ratio" bn, for which C can force a win iff his account balance at node n exceeds Ns balance by more than a factor of bn.

Suppose the account balances at node n are L for N and L * bn for C. C bids an amount DC to move to node 2n, where DC is chosen so that the ratio of Cs to Ns account balances at node 2n, i.e., L * bn - DC divided by L, would equal b2n. N bids to drive the game toward node 2n+1 and is likewise ready to bid up to an amount DN, chosen so that the ratio of Crosser to Naughty account balances at node 2n+1, i.e., L * bn divided by L - DN, would equal to b2n+1. Since we are examining a cut-off condition, the two bids (D values) must be equal. Combining these results gives a the formula relating bn to the COR values at the daughter nodes:

bn = (1 + b2n) * b2n+1 / (1 + b2n+1)

Now, what are the COR values at the lowest rung? Since C would be ready to run down his account balance to zero in order to reach a childless node branching left, we can assign a COR value of 0 to these nodes. Likewise, N's willingness to empty his account to reach a childless node branching right means that we should assign these nodes a COR value of infinity. Applying the formula above lets us propogate up the tree:

b29 = b27 = b15 = ∞ ;   b28 = b26 = b12 = b2 = 0

b14 = b13 = 1;   b7 = 2 ;   b6 = 1/2;   b3 = 1;   b1 = 1/2

From the previously cited equation, we see that at turn n, C should bid a fraction DC/Lbn = 1 - bn/b2n of his account, while N should bid a fraction DN/L = 1 - bn/b2n+1 of his account. We can therefore compute the optimal spending fractions fnC and fnN:

f6N = f7C = f3C = f3N = f1N = 1/2 ;   fN and fC at all other parent nodes = 1

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Hints/TipsRuminations & hint (SPOILER warning!)FrankM2008-04-27 17:40:31
Partial Solution (comment)FrankM2008-04-27 17:28:13
SolutionPartial SolutionDej Mar2008-04-27 14:46:54
Some ThoughtsFond wishes..FrankM2008-04-27 14:26:20
re: Explanation to Dej Mar - No, there's a false assumptionDej Mar2008-04-27 08:40:42
Hints/TipsExplanation to Dej Mar - No, there's a false assumptionFrankM2008-04-27 07:22:14
Some ThoughtsResponse to Gamer (a start)FrankM2008-04-27 06:57:57
Some Thoughts(3) -- [spoiler]Dej Mar2008-04-27 01:18:55
Some Thoughts3 in a row (a start)Gamer2008-04-26 23:40:34
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information