Zergcraft21
Zergcraft21
Joined: Mar 17, 2014
  • Threads: 1
  • Posts: 3
April 11th, 2014 at 2:06:34 PM permalink
Problem statement:
You have N actions that each loose or win 1 unit each trial with their own probability [0,1]. I don't know each action's return, but can simulate the actions. How do I minimize the number of total trials to pick the single action with the highest return for a given accuracy?

Another version of the statement:
I have two coins: One that comes up heads 49% of the time and another than comes up heads 48% of the time, but I don't know which is which. What strategy does the least number of total flips to find which coin is the 49% coin and which is the 48% coin with 90% accuracy?

What if I don't know the coin's probabilities, I just know that they aren't equal. What strategy will pick the coin with the highest head's probability with 90% accuracy?

Context:
I'm writing a simulator for various card/deck situations. Mostly a fun project. I'm having trouble knowing when to 'end' the simulation in each situation. I could run it forever, and it will converge on a value, but I would rather 'exit out' some situations early if it's pretty obvious that one answer is better than another. For example, think of hitting versus standing on hard 20 in blackjack compared to a hit with 16 vs 10.
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 41
  • Posts: 2268
April 11th, 2014 at 2:18:42 PM permalink
Quote: Zergcraft21

Context:
I'm writing a simulator for various card/deck situations. Mostly a fun project. I'm having trouble knowing when to 'end' the simulation in each situation. I could run it forever, and it will converge on a value, but I would rather 'exit out' some situations early if it's pretty obvious that one answer is better than another. For example, think of hitting versus standing on hard 20 in blackjack compared to a hit with 16 vs 10.

Basic strategy for blackjack is created using combinatorial analysis, not simulation.
Poetry website: www.totallydisconnected.com
Zergcraft21
Zergcraft21
Joined: Mar 17, 2014
  • Threads: 1
  • Posts: 3
April 11th, 2014 at 2:23:32 PM permalink
Thanks. That makes sense, but I would still like to simulate various situations and think the problem is still interesting on its own.
socks
socks
Joined: Jul 13, 2011
  • Threads: 15
  • Posts: 364
April 11th, 2014 at 2:41:48 PM permalink
I've also been wondering about simulations and making choices. Being less experienced with gaming math, I'd like to have a second method to test things when I get an answer using one method. But then, when making decisions, I could easily end up with suboptimal decisions if I'm not taking a large sample at every step, right?

Being from the poker world, and using tools like pokercruncher, I'd always though that simulations gave you a lot leverage since you could get close with only a fraction of the actual calculations, but now I'm thinking that the opposite might be true for many situations where you aren't ballparking things with hot/cold runs, but are trying to account for multiple intermediate decisions. Comments? Is it really hard to make useful simulations, to say, sanity check you BJ code. (I know classic BJ doesn't need a sanity check as hard numbers are freely available, but think alt-BJ, or something)
rdw4potus
rdw4potus
Joined: Mar 11, 2010
  • Threads: 80
  • Posts: 7237
April 11th, 2014 at 3:17:17 PM permalink
I'm thinking you'd need a huge number of trials to sim some of these things. Thinking of polling math...if you ask 350 people a binary poll, the true result is +-5% with a 95% CI. If you ask 1100 people, the true result is +-3.5% with a 95% CI. Extrapolate and look at the number of trials you'd need to determine with 90% confidence that 1 of 2 coins was the 48% and not the 49% coin. Or whether it was better to hit or stand on a 16 v 10. The point where you can even approach being sure that bias exceeds variance is extremely high.

NOTE: writing from my phone. only 50% sure the straddles and CI #s above are right. But the point stands even if the math is fuzzy.
"So as the clock ticked and the day passed, opportunity met preparation, and luck happened." - Maurice Clarett
Zergcraft21
Zergcraft21
Joined: Mar 17, 2014
  • Threads: 1
  • Posts: 3
April 11th, 2014 at 4:22:09 PM permalink
-Edit: Odds worse than I thought :( -
endermike
endermike
Joined: Dec 10, 2013
  • Threads: 7
  • Posts: 584
April 13th, 2014 at 3:57:09 PM permalink
http://en.wikipedia.org/wiki/Multi-armed_bandit

Not my exact area of expertise, but this would be a good start if you are still interested.
dwheatley
dwheatley
Joined: Nov 16, 2009
  • Threads: 25
  • Posts: 1246
April 13th, 2014 at 4:03:53 PM permalink
For your N action problem I posted a technique I think is reasonably efficient in another thread:

http://wizardofvegas.com/forum/questions-and-answers/math/17439-a-bag-of-possibly-unfair-coins/#post339656
Wisdom is the quality that keeps you out of situations where you would otherwise need it

  • Jump to: