Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 20 21 [22] 23 24 ... 47  All

Author Topic: Maths thread.  (Read 307085 times)

0 Members and 1 Guest are viewing this topic.

eHalcyon

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 8689
  • Respect: +9187
    • View Profile
Re: Maths thread.
« Reply #525 on: September 30, 2015, 07:45:05 pm »
0

Troll image?
Logged

Awaclus

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 11808
  • Shuffle iT Username: Awaclus
  • (´。• ω •。`)
  • Respect: +12846
    • View Profile
    • Birds of Necama
Re: Maths thread.
« Reply #526 on: September 30, 2015, 08:01:41 pm »
+9

Troll image?

No, it's actually true. Just like this one:

Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

The YouTube channel where I make musicDownload my band's Creative Commons albums for free

silverspawn

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5300
  • Shuffle iT Username: sty.silver
  • Respect: +3188
    • View Profile
Re: Maths thread.
« Reply #527 on: September 30, 2015, 08:08:34 pm »
0

Troll image?

it's 120 = 5*4*3*2*1 = 5!

it's supposed to be clever n stuff.

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #528 on: September 30, 2015, 08:10:35 pm »
+3

Troll image?

Yes, but not that kind of troll image, the other kind.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

eHalcyon

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 8689
  • Respect: +9187
    • View Profile
Re: Maths thread.
« Reply #529 on: September 30, 2015, 08:21:50 pm »
+1

D'oh.  :-[
Logged

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2860
    • View Profile
Re: Maths thread.
« Reply #530 on: October 01, 2015, 11:07:32 am »
+1

This might be the right thread for this.

I was musing this morning on how the Secretary Problem might be modified to handle "who should I main" in MOBAs.

For this, you'd want some same assumptions, some different assumptions:

I. You are going to play N games testing A applicants before selecting your applicant (the same, people tend to have an idea of how much time they want to waste experimenting)

II.  Unlike the Secretary problem, you are free to go ahead and play all N games (though it'd be nice to have a strategy where you quit early if you can completely rule out all but one hero.)

III. Like the secretary problem, the process of gathering information about applicants is sequential in nature, but unlike the secretary problem, you can make up to P passes through the list, revisiting only sufficiently impressive cantidates (The way most players enjoy/efficiently learn suggests that games on the same hero be consecutive.  The large number of characters in a MOBA game requires that P be small.. definitely less than ten.  In Starcraft A=three so P can equal, like, twenty.
It seems like this may need to be revised or cleaned up to reflect that playing a large number of games on a champion, leaving it, then returning it for another long string of games, creates far less testing bias then playing a champion once on first pass, once on second past, etc.)

IV. Like the secretary problem, each applicant has a true value V.  V is your winrate over an infinite number of games with the champion, so it ranges from 0 to 1.  You could probably use practical knowledge about the game to clamp the values to at least .1 through .9 and probably something even smarter than that, but there's lots of parameters already.

V. Like the secretary problem, you gather information about V when you spend time with an applicant.  Unlike the secretary problem, your knowledge is imperfect, and dependent on the amount of time you spend with an applicant.  You'll get a value of wins over games played, and that will have an imperfect correspondence with V, but it gives you some information about V.

VI.  Unlike the secretary problem, the final choice does not have to be last champ you played.  Due to the consequences of rule III and rule I you still might have to reject choices early on in a manner somewhat reminiscent of how those secretaries get very indignant if you don't hire them on the spot.

VII.  The optimal solution to the problem maximizes the V of the final champion selected.  The value of V is more important than how V is relative to the other champions, though, unlike the secretary problem (all though if the secretary problem were made more practical, it would probably also be more concerned with V)(Unless there's all the ones you don't hire join other company's and then you lose the intramural between company's secretary-off).




The idea interest me a bit, and as MOBAs get more stable and balanced there might be more interest in playing the game in a style that sort of chases the solution here.
I find it rather fascinating that the optimal solution quite possibly excludes some applicants entirely when A is small, and N is large.  Maybe even if P is still large or infinite.  Because getting accurate information could be so much more important than being open to every possibility.  The interesting question is, how many applicants will get excluded?  If it proves best to clamp the lowest to highest winrates as something like 15%-60%, it might, paradoxically, sometimes be correct to ignore a totally unplayed virgin champion while you continue to explore a champion you are are 1-1 with, even if the algorithm is doing much better than a .5 V on average, just because you can build a reliable source of information without being two games behind and have ruled against the champion being awful.

Idk just some musings in b4 no1 reads
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Maths thread.
« Reply #531 on: October 01, 2015, 02:21:25 pm »
0

So what are you trying to do?  Doing the experimental games is basically Bayesian statistics, you have some prior distribution of your strength with each champ, and you try to narrow this distributions down by including observations. At the end, you chose one champ.

So the overall goal would be to maximize the expectation value (wrt to the prior distribution (?)) of the real strength of the chosen champ, over all strategies to test these champs.

There are some parameters here that you would have to specify, as the priors and how your observations update the priors. How well you do this influences how good your optimization can be (or you also optimize over these, but that will get really complicated). Given all these I'm not sure if one can analytically solve the problem, but at least one could do simulations.



keep the text below here which is how that post started, is kind of unrelated to the one above but might be interesting, too
---------------------

The problem is interesting, but not specified enough to give a solution, I suggest even the type of the strategy depends on further parameters.
First one that comes to my mind is to fix "how much information do I gather per game".
If that is "everything", you of course just want to test as many champs as possible
If the marginal information is increasing with the number of games you play with a champ (e.g. the second game might give you more information than the first, as you can make more informed tests) the strategy will look significantly different than if it is decreasing (the 1000th game will give you less marginal information than the first probably). 

So you would have to fix that, something like maybe delta information = xe^⁻x .  Or just e^-x is you think the first game is more important than the second.



Logged

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2860
    • View Profile
Re: Maths thread.
« Reply #532 on: October 01, 2015, 03:29:59 pm »
0

So what are you trying to do?  Doing the experimental games is basically Bayesian statistics, you have some prior distribution of your strength with each champ, and you try to narrow this distributions down by including observations. At the end, you chose one champ.

So the overall goal would be to maximize the expectation value (wrt to the prior distribution (?)) of the real strength of the chosen champ, over all strategies to test these champs.

There are some parameters here that you would have to specify, as the priors and how your observations update the priors. How well you do this influences how good your optimization can be (or you also optimize over these, but that will get really complicated). Given all these I'm not sure if one can analytically solve the problem, but at least one could do simulations.



keep the text below here which is how that post started, is kind of unrelated to the one above but might be interesting, too
---------------------

The problem is interesting, but not specified enough to give a solution, I suggest even the type of the strategy depends on further parameters.
First one that comes to my mind is to fix "how much information do I gather per game".
If that is "everything", you of course just want to test as many champs as possible
If the marginal information is increasing with the number of games you play with a champ (e.g. the second game might give you more information than the first, as you can make more informed tests) the strategy will look significantly different than if it is decreasing (the 1000th game will give you less marginal information than the first probably). 

So you would have to fix that, something like maybe delta information = xe^⁻x .  Or just e^-x is you think the first game is more important than the second.

I think there's a miscommunication here.  The way I want to define the problem, the ONLY information gathered about a champion by playing a champion is whether you won or last, and what that win or loss suggests about V.  So if you play Chancellorman and win, you know that Chancellorman can't possibly have V=0, and there is a greater than 50% chance that Chancellorman's V is greater than 50%, because you've taken a random sample (with an awfully small sample size) out of an indefinite number of games played with Chancellorman.  Realistically, some details about that particular game might be somewhat useful to making guesses about V, but in order for the problem to be simple enough we're ignoring those.  (those details have also been largely discredited by statistics, according to developers' analysis of backend stats, but even if they were more useful it'd be simpler to drop them)

So the first game is no more important than the second, it doesn't even matter what ordered they were played.  They are treated as an unordered sample from a larger population of millions of games played with the champion, games you haven't played yet.


I know there's an exact formula for relating the characteristics of a small sample of a population to the population at large based on the sample size.  So "how much information do I gather per game" should already be exactly defined by those formulas, which I learned in high school and do not remember right now. 
I remember there was something special about a sample size of 30 being somewhat of a turning point in getting to a really good bead on the characteristics of the longer population, so it's possible the solution strategy looks something like testing a champ about 5 times, dropping it if it loss streaks out the gate, then continuing to test it to somewhere around 30 and moving on to the next champ at that point even if the champ is doing well.  And excluding enough champs that it will have a chance to get several dudes to 30.
Logged

Ratsia

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 168
  • Respect: +113
    • View Profile
Re: Maths thread.
« Reply #533 on: October 01, 2015, 03:48:23 pm »
+4

I was musing this morning on how the Secretary Problem might be modified to handle "who should I main" in MOBAs.
What you wrote sounds a lot like the multi-armed bandit problem, though the fact that you do not care about the winning rate while exploring makes the solution a bit easier.

There's been a lot of research on this in the machine learning community (and probably in some other fields too) during the past decade or so, in part because it solves online advertising. For practical applications with finite number of candidates and somehow reasonable distribution of the values any of the old standard solutions (Thompson sampling, upper-confidence bounds, etc) should work well, but for interesting theoretical properties you would probably need to do some reading.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Maths thread.
« Reply #534 on: October 01, 2015, 11:14:37 pm »
0

I think there's a miscommunication here.

Are you asssuming a fixed winrate for a champion, or are you assuming a fixed winrate for you with that champion? In the sense of how well it fits your playing style, personal skill and whatever.
If you are in the first case you are right and each game will matter the same, if you are in the second you could model it in a way that games are not equally important (but of course don't have to)
Logged

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2860
    • View Profile
Re: Maths thread.
« Reply #535 on: October 02, 2015, 09:07:25 am »
0

The fixed win-rate FOR YOU.  And yes, it's due to playstyle fit. 

I still don't understand how it's even possible to model games as having different importance with a fixed winrate, but I'd love if I'm missing a detail and you could help me see it!
« Last Edit: October 02, 2015, 09:09:16 am by popsofctown »
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Maths thread.
« Reply #536 on: October 02, 2015, 02:04:10 pm »
0

The fixed win-rate FOR YOU.  And yes, it's due to playstyle fit. 

I still don't understand how it's even possible to model games as having different importance with a fixed winrate, but I'd love if I'm missing a detail and you could help me see it!

Of course depends on how you model the whole stuff, if you do it the Bayesian way I think you can
a) assume there is a "true" fixed win-rate for you, but also assume that your win-rate in the first games is worse (or more reverted to 1/2) than the true one. Kind of cheated as it's not fixed any more, but the "true" one you want to find is still fixed.
b) If you calculate the posteriori distributions, you probably get something like constant * prior* (product of terms due to observations). You could just arbitrarily weight the terms from the first games lower (which, in this context is probably equivalent to a))

But in the meantime I am thinking, this all might add to much complexity (and more parameters) to the problem, I would first really solve it with "really" constant probabilities.
Logged

XerxesPraelor

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1069
  • Respect: +364
    • View Profile
Re: Maths thread.
« Reply #537 on: October 08, 2015, 09:30:58 am »
+1

I'm really frustrated at a particular math problem right now in the (already handed in) homework for introductory Math at CMU, and I'm hoping someone here might be able to justify it to me.

So there's a function f(x) from A to B.

Prove that if f is injective, and S and T are subsets of A, that f(S-T) = f(S) - f(T).

But S is a subset of A, not an element of A. Now the actual problem they want us to solve is obvious, but this kind of ambiguity seems really unforgivable when both definitions could apply in some situations. What makes it worse is that this alternate definition of f(S) was not explained in the homework or any time in class, so there's no reason to expect us to know it.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #538 on: October 08, 2015, 09:40:24 am »
+1

I'm really frustrated at a particular math problem right now in the (already handed in) homework for introductory Math at CMU, and I'm hoping someone here might be able to justify it to me.

So there's a function f(x) from A to B.

Prove that if f is injective, and S and T are subsets of A, that f(S-T) = f(S) - f(T).

But S is a subset of A, not an element of A. Now the actual problem they want us to solve is obvious, but this kind of ambiguity seems really unforgivable when both definitions could apply in some situations. What makes it worse is that this alternate definition of f(S) was not explained in the homework or any time in class, so there's no reason to expect us to know it.

So, these are standard notations:

S - T means S\T = { x in S: x not in T}

f(S) = {y: y=f(x) for some x in S}
f(T) = {y: y=f(x) for some x in T}
f(S-T) = {y: y=f(x) for some x in S-T} = {y: y=f(x) for some x in S and not in T}
f(S) - f(T) = { y: y in f(S) and y not in f(T)} = {y: y=f(x) for some x in S AND y is not f(z) for any z in T}

S and T are subsets of A, so S-T is not ambiguously defined.  They're sets; their difference is set difference. 

I think the problem is straightforward given these definitions.
Logged

XerxesPraelor

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1069
  • Respect: +364
    • View Profile
Re: Maths thread.
« Reply #539 on: October 08, 2015, 09:48:04 am »
0

Yeah I realize the sets aren't ambiguous. I'm talking about the function. It can mean both a function from A -> B and one from P(A) -> P(B).

PS. Yes, the problem was easy once I figured out the equivocation. I just wish they defined a new function instead of coopting f to be two different functions at the same time.
« Last Edit: October 08, 2015, 09:51:02 am by XerxesPraelor »
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #540 on: October 08, 2015, 09:49:12 am »
+1

Namely, suppose f is injective.  Then if y is an elements of B such that there is x1, x2 in A with f(x1) = y, f(x2) = y, we must have x1 = x2.  (I.e., two unique elements in the domain cannot map to the same element in the range.)

First, let y be in f(S-T).  Then y = f(x) for some x in S-T, which is an x that is in S and not T.  We need to show that y is in f(S)-f(T).    Since y = f(x) and x is in S, y is in f(S).  Moreover,  x is not in T. Can y be in f(T)?  If it were, then there would be z in T such that f(z) = y.  But, f(x) = y, and by the injective property of x, this implies x=z.  This is a contradiction, because z is in T but x is not. Therefore, y is not in f(T).  Thus, y is in f(S) but not f(T), so y is in f(S) - f(T).

Now let y be in f(S) - f(T).  We need to show y is in f(S-T).  This is now straightforward.  Because y is in f(S)-f(T), y is in f(S).  So there is an x in S so that y=f(x).  However, y is not in f(T).  So it cannot be the case that x is in T, because then y would be in f(T).  So, x is in S and not T, so x is in S-T.  Thus, y is in f(S-T).

We have shown f(S-T) and f(S)-f(T) are subsets of reach other, and therefore equal.

Note that f being injective was used in only one direction.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #541 on: October 08, 2015, 09:51:30 am »
0

Yeah I realize the sets aren't ambiguous. I'm talking about the function. It can mean both a function from A -> B and one from P(A) -> P(B).

A function is defined with its domain (and codomain).

f: A->B means f is defined to map elements in A and elements in B.

f:P(A)->P(B) and f:A->B are entirely different things, even though you use the same "f" for them.  In your problem, the former was defined and the latter was not. (Well, it's implicitly defined:

Any function f:A->B defines g:P(A)->P(B) by g(T) = {y in B: y = f(x) for some x in T}.  WE shorthand this by using the same "f" instead of new "g".)
Logged

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2860
    • View Profile
Re: Maths thread.
« Reply #542 on: October 08, 2015, 09:55:46 am »
0

I always have trouble justifying super simple statements like that in the way the teacher wants to see it.  I always want to point at it and say, "yeah, duh."...
Examine left hand side.
Using @ signs when my keyboard doesn't have symbols I used in math class
f(S-T) = f(S) - f(S@INTERSECT@T) - [all f(y) such that x@ISELEMENTOF@S and y@ISELEMENTOF@T, x=/=y, and f(x)=f(y)]

Then you simplify.  The S intersect T part simplifies down to f(T) since if you expand it to subtract stuff that is in T but not in S, the f(s) part won't have any of that ish for you to take away so it's all good.  Actually, maybe you can write it just as f(T) in the first place, but it seems more formal that way.  I'm not sure.

The last part simplifies to the empty set because the existence of any f(y) contradicts that f is injective.


EDIT: geez, it says I got quadruple ninja'ed, I'm not gonna read the better answers and get sad, I'm just gonna post my garbage and run away.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #543 on: October 08, 2015, 09:57:18 am »
+1

Yeah I realize the sets aren't ambiguous. I'm talking about the function. It can mean both a function from A -> B and one from P(A) -> P(B).

PS. Yes, the problem was easy once I figured out the equivocation. I just wish they defined a new function instead of coopting f to be two different functions at the same time.

Well, fair enough, but quite often we abuse notation for convenience.  Using f(A) for a subset A in the domain of f to be the image of A under f is such common (and useful) notation, that it isn't really a problem.  Really, you don't have to think of this "new" f as mapping P(A) to P(B).  It doesn't, it just maps A to B. The notation f(A) does not mean "the function f when you plug in A".  It is simply notation for the particular subset in B that is mapped to by elements of A under f.

There is no ambiguity here because there is not an "f" defined on a domain of subsets of A.  f(A) does not mean anything else that what we've defined it to be here.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #544 on: October 08, 2015, 11:38:01 am »
+2

On the subject of math, math is really hard when you forget to include negative signs at the start.

phi(x) = e^{-x^2}/2,

so clearly

phi((x-u)/a) = e^{(x-u)^2/(2a^2)}

20 lines later, things aren't canceling correctly...
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #545 on: December 04, 2015, 01:23:21 pm »
0

TIL all the binomial coefficients other than (n 0) and (n n) of a prime number are divisible by the prime number, and that this is a sufficient and necessary condition for primality.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

mpsprs

  • Explorer
  • *****
  • Offline Offline
  • Posts: 332
  • Respect: +169
    • View Profile
Re: Maths thread.
« Reply #546 on: December 04, 2015, 01:25:29 pm »
+1

TIL all the binomial coefficients other than (n 0) and (n n) of a prime number are divisible by the prime number, and that this is a sufficient and necessary condition for primality.

And hence (x+y)^p=x^p+y^p  (at least mod p).  If only my calculus students recognized that they should not be working mod 2.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #547 on: December 04, 2015, 05:00:08 pm »
0

TIL all the binomial coefficients other than (n 0) and (n n) of a prime number are divisible by the prime number, and that this is a sufficient and necessary condition for primality.
Hmm, necessity follows from the expression in terms of factorials, but how do you prove sufficiency? I suppose n choose p isn't divisible by n for prime p dividing n?
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #548 on: December 04, 2015, 05:14:26 pm »
0

TIL all the binomial coefficients other than (n 0) and (n n) of a prime number are divisible by the prime number, and that this is a sufficient and necessary condition for primality.
Hmm, necessity follows from the expression in terms of factorials, but how do you prove sufficiency? I suppose n choose p isn't divisible by n for prime p dividing n?

Aren't we saying something different?  That p divides (p k) for all 0 < k < p iff p is prime. 

Edit: Thanks mpsprs.
« Last Edit: December 04, 2015, 05:31:18 pm by Witherweaver »
Logged

mpsprs

  • Explorer
  • *****
  • Offline Offline
  • Posts: 332
  • Respect: +169
    • View Profile
Re: Maths thread.
« Reply #549 on: December 04, 2015, 05:15:49 pm »
0

TIL all the binomial coefficients other than (n 0) and (n n) of a prime number are divisible by the prime number, and that this is a sufficient and necessary condition for primality.
Hmm, necessity follows from the expression in terms of factorials, but how do you prove sufficiency? I suppose n choose p isn't divisible by n for prime p dividing n?

Proof for Liopoil.  (But you should do it yourself.  It's not too bad).
Suppose n=pq and consider (n p)  Then the numerator is p*2p*3p*...*qp*(p-free stuff).  The denominator (p!(n-p)!) is p*p*2p*3p*...*(q-1)p*(p-free stuff).  Everything cancels exactly except qp/p=q.  If p^e exactly divides n (so p^e divides n, but p^(e+1) does not), then p^(e-1) exactly divides (n p), which means p^e and hence n cannot divide (n p).
« Last Edit: December 04, 2015, 05:20:01 pm by mpsprs »
Logged
Pages: 1 ... 20 21 [22] 23 24 ... 47  All
 

Page created in 0.06 seconds with 22 queries.