< Earlier Kibitzing · PAGE 291 OF 291 ·
Later Kibitzing> 
May2417
  perfidious: <WannaBe: Computer defeats human in game 1 in 5 game match of Go....> Rut roh. 

May2517
  WannaBe: I made a mistake in my previous post, it was the best of 3 games, not 5. And computer have clinched it. http://money.cnn.com/2017/05/25/tec... Time to run for the hills, Skynet's right around the corner... Where are you Sarah Connor? We are doomed, doooooooooooom'd!! 

Jun1517
  WannaBe: Well, that is great, but can it speak Jive like Barbara Billingsley? https://www.theatlantic.com/technol... 

Jun1517
  Sneaky: I've been thinking about a kind of abstract twoplayer symmetrical game of the simplest type. Forgive me if this is dreadfully dullI honestly am trying to figure out whether or not it's so trivial of a game that it can be dismissed ... or perhaps it's one of those games like rockscissorspaper which are effectively random but can employ psychology if somehow you can "get in your opponent's head." If there is some interest to it, I imagine it could be the core mechanic behind a more elaborate table or computer game. <SETUP> There are 6 jars, 3 for each player. They are labeled "A, B, C" for each player. The jars are opaque: one player has black jars, the other player has white jars. Each player also receives 10 marbles; the white player's marbles are white; the black player's marbles are black. Each player puts a $20 bill in each jar, and an extra $5 in jar C. (This is why I call jar C the "premium jar" ... it's a better to win that one than any other.) <PLAY> In secret, each player puts any number of their marbles in each of the three jars. You are allowed to put no marbles in a jar, all your marbles in a jar, any distribution you can think of. For example, one player might try in 3 in A, 3 in B, and 4 in C. <OUTCOME> The jars containing cash and marbles are now opened up and the marbles counted. For each pair of jars (A, B, and C) the player who had the most marbles in their jar takes all of the money from both jars. <EXAMPLES> I decide to forgo the $25 prize and make my distribution (5,5,0). My opponent tries the (3,3,4) distribution described above. Ergo, I win $40 from the first two jars, lost $25 from C, and profit $15. Suppose we play again. I stick with my original plan with (5,5,0). My opponent, now wise to my tricks, plays (3,6,1). The jars are compared and he has won both jars B and C, winning $45. For round three I try to make a play for the premium jar C: I play (5,0,5). My opponent sticks to his (3,6,1) strategy. Now I win jars A and C for $45. <ANALYSIS> I imagine a computer program that selects the distribution entirely at random. I am confident that if I played (3,3,4) against it every time, I would come out ahead, simply because my setup is "smarter" in that it makes a stronger play for the premium jar. Therefore there must some strategies better than pure random picks, which means there must be a best strategy. But what is it? 

Jun1517
  WannaBe: So, if two jars have the same amount of marble(s), it would be a push and no money exchange hands(?) I think a computer program, that brute force all the possibilities will be the way to go. W's strategy (0,0,10) and you compare that to B's strategy (0,1,9); (0,2,8); (0,3,7);.....(10,0,0) Then you move on to the next possible W's marble distribution (0,1,9), etc... 

Jun1517
  Sneaky: <So, if two jars have the same amount of marble(s), it would be a push and no money exchange hands(?)> Exactly. Draws are possible for either a pair of jars or even all three. 

Jun1817
  al wazir: <Sneaky>:
1. Clearly any useful strategy would have to involve some randomness, since a nonrandom strategy is predictable and hence beatable. 2. Suppose there is an optimal strategy, a strategy that guarantees that its adherent always wins over an extended series of plays. 3. If both black and white play the *same* optimal strategy, neither would come out ahead. 4. This contradicts assumption 2.
5. Therefore there is no winning strategy.
6. The best that can be achieved is a strategy which ensures that its adherent doesn't lose. 7. It is not obvious that such a strategy exists. I can imagine that there are three strategies: call them X, Y, and Z. X always beats Y, Y always beats Z, and Z always beats X, and X, Y, and Z win against all other strategies. 8. Over an extended series of plays it would become apparent which strategy one's opponent is playing. Thus, if my opponent's strategy is X, I would play Z, and then I would come out ahead. 9. Unless he changed to Y.
10. But then the pattern of his play would again become apparent, and I would shift to X. 11. Since he can just as readily discern what strategy *I* am following, and we have no grounds to assume that his understanding of the game is inferior to mine, he is as likely to play the strategy that defeats mine as vice versa. I might adopt a metastrategy in which I sometimes follow X, sometimes Y, and sometimes Z. I'm afraid this gets me into metalogic and ties me into mental knots. 12. But I think it contradicts assumption 7.
13. The nontrivial question is, does there exist a strategy W that wins against anyone who doesn't follow the same strategy? And if so, is it unique? 14. There might be two or more different strategies, W, V, U, ..., each of which defeats any other strategy, but which draw against one another. 

