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

See The Solution Submitted by FrankM    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Fond wishes.. | Comment 6 of 9 |
(In reply to re: Explanation to Dej Mar - No, there's a false assumption by Dej Mar)

I apparantly misread the problem text.  I see now the players mutually play the X's and O's, only their bids determine somewhat where the X's and O's are placed.

I always strive for non-ambiguity, accuracy and completeness; but I know I often fall short. I know it's not just me, but the nature of the problems I want to convey.

As to the term "cat".  In regular Tic-Tac-Toe, when, after the grid is completely filled, there are no three X's or three O's in a row, the game is considered the cat's game.  This term might not be widely used, but it was used in the neighborhoods where I grew up and references to the term can be found on the web.


Thanks, DM, I learnt something new today.

Living as an expatriate and dealing internationally has brought me to remove local features of language. (Another reason is that wide spread prejudice taught me early on the usefulness of hiding my background). As a result my own language can be colourless. I'm glad to be exposed today to a new meaning of cat. (wonder where it comes from..)


Now that I understand this game, I hope to see if I can come up with a solution to all three parts.

It's not an easy problem, but still I wouldn't want to bet against you. I wish you good luck and lots of enjoyment with it!


  Posted by FrankM on 2008-04-27 14:26:20
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 (14)
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