The TopCoder Marathon Match that just finished was a poker problem. They defined a very simple game of poker and a probabilistic strategy their server would follow. My task was to write a program that played 10,000 hands of poker against a specific strategy and try to win. The problem description was couched in terms of trying to learn the server's strategy.
My solution observed the play of every hand and built tables which calculated the probability of the other player's actions. Using these probabilities, my program chose actions that maximized expected value at every point. When I tested this approach and allowed it to play millions of hands, this worked great. Unfortunately, 10,000 hands was not enough hands to get good enough information about the other players actions in all situations.
I spent the rest of the match trying to figure out what short cuts I could make. Things like, "well I haven't seen this betting pattern exactly, but I've seen similar actions, so I will use what I saw in the similar (but not exact) situation as a predictor of the computer's strategy." The other thing I did was hard code a couple rules. I noticed that it took a long time for my solution to learn to fold the bad hands. Over the course of 10 million hands it would learn to fold about 30% of them. In the first 10,000 hands it only folded about 1% of them. I've played enough poker to know that not folding enough is the mistake of most weak players. To address this, I just hard coded the program to fold the weak hands.
This combination of strategies were enough to let me finish in around 60th place. Since the top 200 advance this round, this is good enough.
So what does this have to do with ruts? Well it turns out that a number of the people who did better than me did not create learning strategies. Instead of trying to figure out how to observe and adapt appropriately, they spent their time coming up with an algorithm that would be good against all strategies. Some of them were able to come up with some very simple strategies which were, nevertheless, able to do better, on average, than my more complicated learning strategy. If we played millions of hands rather than 10,000, mine would almost definitely be better, but that wasn't the problem we had to solve.
I got stuck in the rut of figuring out a learning algorithm, I just never realized it. While it occurred to me to figure out a good fixed strategy, I only thought of that in the context of what my learning program should do until it learned the opponent. Since this felt like just a tweak to my approach, I never got around to doing it.
Moral of the story: sometimes it can be a good idea to try different ideas even if you don't realize you are in a rut.
Friday, March 30, 2007
Monday, March 26, 2007
Don't Get Stuck in a Rut
I was solving a practice TopCoder problem the other day, and was having difficulty. First the problem:
Imagine you are multiplying to positive integers A and B (A >= B) using long multiplication with no carry. For example if A = 89 and B = 76:
The input to your program would be the array {56, 111, 54}. You have to return A, in this case 89. If there are multiple A's that satisfy the input, you have to return the one that minimizes A-B. To make sure the problem is feasable they constrain it by saying that the result of A*B < 1014.
I decided to approach the problem by noticing that the the most significant digit (MSD) of the answer was equal to the MSD of A times the MSD of B. I would try each combination of digits that makes this work, and then move on to the next digit. I also noticed that the number of digits in the answer equals the number of digits of A + number of digits of B - 1. So I tried every combination of lengths of A and B that satisfied these constraints, when picking digits. I then returned the one that worked that satisfied the tie breaking condition (i.e. smallest A that is >= B).
This passed all the examples provided, so I submitted it. Unfortunately it timed out on some of the system tests. Since this was a practice, I had access to the system test and copied it locally. I ran this test locally and let it run for a couple hours. When I came back it still hadn't finished. Given that the program has to solve the problem in less than 2 seconds, this was a wee bit too slow.
I finally gave upI looked at my code and found some obvious optimizations. This improved runtime from hours to 10's of seconds. Better, but still too slow. I worked at it a while longer, but just couldn't figure out how to improve my code enough to get it to run fast enough. So I finally gave up and read TopCoder's solution to the problem.
Their solution - just try every value from 1 to sqrt(N) for B. Set A to be N / B. Check if it satisfies the constraints. You can check 107 choices for B in under 2 seconds, and their bounds guarantee that B won't be larger than that.
This solution is much easier to comprehend and code up than what I came up with. Yet, I didn't see it. I was stuck in a rut. This comes up repeatedly when trying to solve a problem, whether it is a small contrived problem like TopCoder or much larger "real-world" problems. Once you see an approach that looks like it might work, it can blind you to other approaches which might be better. This is really just another example of "Don't Want That", where what you need to stop wanting is your current approach.
How do you get out of this rut? The first thing that has to happen is that you have to notice you are in a rut and be open to the idea that other solutions may exist. Given this, how do you find these other solutions? One of my favorite ways is to present the problem I have to someone else without telling them my current approach. A fresh mind often comes up with a fresh solution. What if you don't have someone to discuss it with or, as in a competition, you can't discuss it with people? Then you have to try and clear your mind of everything you know. Start at the problem from scratch, considering every salient fact, paying particular attention to any that your previous approach ignored. Try to come up with the most off the wall things you can think of and pay attention to the reasons they don't work. If you have the luxury of time, put the problem down and don't think about it for a while.
Unfortunately, sometimes it is hard to describe a problem to a fresh person without sullying it by hinting at our own approach. And I often find that no matter how hard I try to come at a problem from a new angle, my mind just slips back into the old rut. So how do you get unstuck from a rut?
Imagine you are multiplying to positive integers A and B (A >= B) using long multiplication with no carry. For example if A = 89 and B = 76:
8 9
x 7 6
------------
48 54
+ 56 63
-------------
56 111 54
The input to your program would be the array {56, 111, 54}. You have to return A, in this case 89. If there are multiple A's that satisfy the input, you have to return the one that minimizes A-B. To make sure the problem is feasable they constrain it by saying that the result of A*B < 1014.
I decided to approach the problem by noticing that the the most significant digit (MSD) of the answer was equal to the MSD of A times the MSD of B. I would try each combination of digits that makes this work, and then move on to the next digit. I also noticed that the number of digits in the answer equals the number of digits of A + number of digits of B - 1. So I tried every combination of lengths of A and B that satisfied these constraints, when picking digits. I then returned the one that worked that satisfied the tie breaking condition (i.e. smallest A that is >= B).
This passed all the examples provided, so I submitted it. Unfortunately it timed out on some of the system tests. Since this was a practice, I had access to the system test and copied it locally. I ran this test locally and let it run for a couple hours. When I came back it still hadn't finished. Given that the program has to solve the problem in less than 2 seconds, this was a wee bit too slow.
I finally gave upI looked at my code and found some obvious optimizations. This improved runtime from hours to 10's of seconds. Better, but still too slow. I worked at it a while longer, but just couldn't figure out how to improve my code enough to get it to run fast enough. So I finally gave up and read TopCoder's solution to the problem.
Their solution - just try every value from 1 to sqrt(N) for B. Set A to be N / B. Check if it satisfies the constraints. You can check 107 choices for B in under 2 seconds, and their bounds guarantee that B won't be larger than that.
This solution is much easier to comprehend and code up than what I came up with. Yet, I didn't see it. I was stuck in a rut. This comes up repeatedly when trying to solve a problem, whether it is a small contrived problem like TopCoder or much larger "real-world" problems. Once you see an approach that looks like it might work, it can blind you to other approaches which might be better. This is really just another example of "Don't Want That", where what you need to stop wanting is your current approach.
How do you get out of this rut? The first thing that has to happen is that you have to notice you are in a rut and be open to the idea that other solutions may exist. Given this, how do you find these other solutions? One of my favorite ways is to present the problem I have to someone else without telling them my current approach. A fresh mind often comes up with a fresh solution. What if you don't have someone to discuss it with or, as in a competition, you can't discuss it with people? Then you have to try and clear your mind of everything you know. Start at the problem from scratch, considering every salient fact, paying particular attention to any that your previous approach ignored. Try to come up with the most off the wall things you can think of and pay attention to the reasons they don't work. If you have the luxury of time, put the problem down and don't think about it for a while.
Unfortunately, sometimes it is hard to describe a problem to a fresh person without sullying it by hinting at our own approach. And I often find that no matter how hard I try to come at a problem from a new angle, my mind just slips back into the old rut. So how do you get unstuck from a rut?
Monday, March 19, 2007
This time it was good enough
My submission that I talked about last week would've placed around 230th place. (top 500 advance). I didn't let it be though. I worked on it further, and ended up finishing right around 100th place. The official results aren't finalized yet, so I don't know my exact place.
So was the effort I put in to raise my result worth it, given that I would've advanced either way? Can I consider it good practice for the next round (which starts Wednesday) where only the top 200 advance?
As you might've figured by these last two posts, I am in TopCoder mode at the moment. This seems to happen once or twice a year during tournament time, so you'll have to bear with me. I am justifying it by saying it fits with the theme of my blog because these are programming contests.
So was the effort I put in to raise my result worth it, given that I would've advanced either way? Can I consider it good practice for the next round (which starts Wednesday) where only the top 200 advance?
As you might've figured by these last two posts, I am in TopCoder mode at the moment. This seems to happen once or twice a year during tournament time, so you'll have to bear with me. I am justifying it by saying it fits with the theme of my blog because these are programming contests.
Monday, March 12, 2007
Is It Good Enough?
This week the first round of the Marathon Match for the TCO '07 started. In a "marathon match" they give you a problem and you have a week to come up with the best solution you can. It's usually fairly easy to come up with a working solution, the trick is to come up with a good one. Unlike the TopCoder algorithm matches, there isn't a right answer, rather your program is judged based on the quality of answer it provides. For example, if you were trying to solve the travelling salesman problem, you might be judged based on the total distance your route takes.
I don't need the best programMy dilemma is how much time to spend on this problem. I love these sorts of contests but this week - Wednesday through Wednesday in this case - is fairly busy for me and I don't have a lot of spare time. In this first round 500 people advance to the next round. So I don't need the best program, I just have to be good enough. I've spent a couple hours coming up with and coding a solution and as of the time of this writing, I am in 132nd place. Is this good enough? Will 369 people come up with better solutions than mine in the next 2.5 days? I don't know.
There is something satisfying about the TopCoder algorithm matches where you program has to pass every single input exactly or else you get no credit. It is similar to many school homework assignments where you have well defined requirements to solve. In these cases it is much easier to know when you are done. If it satisfies the requirements, it is done. Unfortunately, in the real world, problems are more like the marathon match problems. Programs aren't right or wrong, rather they are better or worse. You can always improve things if you spend more time.
So how do you know when to release your code? Does your software escape leaving a bloody trail of designers and quality assurance people in its wake? Perhaps it is never finished - it simply stops in interesting places.
Given that there are always other projects to work on, I think this is a very important question to answer, whether at the class level, the component level, or the entire project level. The ability to know what is good enough is one of the differences between companies, teams, and individuals that succeed and those that don't.
I don't need the best programMy dilemma is how much time to spend on this problem. I love these sorts of contests but this week - Wednesday through Wednesday in this case - is fairly busy for me and I don't have a lot of spare time. In this first round 500 people advance to the next round. So I don't need the best program, I just have to be good enough. I've spent a couple hours coming up with and coding a solution and as of the time of this writing, I am in 132nd place. Is this good enough? Will 369 people come up with better solutions than mine in the next 2.5 days? I don't know.
There is something satisfying about the TopCoder algorithm matches where you program has to pass every single input exactly or else you get no credit. It is similar to many school homework assignments where you have well defined requirements to solve. In these cases it is much easier to know when you are done. If it satisfies the requirements, it is done. Unfortunately, in the real world, problems are more like the marathon match problems. Programs aren't right or wrong, rather they are better or worse. You can always improve things if you spend more time.
So how do you know when to release your code? Does your software escape leaving a bloody trail of designers and quality assurance people in its wake? Perhaps it is never finished - it simply stops in interesting places.
Given that there are always other projects to work on, I think this is a very important question to answer, whether at the class level, the component level, or the entire project level. The ability to know what is good enough is one of the differences between companies, teams, and individuals that succeed and those that don't.
Sunday, March 4, 2007
Will I be the next ex-blogger?
Shortly after I started this blog, UserFriendly - a comic I read - had this thread on blogging. I didn't know if I should take it as an omen or not. I decided to be positive and continue with the blog. Now, two weeks in a row, I find that I haven't found the time to write the week's post. Rather than haphazardly dash something off now, I will just settle for this apology, and hope the link to a tech related comic strip amuses some of you.
Subscribe to:
Posts (Atom)