Jun1917   john barleycorn: Let A and B be the $20 jars and C the $25 jar. The worst strategy is to put all your marbles in one jar. Your opponent plays A=B=1 and C=8 to win a fortune. Splitting your 10 marbles among 2 jars and leave the 3 jar empty is also not the best idea in the world. If you would choose randomly one of the 27 possiblities to do so and the second player puts 1 marble into A, 3 into B, and 6 into C he will win provided the game is played often enough. So, an optimum strategy has to consider at least one marble in each jar, the fact that your jar wins if it contains 1 marble more than the opponents corresponding jar and holding 2 more more marbles than your opponent's jar means nothing. Furthermore, you cannot win/lose on all three jars, you cannot have 2 wins /losses and a draw, nor 2 draws and a win/loss. Probably best is choosing randomly from the following (A;B;C)= (1;4;5), or any permutation thereof.
Since your opponent may know that too, he may choose accordingly an thus making it an equal game. 

Jun1917   john barleycorn: <sneaky> <if I played (3,3,4)> consider:
(3,3,4) against (1,4,5), (1,5,4), (4,1,5), (4,5,1), (5,1,4), (5,4,1). It is losing big time :) 

Jun1917   john barleycorn: <al wazir: <Sneaky>: ...
2. Suppose there is an optimal strategy, a strategy that guarantees that its adherent always wins over an extended series of plays. 3. If both black and white play the *same* optimal strategy, neither would come out ahead. 4. This contradicts assumption 2. >
How can you assume an always winning strategy which when copied by the opponent is not winning? All you can claim is a nonlosing strategy in that case. There is a difference. 

Jun1917   john barleycorn: <5. Therefore there is no winning strategy. 6. The best that can be achieved is a strategy which ensures that its adherent doesn't lose. 7. It is not obvious that such a strategy exists. ...> ok, are you saying there is no winning strategy (your point 1.  4.) and the existence of a "nolose" strategy is questionable? What the heck are you talking about?
Can you give an example where the relation "x is a better strategy than y" is not transitive? 

