Strategy analysis

LiteS · 2015-02-13 16:35:09

Alright, I've been through the forums for a bit and found a few mentions of picking strategy, the common methods I've heard are "Lowest high number for opponent" and "Pick randomly". This game is designed with multiple strategies in mind, but being able to calculate them twice manually (once for your columns, and again for opponent's rows) is time-prohibitive. A topic I've heard mentioned by Jason, but not really expanded upon, is row/column variance, but actually crunching the numbers isn't practical by hand.

I believe it's possible to extract the magic square from the game somehow. I haven't figured it out how to do it automatically, but typing a square out into a prepared spreadsheet can visually display picks for just about every strategy imaginable, and can give some insight into your opponent's picks.

CM Excel example

I don't believe this is cheating, but I do believe it gives an advantage to those that do it, since certain strategies become glaringly obvious when displayed this way.

I haven't found it yet, but is there a simple way to extract the 6x6 square from the game? I've included five non random basic strategies, what others have y'all noticed?

Edit:
If anyone would like the spreadsheet, let me know and I'll post it.

Last edited by LiteS (2015-02-13 20:22:42)

AnoHito · 2015-02-13 18:09:53

You just had to go and spoil it for me didn't you? ;P I was just talking about my top secret new picking strategy in the chat last night, but pretty much anyone looking at your chart would be able to figure out what I was doing... Ungh, I was hoping it would at least be until the game was actually released before someone else figured it out. By the way, it's really not that hard to estimate variance in your head if you know what to look for. It's not 100% accurate, but a little inaccuracy actually adds an element of randomness that can work in your favor.

.. · 2015-02-14 01:01:11

That's a very unusual sample magic square.

You can extract the magic square from the log saved to recordedGames/, just need to pull it out with a regex.

jasonrohrer · 2015-02-14 02:24:40

You could also set up a simple web proxy that scrapes the square out of the protocol (the protocol is all HTTP).

For median, you're taking the average of the middle two values (there are an even number of values in a row, so there is no middle value). But what value is the median? What does it tell you?

.. · 2015-02-15 09:21:43

Yes, the median is only a proxy for the actual useful information there: knowing that 50% of the numbers in a row/column are above/below some value.

LiteS · 2015-02-16 18:52:17

jasonrohrer wrote:

But what value is the median? What does it tell you?

That's one of the things I'm trying to figure out. In the analysis I've done so far, no strategy gives either player an advantage over a single player picking randomly. I have found that some boards have a near insignificant bias toward one player (the one I posted gives the player playing rows less than a half a percentage edge). This could be the "variance advantage" alluded to earlier.

So what does it all mean?

Well, if you or your opponent is down to their last chips (say, less than double the ante), and bluffing is no longer an option, if either player picks randomly the game is up to Minosons.

.. wrote:

That's a very unusual sample magic square.

I picked a spiked variance one on purpose just to see if anything interesting would come of it.

EDIT:
Whoops, turns out I'm wrong, there are strategies that give about a 5% edge against random picks, but picking for the median isn't one of them. I'm still building the spreadsheet.

Last edited by LiteS (2015-02-16 19:20:28)

jere · 2015-02-16 19:39:26

I'd figure a random strategy is a lot more exploitable than a 5% advantage. Assuming you had a column that looked like that first row give them that: 83% chance they have no more than 26. 33% chance they have no more than 6.

Give yourself that first column and you have 50% chance of a 30+. At least when the ante is low, you just fold half the time you get a raise.

Am I way off?

Last edited by jere (2015-02-16 19:41:51)

LiteS · 2015-02-16 22:16:59

jere wrote:

I'd figure a random strategy is a lot more exploitable than a 5% advantage. Assuming you had a column that looked like that first row give them that: 83% chance they have no more than 26. 33% chance they have no more than 6.
Give yourself that first column and you have 50% chance of a 30+. At least when the ante is low, you just fold half the time you get a raise.
Am I way off?

I'm starting the analysis by assuming every game is played to fruition, no folding, just to get a baseline. That 50% chance of 30+ is pretty much exactly that, a 50/50 shot at winning.

When I have the time I'll break it down further, but the more math I do on static boards the more handicapped I feel playing the game in real time.

joshwithguitar · 2015-02-17 00:11:08

Using perfect play against a random opponent you will win around 2/3 of the games (I am very certain of this). So a random strat is not a great idea.

Last edited by joshwithguitar (2015-02-17 00:11:37)

jasonrohrer · 2015-02-17 01:38:52

One question is: Does random mean random all the way through, or random only on the first pick?

As Jere has demonstrated, there are situations on the third pick where you can force a win by picking right. If you're picking randomly even then, clearly you are throwing away victories.

Looking back at my tests with various AI bots, I recall that I had to serialize the game so that regular game tree minimax could be applied to it (regular minimax doesn't handle hidden information). So, the 82% win rate that I saw for tree mimimax vs a random opponent doesn't tell us much, because the minimax AI had too much information (it knew what its opponent picked turned 1 before making its pick turn 2).

A kind of blind Monte Carlo method against a random opponent would be to simulate the random opponent against all possible picking orders that we could use. There are only 720 to test, which seems pretty reasonable. Then you'd just pick the picking order that has the best average outcome. I'll experiment with this and report back. Maybe that's what Josh has already done to get his 2/3 figure.

jere · 2015-02-17 02:19:23

Well, I haven't done any analysis like ya'll, but feel like I have a pretty good intuition on some things.

I'm starting the analysis by assuming every game is played to fruition, no folding, just to get a baseline. That 50% chance of 30+ is pretty much exactly that, a 50/50 shot at winning.

I guess what I was referring to was how to get a strong opening pick and be very confident that you have a good lead. From that perspective, it's better to have that 50% of the time than have a middling pick all the time (low variance).

I definitely wasn't considering the whole game with no folding. For that, I totally believe Josh's 2/3 number. In that case, random is fine for the first round because all rows/columns have the same average. But that's not true in later rounds, because high and low numbers have been eliminated. In the 2nd round, you start to see clear "winner" and "loser" columns. Normally, the opponent knows you're gunning for these, but a random strat obviously is oblivious. And then like you said, Jason, many times the last round can be very lopsided and random is going to fare badly in those cases.

.. · 2015-02-17 02:49:31

Minimax doesn't seem very relevant when either player acts randomly; what you should use to pick a move against an opponent that doesn't look ahead is expectimax. You do opponent modelling and predict how the opponent will act on each turn, e.g. pick uniformly at random. But if your opponent is actually trying to outwit you then they'll also consider how you might act, and the name of the game is completely different; you're searching for Nash equilibria.

LiteS wrote:

the more math I do on static boards the more handicapped I feel playing the game in real time.

Haha, I felt the same way! Had to remind myself that I was playing for fun, not just to win.

jasonrohrer · 2015-02-17 04:24:29

Okay, interesting preliminary result, which was unexpected to me:

Monte Carlo simulation of a random opponent, and picking a pre-ordained, non-reactive move list that does "best" against the simulation on a given board, does not produce a move list with anything that looks like a statistically significant edge against said random opponent. I'm no expert in stats, but a 5% edge on 1000 experiments that erodes down to a 2% edge on 10,000 experiments and down to a 1% edge on 100,000 experiments looks like noise.

Also, taking a non-reactive move list that wins the most over 1000 games and running it for another 1000 often produces a worse win rate or even a majority loss (rarely---so there's probably a slight edge to be had).

So, being reactive is clearly necessary to defeat a random opponent.

Open question: when playing a random opponent, can you do better than picking randomly yourself on turn 1? I think you can.

jasonrohrer · 2015-02-17 04:41:03

Whoops... Monte Carlo isn't needed. There are only 720 possible ways your random opponent can play. So, just need to simulate each of your 720 non-reactive strategies against each of those opponent strategies and see which one wins the most.

There's always an edge when you do this. Rarely it's as high as 3%, rarely as low as 0.5%, and usually between 1 and 2%.

jasonrohrer · 2015-02-17 07:20:54

A naive reactive maximizing opponent against a known random opponent can achieve a win rate of 65% according to my simulations.

If the reactive maximizing opponent picks randomly on turn 1 instead of considering the best choice, the win rate goes down to 60%.

I think that doing full-blown expectimax will achieve even better than 65%. Though Josh is saying perfect play will win 2/3, so maybe not.

LiteS · 2015-02-18 04:44:43

jasonrohrer wrote:

Whoops... Monte Carlo isn't needed. There are only 720 possible ways your random opponent can play. So, just need to simulate each of your 720 non-reactive strategies against each of those opponent strategies and see which one wins the most.
There's always an edge when you do this. Rarely it's as high as 3%, rarely as low as 0.5%, and usually between 1 and 2%.

Using the board presented, simply picking the three columns with 34, 35, and 36 for yourself and the remaining three for the opponent skewed in your favor by about 5%. And yeah, since I was assuming perfectly random I avoided Monty Hall situations (I picked random cuz it's an easy start). I just had to find all possible plays for the opponent and then add up how many times I won, how many draws, and how many times random won.

I'm currently only working with one board, so if/when I find Nash equilibrium for this board I can see if I can expand it to another board. My current guess is Nash equilibrium for this game is similar to the one in the prisoner's dilemma, in which the "best" play is actually just a "lose the least", but I could be wrong.

Edit: Missed Jason's most recent post. I'm assuming we're getting different numbers (65% vs 55%) because I'm counting draws as losses.

Last edited by LiteS (2015-02-18 04:49:55)

jasonrohrer · 2015-02-18 06:24:07

No, I'm counting draws as losses. Win rate of 65% means win rate.

I'm actually playing my "bot" against a random bot, turn by turn. My bot is looking at the available information each turn (what we know about what the opponent picked so far) and picking the move that leads to the highest expected win percentage. That's giving me a 65% win rate against the random opponent.

Also, different boards have slightly different win rates for this method, but the average across a bunch of boards is 65%.

LiteS · 2015-02-18 19:59:55

jasonrohrer wrote:

No, I'm counting draws as losses. Win rate of 65% means win rate.
I'm actually playing my "bot" against a random bot, turn by turn. My bot is looking at the available information each turn (what we know about what the opponent picked so far) and picking the move that leads to the highest expected win percentage. That's giving me a 65% win rate against the random opponent.
Also, different boards have slightly different win rates for this method, but the average across a bunch of boards is 65%.

Ahh, so you're re-optimizing picks every round, while I'm just picking all columns simultaneously. I haven't taken the rounds into account yet, still working on it, but now the discrepancy makes sense.

jasonrohrer · 2015-02-20 20:06:41

Yeah, I tried that too.

Assume a random opponent, and pick the optimal order for the 6 columns that I'm going to pick. That method was only netting a very small advantage... something around 2% (52% win rate when the number of trials got large).

joshwithguitar · 2015-02-21 00:20:40

Using my method (which I think is optimal) you should win close to 68% of the time (counting draws as not winning).

My method finds the move with the largest expected win rate given that it will also play the moves with the largest expected win rate in the later rounds and a random opponent.

jasonrohrer · 2015-02-21 02:35:03

Josh, does your method pick all 6 moves up front, before seeing any of the opponent's choices? Or does it make decisions step-by-step, two picks at a time?

joshwithguitar · 2015-02-21 22:47:36

Up front it decides what moves it would make in any given situation so it doesn't have to recalculate each time a move is made. The moves it takes do take into account the red moves of the opponent.

jasonrohrer · 2015-02-21 23:50:30

Oh, so it is essentially computing the whole partial-information game tree up front. So, your results pretty much agree with mine, then.

context fabric · 2015-02-25 06:42:29

Ive been watching this thread since Im doing my own statistical analysis using Octave.

I just happened to notice you said there are 720 possible moves your opponent (or yourself) could make. The actual number is 120 (unless im missing something?), which is a lot less to test against.

jasonrohrer wrote:

Whoops... Monte Carlo isn't needed. There are only 720 possible ways your random opponent can play. So, just need to simulate each of your 720 non-reactive strategies against each of those opponent strategies and see which one wins the most.

Im guessing you came up with the 720 with 6!

I actually generate the possible 120 moves with this funtion

# returns a set of unique possible moves a player could make
#  size(result) = 120 3
#  result = [ first_pick, second_pick, third_pick ]
function result = possibleMoves()

	result = [];
	
	for first_pick = 1:6
		for second_pick = 1:6
			for third_pick = 1:6
			
				if first_pick == second_pick || first_pick == third_pick || second_pick == third_pick
					# do nothing
				else
					# append possible move sequence
					result(end+1, [1, 2, 3]) = [first_pick, second_pick, third_pick];
				endif
				
			endfor
		endfor
	endfor
	
	# filter out duplicate move sequences
	result = unique(result, "rows");
	return;

endfunction

Also I would be interested in your spreadsheet LiteS if you want to share it.

Last edited by context fabric (2015-02-25 09:06:01)

storeroom leaflet · 2015-02-25 07:06:14

Context: you are forgetting about the picks for your opponent! Including picks for your opponent there are definitely 6!=720 ways of doing this.

CORDIAL MINUET ENSEMBLE

#1 2015-02-13 16:35:09

Strategy analysis

#2 2015-02-13 18:09:53

Re: Strategy analysis

#3 2015-02-14 01:01:11

Re: Strategy analysis

#4 2015-02-14 02:24:40

Re: Strategy analysis

#5 2015-02-15 09:21:43

Re: Strategy analysis

#6 2015-02-16 18:52:17

Re: Strategy analysis

#7 2015-02-16 19:39:26

Re: Strategy analysis

#8 2015-02-16 22:16:59

Re: Strategy analysis

#9 2015-02-17 00:11:08

Re: Strategy analysis

#10 2015-02-17 01:38:52

Re: Strategy analysis

#11 2015-02-17 02:19:23

Re: Strategy analysis

#12 2015-02-17 02:49:31

Re: Strategy analysis

#13 2015-02-17 04:24:29

Re: Strategy analysis

#14 2015-02-17 04:41:03

Re: Strategy analysis

#15 2015-02-17 07:20:54

Re: Strategy analysis

#16 2015-02-18 04:44:43

Re: Strategy analysis

#17 2015-02-18 06:24:07

Re: Strategy analysis

#18 2015-02-18 19:59:55

Re: Strategy analysis

#19 2015-02-20 20:06:41

Re: Strategy analysis

#20 2015-02-21 00:20:40

Re: Strategy analysis

#21 2015-02-21 02:35:03

Re: Strategy analysis

#22 2015-02-21 22:47:36

Re: Strategy analysis

#23 2015-02-21 23:50:30

Re: Strategy analysis

#24 2015-02-25 06:42:29

Re: Strategy analysis

#25 2015-02-25 07:06:14

Re: Strategy analysis

Board footer