| Football Forum View the Forum Registry |
| |
| 0 |
Subject: ATTN: Sludge (Thread rating of 1, please) Posted by: Madman - [44633210] Wed, Sep 27, 14:00 Insomnia has many advantages -- one of which is that new ideas to illustrate old problems can spring to mind out of the blue. You once asked for a demonstration that the algorithm for determining the probability of 10+ wins for any given strategy could be shortened to less than 215*215*15*5. (BTW, that's only a rough approximation for the big-oh of the thing, no? Because you have to add up and multiply out the probability of any one strategy-outcome match occuring to get all the expected probabilities, eh? If you've found a shortcut to do that, then I would be much more sympathetic to your previous arguments). This is a somewhat more advanced permutation on the ideas I had before. Over the course of the afternoon when I can get a chance, I will outline a series of steps to do just that -- shorten the algorithm. I THINK. Here's the outline of what I will do: 1) Introduce a minor tweak to the probability calculation from the one that you gave in the Optimal Pickoff Strategy thread. Namely: Expected bonus points = 50*(Pr(15 correct)+Pr(14 correct)+Pr(13 correct)+Pr(12 correct)+Pr(11 correct)+Pr(10 correct)) I doubt this step will be insightful to you, but I had to work some related issues out to verify my calcs, and this seems like a good place to start. 2) I then have to clarify the method in which you go through the 2^15 strategy possibilities. 3) The part you'll be interested in (and may be obvious after 1) and 2): I'll then outline a demonstration of a basic algoritm change that will eliminate half of one loop of 2^15 you do, and that will shorten all loops from 2^15 to 2^14. Or so I hope. As I said, I'll be in an out all afternoon. So expect a short series of posts here. Before I cleaned up 1), I hoped that my insight would be able to be extended to much bigger cuts. Now, I'm not so sure. But, that's why you have a PhD -- to figure that out for yourself, eh? FYI -- THIS is why I really like fantasy sports. It gives me cool problems to think about. I know, I know. Why waste the energy solving these problems when I have a bunch of REAL problems to solve. I'm not sure I can answer that satisfactorily, but I enjoy it. So, even if this doesn't work, I'm interested in knowing why it doesn't work. Or, if I make a mistake, maybe you can get the concept to work. Because I feel very strongly that there is a way to shorten this thing. And I've been told by people I respect that my intuition is usually fairly solid on this sort of thing. Although I admit that it's wrong all-too-frequently, our intuition is all we have to go with until we see proof one way or the other, eh? (BTW, this idea germinated in about 2 seconds in a semi-wakeful state. It's taken me 45 minutes to write out on paper. And 10 minutes to edit this intro. AARGH. That's why I've got to split this thing up. Sorry.) | ||||||
| 1 | Madman ID: 44633210 Wed, Sep 27, 14:19 |
1) Bonus calculation. (which I just realized I wrote wrong in the intro -- ARGH!) 50*Prob(exactly 10 correct)+100*Prob(exactly 11)+...+300*prob(exactly 15) Note that this specification relies wholly on seeing ALL 15 outcomes. Alternative specification. (all probabilities are exact unless noted otherwise. Eqn numbers to left.) Assume we see games X1,...,X14 and calculate the probability of exactly getting 10, 11,..., 14 games correct given these observations. Further, assume that we add game X15 to the mix (always, Xi = 1 for a win, 0 otherwise). Note that we do not have to recalculate all 215 possibilities to find Pr(10|X1,...,15). (1) Pr(10|X1,...,15)=Pr(9|X1,...,14)*Pr(X15)+Pr(10|X1,...,14)*(1-Pr(X15)) This holds for 11,12,13,14, as well, but I won't write them out. The 15 win possibility is a bit more restrictive: (1') Pr(15|X1,...,15) = Pr(14|X1,...,14)*Pr(X15) But the point here is that we now know there is no THEORETICAL reason why we have to run all 215 combinations, if we store the following variables. Variable list: Pr(9|X1,...,14), ..., Pr(14|X1,...,14) Obviously, I have not yet demonstrated an efficient way of USING this information yet, but that will follow. | |||||
| 2 | Madman ID: 44633210 Wed, Sep 27, 14:35 |
2) We need to figure out an efficient way to use the result from 1. At first I was looking around for ways to STORE a bunch of stuff and LOOKUP probabilities. Instead, I think a simple algorithm change (or, more likely, a clarification) will do. The idea here is that we will take advantage of information that is inherent in the way you generated all 215 strategies/outcomes. Specifically, you likely run a series of loops, generating a set of sequences as follows: 000000000000000 000000000000001 000000000000010 000000000000011 000000000000100 ... Notice that the first 14 elements of the above sequences are always the same for all odd-even pairs (i.e., 1&2, 3&4, etc.). It is important to maintain this regularity. Before I proceed to step 3 (which will make this patently obvious), let me post your algorithm design: For i=1..2^15 For j=1..2^15 Compare strategy[i] with outcome[j] to determine the probability and score. (This consists of another loop with 15 iterations, since you have to go through each game.) End For End For Note that what I am saying here in step 2 is that the method of the For i = 1 ... loop has to be systematic. Step 1) deals with the length of the for j = 1 ... loop. Of course, as it stands at the moment, strategy[i] and outcome[j] would not be comparable if we do this without subsequent changes to the i loop or some other design change. This will be addressed shortly. I'll be back in awhile. Please bear with me. Step 3 will put everything together. Or so I hope. If I'm being excessively slow, I apologize. I'm under the belief that there will be a huge punch line. And, looking at my notes, I'm going to split step 3 into two parts. First, I'll define some notation. And then, what you've been waiting for, I'll sketch the algorithm. | |||||
| 3 | patjams ID: 488362714 Wed, Sep 27, 14:36 | Alright you two knock it off! These boards are supposed to be fun! | |||||
| 4 | Madman ID: 44633210 Wed, Sep 27, 14:38 |
Note: at this point, I think you can probably predict where I'm going with this. In either event, I really will flesh the rest of this out before supper. Looking back on the previous posts, it looks like I have had no insight whatsoever. It's always amazed me how the simple appears so complex until you see that it is simple. And then you say, "so?" I HATE that. | |||||
| 5 | Madman ID: 44633210 Wed, Sep 27, 14:41 |
One last thing: This deals with FOOTBALL PICKOFF and the discussion in the Optimal Roster Thread. Good grief. I can't believe I didn't say that before. NOW, I will do my other stuff and be back in a bit. | |||||
| 6 | D2K ID: 4644639 Wed, Sep 27, 14:45 | I just got a dizzy spell from trying to read this...I think I'm OK now. | |||||
| 7 | louky ID: 8451310 Wed, Sep 27, 14:47 | Where do you click to rate a thread completely over your head? | |||||
| 8 | KevinL ID: 52463114 Wed, Sep 27, 14:58 | Madman, are you trying to say that if there's 15 games, and you calculate the probability of getting 15 correct = P15, then the probability of getting 0 correct (P0) = 1 - P15? | |||||
| 9 | Sludge ID: 1440310 Wed, Sep 27, 15:10 |
Madman - I'll work on digesting this a bit, but there's something that I find discomforting in the above. You discuss probabilities of observing X1+X2+...+X15=A wins given X1, X2, ..., X15. Once you are given X1, X2, ..., X15, it doesn't make sense to make probability statments about functions of your (no longer) random variables! Suppose we have a three game week. I observe that X1=1, X2=0, X3=1. (I.e., they are given.) P(0|X1,X2,X3) = 0 P(1|X1,X2,X3) = 0 P(2|X1,X2,X3) = 1 P(3|X1,X2,X3) = 0 In fact, there are those that would argue that even making the probability statements I just did are nonsense! | |||||
| 10 | Sludge ID: 1440310 Wed, Sep 27, 15:23 |
Just for reference, my program that goes through every possibility (and, actually, stores nothing) takes ~10 minutes on a 14 game week, and ~20 minutes on a 15 game week. This is on a Pentium III 500 MHz Xeon running Linux. (Actually, running Linux as a virtual machine under VMWare. NT drains a bit of the resources it would normally have available.) If any of you are dual-booting Windows * and a *NIX system, then I would recommend you check out VMWare. It allows you to run 'em both at the same time. It's also as stable as a slab of concrete. www.vmware.com | |||||
| 11 | 6-9 With The Afro ID: 2245413 Wed, Sep 27, 15:48 |
I feel dum.
| |||||
| 12 | Madman ID: 44633210 Wed, Sep 27, 16:00 |
KevinL Pr(X15) was meant to be the probability that you win the 15th game. 1-Pr(X15) is the probability that you lose the 15th game. In addition, I talked about the Probabilities of winning a total of 10 games out of a 14 game week, for example, and for that I used the notation: Pr(10|X1,...,14). This was sloppy, and I'll replace it in the future (see below in this post). Clear as mud? Sludge I see your point, and it deals with the notation. I was very misleading. Let me say that at this point I understand your concern, but I'm not doing what you think I'm doing. I needed to distinguish between the case when you have 14 games vs. 15. That's ALL I was trying to do. Here's a novel (sarcasm) idea: Instead of Pr(10|X1,...,14), I'll just use this: Pr(10|g=14) which should be read as: the Probability of getting 10 wins given that you have 14 games. (g=number of games) At any rate, I think when I describe the general algorithm, it will become more clear. Sorry. My lack of a standard stats background is coming out to haunt me, eh? ----------- Regarding the length of your running time, I was under the impression that it took about an hour to run. I see that I mistook the hour long information you gave to be the length of time it took to PROGRAM. Oh well. This is still a theoretical exercise. And I think it could cut down the running time to under a minute or so if my calculations are correct. It depends on how far you want to take it. | |||||
| 13 | Madman ID: 44633210 Wed, Sep 27, 16:18 |
Step 3a) Let me try to define some notation. I just showed everyone how bad I am at this part, but I'll try anyway. sf = individual game choices (f for football). The subscript f refers to which game (1 through 15). 1 = home team, 0 = away team. Si = A Strategy. A Strategy is a set of s's. 15 or fewer. i refers to a number between 1 and 215 to distinguish between all the different possibilities. rf = (potential) result for game f. 1 = home team wins, 0 = away team wins. OUTj = Outcome. OUTj is a set of up to 15 rf's. There are 215 different possible Outcomes, as referenced by j. Pf = Actual probability of the home team winning game f. Pr(OUTj) is the Probability of Outcome J occuring. g = number of games. This will primarily be used to verbally help keep track of what is going on. Pr(W|g, Si) = Any strategy, Si, will have a probability of getting "correct picks". This is the probability that strategy Si has W "correct picks" when you consider g games. A correct pick obviously occurs when sf = rf. I think that is all I need. | |||||
| 14 | Madman ID: 44633210 Wed, Sep 27, 16:27 |
One more definition: A Strategy n-Family is a set of Strategies that share in common the first n elements. I will be looking for Strategy 14-Families. The algorithm can be shortened further by concentration on 13-Families, etc. There is a limit to the gains from this procedure, however, as will become evident, I hope. | |||||
| 15 | Madman ID: 44633210 Wed, Sep 27, 16:50 |
One more comment on Strategy n-Families: 000000000000000 000000000000001 are both in the same Strategy 14-Family (and, incidentally, they are in the same Strategy 13-Family, etc.) 3b) The algorithm with comments denoted by /* and pseudo-code denoted by ". /*stratcount, outcomecount, are just counting variables. For stratcount = 1 to 214 /*find a unique 14-element Si /*stratcount essentially counts the number of Strategy 14-Families, in case you're keeping track. For outcomecount = 1 to 214 /*find all possible 14-element OUTj /*With all those in hand, find the relevant probabilities. Namely: "Find Pr(9|g=14, Si) "Find Pr(10|g=14, Si) ... "Find Pr(14|g=14, Si) next outcomecount These are our "Family Roots" (hahaha). I.e., these are the common elements from which we can subsequently determine all the necessary probabilities for each of the individual Si's in our Strategy 14-Family. /*There are now two out of the 215 15-game strategies that share a common 14-game beginning set of predictions. We're going to evaluate those two strategies, essentially in tandem. /*First, the strategy in the family that ends with a 0. "From the Family Roots, calculate, using the ideas in Step 1, all the probabilites for bonus points -- i.e., Pr(10|g=15,Si), and for W=11, etc. /*note that Si is now the 14 elements from the Strategy 14-Family AND the 15th selection (do this for both cases: s15=0 and 1). /* Because I've tried to clarify the notation, I'll reiterate Step 1 here (ignoring the Si which is in all of the Pr()'s but I'm too lazy to type it): Step 1 noted that) Pr(10|g=15)=Pr(9|g=14)*(1-Pf) + Pr(10|g=14)*Pf /*(Pf is the probability of the HOME team winning, and we chose the visitor first. After you've done this for the Si in which s15=0, then you'll have to do it for s15=1) "Then use these probabilities like you would have otherwise to find the value of the pick. next stratcount | |||||
| 17 | Madman ID: 44633210 Wed, Sep 27, 17:24 |
Notice that in step 1 I used Strategy 14-Families as my building blocks (although I didn't call them that back there). But, there is no reason to stop there. For example, using Strategy 13-Families, you could do the same exercise, but take it a step farther. With Strategy 14-Families, all we needed was: Pr(10|g=15) = Pr(9|g=14)*P15+Pr(10|g=14)*(1-P15) But, notice that you can take a result for Strategy 13-Families to derive your Probabilities for Strategy 14-Families to plug into the overall results. That is, Pr(9|g=14)=Pr(8|g=13)*P14+Pr(9|g=13)*(1-P14). (Note: this is some speculation. I haven't worked it all out. I can think of a couple of potentially different ways of doing this. But all such methods will inherently run into the same or worse combinatorics dilemma the original Sludge algorithm had. The only question is how far can you go before it becomes the inefficiencies outweigh the gains?) More speculation: the most efficient algorithm goes a little way up both exponential "messes" separately. Each of these solution methods gets much worse when you rely SOLELY on one or the other. That's why I'm guessing the optimal Strategy N-Family to use is likely a size 8 or 9 (that would be an interesting problem, but not one I want to tackle at the moment). Bottom Line In practice, just going to a Strategy 14-Family should reduce the number of calculations to about 25-30% of the original algorithm, I figure; maybe less. If you can do the Strategy 13-Family extension, then that could drop to 15%ish. By not having to go through all possible outcomes every time, however, HUGE gains are possible. If you can shoot this down, Sludge, then I yield. This is my best shot at saying that there is a faster algorithm. Finally, notice how I'm doing my "lookup" function. In essence, I'm sorting the strategies. By sorting them first and then calculating a large portion of the probabilities associated with a set of the strategies, I don't actually have to explicitly "lookup" anything -- the information is imbedded in the loop. My thinking in the old thread was that you could run through a bunch of possibilities, and, since there was so much repetitiveness in the outcomes charts, "lookup" the relevant information. Obviously, I think my thinking progressed a lot in those 2 seconds of semi-awakeness this morning. And those 2 seconds of semi-awakeness have made me lose a few hours this afternoon. Aaargh. Ahhh. I'm done. Questions? Comments? Am I full of excrement?? I really am sorry if anyone is P.O.'d but this thread. I figured by rating it low it could perhaps drop off the radar except for interested parties. Consider this another test of the ratings system. | |||||
| 18 | Madman ID: 44633210 Wed, Sep 27, 18:13 |
I know I need to shut up to let what I said soak in and be proven or disproven. But, I'm burning with curiosity at the moment. It seems to me that this concept of an N-Family here could be much more general and powerful than what I've used it for in this relatively small application. In general, when confronted with a huge array of stochastic variables, how should you stratify and categorize differences in the potential realizations of those variables? If you want to shorten computational speed, you could use these N-families to bound subsequent probabilities, and shorten algorithms in much more drastic ways than I did here. (For an example that relates to the this particular algorithm, by checking the conditional probabilities of a given strategy at a 9 N-Family level, you could bound the subsequent expected point level for the strategy and determine whether to go on and generate the 13 N-Family or whatever, get it?) What are the exact relationships between the conditional probabilities of N-Families that are two steps away from another? I keep waffling on that. Not to mention 3 steps apart, etc. Is there N-Family symmetry in some fashion or another? How does all this vary with the construction method for the family? AARGH... Time to eat. Sorry, I WILL shut up now unless you have questions or issues to bring up. Right about now I am wishing I hadn't slept through my probability class as an undergrad. Immaturity sucks!! I have to live with those decisions forever (for the record for you high school types out there, I did do the homework and got a good grade. Everyone should always do that. Just didn't pay that much attention, and tended to strategically miss class.). I'm getting wayyy off the topic at hand. Sorry. That's especially bad form since I'm awaiting confirmation the veracity of the logic. Just getting carried away. | |||||
| 19 | Madman ID: 44633210 Wed, Sep 27, 21:15 |
Wow. Check this out. I did all that work, but here is a method that cuts literally more than 900 million steps out of your original method -- without much trouble (and, this can be used in conjunction with the method described in post 1-18, but, to clarify, I'll describe this as a wholly independent solution). Method #2 Forget the static definition of a strategy as Sludge's algorithm and the outline above suggests. Re-define a strategy as a set of probabilities associated with your team choices. Then, check this algorithm out: create an array with 4944 rows and 16 columns create another array with 5 elements. Call it Prob(). Prob(1) is the probability of 10 ones. Prob(2) will be the probability of 11 ones. etc. for j = 1 to 4944 'There are 4944 unique ways you can get 10-15 "1"'s in a set of things chosen 15 at a time. 'Not sure how to generate that list efficiently. Worst case scenario is that you go through all 215 and just pick out the 4944. No biggie because YOU ONLY HAVE TO DO THIS ONCE!! 'put these possibilities in the first 15 columns of the array I just mentioned 'in the 16th column, put the total number of "1"'s for that row. This is a number between 10 and 15. next j for i = 1 to 215 'run through all the possible combinations of probabilities. 'for each possibility, go through the elements 1-15 as follows: (prob is a variable) 'reset Prob() to zero. let rowprob = 1 for j = 1 to 4944 for k = 1 to 15 if element k in row j of the array = 1 then rowprob = rowprob*s1 else rowprob = rowprob*(1-s1) end if next k if array(j,16) = 10 then prob(1)=prob(1) + rowprob if array(j, 16)= 11 then prob(2)=prob(2) + rowprob ... next j At the end of this loop, voila! You have an array Prob() that has the conditional probabilities of 10,11,12,13,14,15 wins given your strategy i. Calculate it's expected payout. next i It's as simple as that. Note that 4944 < 213 This means that the Big-oh for my algorithm is getting better .... less than 215*213*15 . . . Although the effects of adding up the probabilities of course isn't in that. But that wasn't in the Big-oh you set for your initial algorithm, sludge, so it's hard to compare. And, if you use some matrix multiplication routines, those internal loops can probably be processed faster by creative re-doing the if statement inside that middle loop. Both Methods Combined Finally, note that you don't actually have to go through 215 strategy combinations. Once again, you could use my Strategy N-Family idea (or a derivative thereof) and do the following: Loop i ... 214 Go through the 3473 possibilities for 9 or more "1"'s out of 14 elements. Use the conditional probability formula way back from step 1 to fix up your prob. of 10-15 wins. The big-oh of THAT algorithm HAS to be faster than going brute force. By my rough calcs, it's now LESS THAN 215*212*... (still 215 initially since you have two cases in the 14-Family to consider) or more than 900 million calcs shorter than your original. So I lied. I said that I told you my best shot. I sit corrected. THIS is my best shot. | |||||
| 20 | Madman ID: 44633210 Wed, Sep 27, 21:34 |
Sludge I think I can code this up reasonably quickly in VB and publish an executable. This way you don't have to wade through all the above. The more I think about it, the more I know I can get this thing to fly. It may not be the most user-friendly program, but then YOU could compare the results from your two programs. Are you game? I know, I know. I should just code your algorithm. But, then, why should YOU believe me, eh? This way, we'll have independent corroboration. (caveat on speed: I dunno what you're programming in, but VB is notoriously slow. Surely the last set of algorithm changes would make up for that, but I dunno.) | |||||
| 21 | Sludge ID: 20421222 Wed, Sep 27, 21:39 |
Madman - Maybe I'm dense, but I don't see how it shortens anything. Here's an exact bound on how many operations the program goes through: 2^k*2^k*(3k+2) k = # games For each strategy and each outcome (of which there are 2^(2k)), we have to do 1 multiplication to compute proabilities, 1 addition to update the score, an additional c additions where c is the # of correct picks, 1 addition if you get a bonus, and one addition to update the expected value. Since c is <= k, just assume it is the max of k. If you could write down more in-depth pseudo-code indicating each operation needed, you or I could do the same for yours. (In big-o notation, that'd be k*2^(2k), btw.) | |||||
| 22 | Sludge ID: 20421222 Wed, Sep 27, 21:49 |
Madman - I'm not interested in speed... I'm more interested in number of operations. Program it, we'll get a test data set, and compare answers. I'm 99.9999% confident that my program gives correct answers. We will have to agree on what we consider an "operation". In general, I define it as any addition, subtraction, multiplication, or division. This INCLUDES additions or subtractions updating the counter in a loop IF no operations take place in that loop. This does not include comparisons made, variable initializations (i.e., sum=0), or storage/output of final/preliminary results. | |||||
| 23 | Sludge ID: 20421222 Wed, Sep 27, 21:51 | I'm programming in C on a Linux box. There is none of the overhead that VB would require. It's about as close to optimal speed as you can get short of assembly. | |||||
| 25 | Madman ID: 44633210 Wed, Sep 27, 22:43 |
Sludge -- there are the two algorithm changes above. First, let's ignore the N-Family one, because that's harder to figure out. But the "fixed outcomes" routine in post 19 HAS to be faster than yours. Why? It adds one extra loop of 2^k at the beginning (32K calcs). After that, INSTEAD of going through all 2^k, you only go through 4944. So, you could do your exact same code on that set. Basically, it takes advantage of the insight that 2^k-4944 of the combinations of picks are totally irrelevant to ever getting 10+ wins (IF you set up the problem in the correct way). I'll grant you the other algorithm is harder to evaluate, because there you are indeed adding a set of steps (namely you have to calculate one additional probability. In YOUR routine, when k=15 you had to find 6 probabilities. In mine, you have to find 7). But, once again, I don't see how finding one additional probability, and then adding an extra term to the other probability calculations can even compare to adding 1 to an exponent. | |||||
| 26 | Madman ID: 44633210 Wed, Sep 27, 22:45 |
BTW, there is no way VB is keeping up with any C program under those conditions. Therefore, it will be very hard to evaluate the relative speeds. We can at least compare the answers this way. If the answers are the same, then we can go from there. I'm fairly certain the brute force method is accurate. BTW, if you set X1=P1<>50, does it spit out the optimal solution? That's a no-brainer test, as well. | |||||
| 27 | Texas Flood ID: 12458220 Wed, Sep 27, 23:08 | sludge & madman, are you guys in a tie for first place;)? | |||||
| 28 | Gigantes ID: 3757313 Wed, Sep 27, 23:29 | you gotta be frickin kiddin me....is this a joke, or is it the pocket protector thread??!? You guys stole three minutes outta my life with this cr*p! I kept waiting for the point (or the punchline!!) :) | |||||
| 29 | Sludge ID: 1440310 Thu, Sep 28, 09:21 |
Texas Flood - Don't you think it's a little early to start criticizing? There are still 13 weeks plus playoffs. The only defense I have to all the criticism is that I won last year using the same basic strategy, and you didn't. Neener neener. Gigantes - Nobody was holding a gun to your head when you read it. Therefore, the three minutes you wasted you volunteered. BTW, Madman, what color is your pocket protector? Mine's purple with little Pokemon stickers on it. | |||||
| 30 | Sludge ID: 1440310 Thu, Sep 28, 09:25 |
Madman - It is not difficult to count up the numbers of basic operations performed. That's why I said I don't care about speed. Nobody measures an algorithm's performance based on its speed on a specific machine. All you have to do is add a counter that increments each time one of the basic operations I described above takes place. (And, only count those operations that are necessary to the algorithm. Things such as error-checking don't count.) And, yes, I've tested the program for the situation you described, and it picks all favorites in that case. We can come up with two or three test cases to try them on, no problem. | |||||
| 31 | Sludge ID: 1440310 Thu, Sep 28, 12:03 |
Madman - Finally got a couple of minutes to go through post #19. I don't see anything that is obviously incorrect. I'm ready to compare answers. Get that thing coded, man! | |||||
| 32 | Madman ID: 44633210 Thu, Sep 28, 12:03 |
Sludge I can send you my complete code, and you can probably tell me how to write it better. More importantly, which things to "count" and which things to not "count". Let me define the critical insights intuitively with both of the algorithm shortcuts: a) The original shortcut -- it's much faster to calculate one additional conditional probability and a handful of extra addition/multiplication operations (i.e, around 10) that it is to run through 2^14 extra steps. b) Method 2 -- the only one I implemented in my code -- 2^15-4944 of the outcomes are irrelevant in your j loop. To illustrate method 2 again -- Here's a slight tweak on it. Do your EXACT algorithm. Imagine that for each j in your loop, you were able to know ahead of time whether you actually had to do that j. If you didn't have to do the j, you never brought it up. That's exactly what Method 2 is -- it's just a method of sorting and sifting through the j's to minimize wasted computer time. Run through the 2^15 outcome possibilities BEFORE getting into the evaluation of strategies. From then on out, only look at 4944 of the j possibilities. In fact, the insight in Method 2 is so shocking (to my little mind which is still trying to comprehend the implications) that I'm wondering whether you can actually use both methods at the same time. Essentially, the gains from Method 2 are so strong that all the sudden it becomes at open question about whether it is efficient to calculate an additional conditional probability -- because ever additional conditional probability requires you to retain more outcomes in your j loop AND requires more computations. Therefore, I'll back off on the hy-brid. ------------------------ I need some tests. My algorithm is giving wrong EV's. It gives correct Probabilities for wins, however, so I'm sure the rest of it can be fixed. I think. BTW, it takes under 4 minutes on a 15 game schedule in VB. Unless this blows up considerably with the fix the EV's, I think this dramatic result obviates the necessity of adding in the number of calculations. I can do that if you want, but I really do think this is logically clear. I maybe can't explain it . . . But the truth is independent of the quality of my verbiage. Or so I have been reminded on many an occasion. gigantes Sorry dude. But I TOLD you it was a thread rating of 1!! Texas Flood Not sure exactly what you would be referring to. But I re-iterate what Sludge said. There are no guarantees with any method (other than entering 2^15^17 combinations of picks for the season. And I doubt the guru would appreciate that). | |||||
| 33 | Sludge ID: 1440310 Thu, Sep 28, 12:07 |
Madman - I put my email on this message. Send it to me there. If I get some extra time today (I should... it's my day to spend a couple of hours looking at Fantasy Football stuff), I may even code it in C. | |||||
| 34 | Gigantes ID: 3757313 Thu, Sep 28, 20:00 | Guys, sorry about post #28, that came off as kinda hostile.... I think I was just jealous that I didn't understand nary a word of it!!!! | |||||
| 35 | Sludge ID: 20421222 Thu, Sep 28, 23:11 |
Let me be the first to congratulate Madman on his, dare I say brilliant, solution to the problem. We have hashed it out behind the peering eyes and bright lights of the forum, and he has shown that his algorithm and my brute force (read that as "barbaric") method give the same answers... but his give them in about 1/10th the time using a compiler that is much slower. I bow to his genius. To make it clear to those that have been paying attention, (You there in the corner! Wake up or get out of my classroom!) his observation that made everything possible was that you don't need to examine every possible outcome for every possible strategy, as I had incorrectly asserted previously. You only need to consider those outcomes which correspond to your strategy yielding 10 or more correct picks. It's as simple as that. Clear as mud now? | |||||
| 36 | Sludge ID: 1440310 Fri, Sep 29, 14:18 |
Punchline? You want a punchline? Madman sent me his code last night. This morning, I ported it to C. (It was originally in VB. Yuck. Slow.) Now that I had it in C, I could directly compare times. (Not that there would be any contest, but it'll give you an idea of the improvement in efficiency.) "My" brute force method applied to a 14 game week: 11 minutes, 23.51 seconds. Madman's method applied to the same 14 game week: 0 minutes, 5.38 seconds. Punchline: 127 times faster. *Bowing to Madman* *Bow* *Bow* | |||||
| 37 | Madman ID: 44633210 Sat, Sep 30, 14:05 |
Sludge I was just glad to help. I was obviously intrigued by the problem. And I really should point out how open you have been regarding optimal strategies in this game. You could have sat on your 1999 Championship and not bothered to try to improve the competition this time around. This is my way of saying "Thanks". And, please remember this the next time I say something stupid ;-). | |||||
| 38 | Madman ID: 44633210 Sat, Sep 30, 17:57 |
To everyone else Don't feel bad if my blathering above is not understandable. I really don't think I explained it very well. Sorry. I am frustrated, as well. Don't worry about it. It's always painful to see something clear, cool and simple in your head, but then have it come out convoluted when you try to explain it. Trust me. When I started to write it up, I had no idea it would look this messy. | |||||
| 39 | Sludge ID: 20421222 Sun, Dec 10, 23:25 |
Since it's quite likely I may not get the chance to say this again after this week... Re: #27 sludge & madman, are you guys in a tie for first place;)? Hehehehehehehe... (I've been waiting and hoping to be able to say that.) | |||||
| 40 | Matt S ID: 57543213 Mon, Dec 11, 01:54 |
You just gave yourself the kiss of death. It is good to see somebody de-throne Mallinyourmouse. I'm happy with my performance so far this year. I'm sitting in 12th place as of now (MattS8282) and am aiming for a top 5 finish. Look out boys and girls, I'm coming back! Congrats, Sludge! Matt S | |||||
| 41 | devils1 ID: 107452911 Mon, Dec 11, 10:10 | For what it's worth, I understood less than 10% of what you guys said, but I'm impressed! I'm constantly blown away by the level of intellect on these boards. | |||||
| 42 | Texas Flood ID: 12458220 Mon, Dec 11, 16:18 |
sludge & madman, I was just havin a little fun with you guys:) your discussion was way over my head and i was totally lost. i had forgot all about this thread till i saw it butted back up. hope you don't think poorly of me for my comment no harm intended. by the way how did it work out? | |||||
| 43 | Sludge ID: 20421222 Mon, Dec 11, 19:03 |
TF - I know it's all in jest, as was my newest comment. Reason I made it is because I just moved into first place overall. Just thought I'd take a moment to gloat while I still could. (Meaning that I may not be up there very long... although I certainly hope I am.) Of course, the joke just doesn't seem all that funny anymore. | |||||
| Rate this thread: | If you wish, you may rate this thread on scale of 0-5. Ratings should indicate how valuable or interesting you believe this thread would be to other users of this forum. A '5' means that this thread is a 'must read'. A '1' means that this is a complete waste of time. If you have previously rated this thread, rating it again will delete your previous rating. If you do not want to rate this thread, but want to see how others have rated it, then click the button without entering a rating, or else click here. | ||||||
| |||||||
Post a reply to this message: (But first, how about checking out this sponsor?) | |||||||