Jun1917
  johnlspouge: Rockpaperscissors on a comparison of pure strategies: always "rock", always "paper", always "scissors". [ https://arxiv.org/pdf/1406.2212.pdf ]
Nontransitivity holds for many patterns when matching patterns in a coin toss (the application I am most familiar with), as the reference mentions. Define "better"? 

Jun1917   john barleycorn: <johnlspouge: Rockpaperscissors on a comparison of pure strategies: always "rock", always "paper", always "scissors". [ https://arxiv.org/pdf/1406.2212.pdf ]
Nontransitivity holds for many patterns ...> Wait,a nontransitive game is a different thing from a nontransitive strategy to play the game. In a nontransitive game it is a good strategy not to be the first to choose and play. and if it is not good to be the first player it also not good to be the second player if more than 2 players are involved. Clearly, transitive. 

Jun1917   john barleycorn: <johnlspouge: ...
Define "better"?>
My paraphrasing for <al wazir>'s <X always beats Y> 

Jun1917   nok: I think Sneaky wants the best play against a random opponent. 

Jun2017
  johnlspouge: <Sneaky>'s problem is a zerosum twoperson game. Its symmetry guarantees a value of 0.0, i.e., best play yields both players no payoff on average. The game's only distinguishing feature seems to be the symmetry of the $20 jars. In principle, the symmetry simplifies the solution. (Section 3.5 in [ https://www.math.ucla.edu/~tom/Game... ] describes the simplification: basically you play any symmetries with probabilities equal to each other, and then you average the payoffs of the four symmetric options for the two players to reduce the size of the payoff matrix.) The reduction made no practical difference: I just threw the whole payoff matrix into the online game solver at [ http://levine.sscnet.ucla.edu/games... ] The solver uses a simplex method for solving the linear constraints in the minimax criterion for an optimal strategy. Without simplifying with symmetry, for N marbles and K jars, elementary combinatorics shows that each player has N+K1 choose K1 possible plays, so for N=10 and K=3, each player has 12.11/2=66 possible moves; for N=3 and K=3, 5.4/2=10. The complete payoff matrix for 3 marbles is
(0,0,3) 0,5,5,5,5,15,15,5,15,5
(0,1,2) 5,0,5,5,0,5,15,25,5,25
(0,2,1) 5,5,0,5,25,0,5,0,25,25
(0,3,0) 5,5,5,0,25,25,0,25,0,0
(1,0,2) 5,0,25,25,0,5,5,5,15,5
(1,1,1) 15,5,0,25,5,0,5,0,5,25
(1,2,0) 15,15,5,0,5,5,0,25,0,0
(2,0,1) 5,25,0,25,5,0,25,0,5,5
(2,1,0) 15,5,25,0,15,5,0,5,0,0
(3,0,0) 5,25,25,0,5,25,0,5,0,0
where Player 2 (columns) has the same moves as Player 1 (rows). You can check payoffs to see that my program calculates the payoff matrix correctly. The format permits entry into the online calculator with minimal editing. The calculator returns an optimal strategy (0,0,3) 0
(0,1,2) 0.166666667
(0,2,1) 0
(0,3,0) 0
(1,0,2) 0.166666667
(1,1,1) 0.333333333
(1,2,0) 0.166666667
(2,0,1) 0
(2,1,0) 0.166666667
(3,0,0) 0
which is indeed symmetric in the two $20 jars.
For 10 marbles, it returns an optimal strategy (omitting 0.0 probabilities) (0,3,7) 0.115384615
(0,5,5) 0.019230769
(1,1,8) 0.057692308
(1,4,5) 0.076923077
(1,6,3) 0.019230769
(2,0,8) 0.019230769
(2,3,5) 0.038461538
(2,6,2) 0.076923077
(3,0,7) 0.038461538
(3,1,6) 0.076923077
(3,6,1) 0.038461538
(4,1,5) 0.019230769
(4,5,1) 0.115384615
(5,2,3) 0.134615385
(5,5,0) 0.019230769
(6,0,4) 0.076923077
(6,4,0) 0.057692308
Note that I edited obvious rounding errors in near0 probabilities out. The probabilities sum to 1.0, but the given optimal strategy is not symmetric (e.g., (4,6,0) had 0.0 probability, whereas (6,4,0) had probability 0.057692308). 

Jun2117   john barleycorn: <johnlspouge> setting up the 66 x 66 matrix for gives me slightly different results. (provided I did it right) For example (4,6,0) and (6,4,0) have the same negative expectation of 3,25 $/game. My complete list of combinations with positive expectatio: (0,2,8)
(0,3,7)
(0,4,6)
(0,6,4)
(0,5,5)
(2,0,8)
(3,0,7)
(4,0,6)
(6,0,4)
(5,0,5)
(1,1,8)
(1,2,7)
(2,1,7)
(1,3,6)
(1,6,3)
(3,1,6)
(3,6,1)
(6,1,3)
(6,3,1)
(1,4,5)
(1,5,4)
(4,1,5)
(4,5,1)
(5,1,4)
(5,4,1)
(2,2,6)
(2,6,2)
(6,2,2)
(2,3,5)
(2,5,3)
(3,2,5)
(3,5,2)
(5,2,3)
(5,3,2)
(2,4,4)
(4,2,4)
(4,4,2)
(3,3,4)
(3,4,3)
(4,3,3) 

Jun2117   john barleycorn: The short version of it:
any permutation of one of the following distributions has a positive expectation: (1,3,6), (1,4,5), (2,2,6), (2,3,5), (2,4,4), (3,3,4) and any of the following distributions with the first 2 components switched (0,2,8), (0.3,7), (0,4,6), (0,5,5), (0,6,4), (1,1,8), (1,2,7) It is clear that a distribution (k,l,m) has the same expectation as (l,k,m) (the first 2 components give the marbles in the $20 jars) 

Jun2317   john barleycorn: <johnlspouge> just look at your 3 marble example. < ...
The complete payoff matrix for 3 marbles is
...
(1,2,0) 15,15,5,0,5,5,0,25,0,0
...
(2,1,0) 15,5,25,0,15,5,0,5,0,0
...>
Well, (1,2,0) and (2,1,0) have 10 payout.
<... The calculator returns an optimal strategy ...
(1,2,0) 0.166666667
...
(2,1,0) 0.166666667 >
Which is very much doubted. 

Jun2417
  johnlspouge: @<john barleycorn>: Theorem 3.1 in the previous web reference [ https://www.math.ucla.edu/~tom/Game... ] gives necessary conditions on an optimal solution. A more thorough treament, e.g., Theorem 2.9 in JCC McKinsey (1952)
Introduction to the Theory of Games
McGrawHill
expands the theorem into necessary and sufficient conditions. I checked the necessary and sufficient conditions by hand for the 3marble case, and the solution I gave is optimal. 

Jun2417   john barleycorn: <Johnlspouge> with all due respect no strategy reverses a negative payout. I think (1,2,0) and (2,1,0) got mixed up with (0,2,1) and (2,0,1). Also as mentioned (6,4,0) and (4,6,0) must have the same expectation. (on the side why do you always mention probabilities? games are evaluated by their expectation) (5,5,0) in the 10 marbles variant is also not winning. These things can be calculated in the "pedestrians" approach. 

Jun2617
  johnlspouge: Player 1 optimally plays the indicated strategy that I gave before, randomizing his plays according to the probabilities I gave before from the online calculator (0,0,3) 0
(0,1,2) 1/6
(0,2,1) 0
(0,3,0) 0
(1,0,2) 1/6
(1,1,1) 1/3
(1,2,0) 1/6
(2,0,1) 0
(2,1,0) 1/6
(3,0,0) 0
Using the payout matrix (to Player 1) that I gave before, Player 2's pure strategies (indexed below in column form, as Player 1's were, above) yield the indicated expected payouts to Player 1, if Player 1 uses the optimal strategy above. (Multiply the payout by optimal probability and sum over the column of the pure strategy for Player 2 in the payout matrix.) (0,0,3) 50/6
(0,1,2) 0
(0,2,1) 0
(0,3,0) 80/6
(1,0,2) 0
(1,1,1) 0
(1,2,0) 0
(2,0,1) 0
(2,1,0) 0
(3,0,0) 80/6
Thus, every convex combination of pure strategies for Player 2 forces a nonnegative payout from Player 2, so Player 2 can at most hold Player 1 to a 0 payout, which (because the game is symmetric) is the value of the game. Player 2 has the same optimal strategy as Player 1, and (with payout signs reversed) Player 1 can not extract a positive expectation from Player 2. < <john barleycorn> wrote : on the side why do you always mention probabilities? games are evaluated by their expectation > The probabilities are the basis of mixed strategies. The references I gave explain them. The online calculator you used provides probabilities for the optimal mixed strategy, and you should have provided them as part of the solution for the optimal strategy. 

Jun2617   nok: I think the question was best play(s) against a uniformly random opponent, not optimized. (And how it depends on the jar contents' ratio, I guess.) <I imagine a computer program that selects the distribution entirely at random.> 

Jun2617
  johnlspouge: @<nok> The original intent was not clear. I had assumed that <Sneaky>'s mention of a uniform strategy was musing, because otherwise the problem is a trivial calculation. <al wazir> seems to interpret the problem as I did. 

Jun2617
  johnlspouge: @<john barleycorn>: Apologies about the online calculator, which is irrelevant to the problem you were solving. 



< Earlier Kibitzing · PAGE 291 OF 291 ·
Later Kibitzing> 


