do while !glory
August 14, 2014 5:18 AM Subscribe
Welcome to Al Zimmermann's Programming Contests. You've entered an arena where demented computer programmers compete for glory and for some cool prizes. The current challenge is just about to come to an end, but you can peruse the previous contests and prepare for the new one starting next month.
Glad to see Tomas Rokicki as a frequent competitor. He's been writing neat stuff for years, with an eye for gleeful correctness.
posted by scruss at 7:02 AM on August 14, 2014
posted by scruss at 7:02 AM on August 14, 2014
Scrabble at first seemed strange -- it should be a problemset already solved. I played a two-player version in 95 that had a suggest function, and it would tell you the highest point total you could score given the board and tiles in hand. Once the board was filled out, it took a long time to evaluate, but always gave the right answer.
Thus, seems like this one should be a closed answer, but given the scores shown, perhaps not..
posted by k5.user at 8:04 AM on August 14, 2014
Thus, seems like this one should be a closed answer, but given the scores shown, perhaps not..
posted by k5.user at 8:04 AM on August 14, 2014
Because you know the order the tiles come out of the bag you can set yourself up for bigger plays later; the optimal game is probably not going to be a series of optimal turns.
posted by fleacircus at 9:23 AM on August 14, 2014 [4 favorites]
posted by fleacircus at 9:23 AM on August 14, 2014 [4 favorites]
How cool.
posted by benito.strauss at 9:58 AM on August 14, 2014
posted by benito.strauss at 9:58 AM on August 14, 2014
fleacircus: "Because you know the order the tiles come out of the bag you can set yourself up for bigger plays later; the optimal game is probably not going to be a series of optimal turns."
The class of algorithms that would work using just your current rack of tiles are called greedy. The opportunity to bingo, along with premium squares means you should prioritize the number of long (high score) words rather than the average.
Dynamic programming might be able to help, but it's still a high dimensional sparse matrix, as you're working with the board state just as much as the tiles remaining.
posted by pwnguin at 12:02 PM on August 14, 2014 [1 favorite]
The class of algorithms that would work using just your current rack of tiles are called greedy. The opportunity to bingo, along with premium squares means you should prioritize the number of long (high score) words rather than the average.
Dynamic programming might be able to help, but it's still a high dimensional sparse matrix, as you're working with the board state just as much as the tiles remaining.
posted by pwnguin at 12:02 PM on August 14, 2014 [1 favorite]
It seems like there are two problems. Building an ordered table of high-scoring words from a series of partially- or completely-refilled hands, and placing that series of high-scoring words on the board in an optimal fashion (particularly to take advantage of word multipliers).
The key seems to be picking the right data structures to handle a pool of words that solve the first problem, such that an optimal answer can be calculated for the second problem.
For instance, one would want to prioritize high-scoring words at specific cycles or "waves" in the game (at the start, and then every 3-4 turns, on average, perhaps), because high-value multipliers are spaced in such a way that multiple turns are required to reach them.
Interesting challenge.
posted by Mr. Six at 3:23 PM on August 14, 2014
The key seems to be picking the right data structures to handle a pool of words that solve the first problem, such that an optimal answer can be calculated for the second problem.
For instance, one would want to prioritize high-scoring words at specific cycles or "waves" in the game (at the start, and then every 3-4 turns, on average, perhaps), because high-value multipliers are spaced in such a way that multiple turns are required to reach them.
Interesting challenge.
posted by Mr. Six at 3:23 PM on August 14, 2014
Oh, man, the Scrabble one is an interesting question and I wish I'd seen this sooner because I have a couple ideas but not really enough spare time in the next few days to find out whether (or more likely why) they're wrong.
Certainly like pwnguin notes there's a huge opportunity for bingo-chaining here that doesn't exist in real play; my first blush notion is to search for play orders that involve using bingo plays with low-scoring letters to build toward high-scoring letter plays on the major bonus tiles. Capping/expanding plays off of a high-scoring letter seems like a good tactic as well, so doing some work up front to identify good bingo candidates that can be supplemented by hanging an additional letter of the previous word to re-score the previous points could help.
Come up with a good enough rubric for that sort of thing and you could probably get away with a pretty solid generator of consistently great if not optimal solutions using a much-less-than-exhaustive search of the space.
posted by cortex at 3:46 PM on August 14, 2014
Certainly like pwnguin notes there's a huge opportunity for bingo-chaining here that doesn't exist in real play; my first blush notion is to search for play orders that involve using bingo plays with low-scoring letters to build toward high-scoring letter plays on the major bonus tiles. Capping/expanding plays off of a high-scoring letter seems like a good tactic as well, so doing some work up front to identify good bingo candidates that can be supplemented by hanging an additional letter of the previous word to re-score the previous points could help.
Come up with a good enough rubric for that sort of thing and you could probably get away with a pretty solid generator of consistently great if not optimal solutions using a much-less-than-exhaustive search of the space.
posted by cortex at 3:46 PM on August 14, 2014
Assumptions:
1) The optimal game is definitely not going to be a series of optimal turns. If it was, it would be an easy problem.
2) The problem space is too big to solve by brute-force (ie just check every possible series of moves and choose the highest-scoring one). Otherwise we could just brute-force it and all get the same score.
So, we have to come up with some way of reducing the number of possibilities that we check, but still try to get the highest scores possible. There are heuristics that you can use, like "waves" or "chains" or anything else you can think of, but the problem is that you don't really have any way of knowing if they are helping, and you don't have any way of improving them if they do help. A different approach, which I would like to try given more time (snap, cortex), is to use the Monte Carlo Method. It works like this:
- Given a board in a certain state and a bunch of tiles in your hand, you can easily come up with a list of possible moves and what score they would net you.
- For each of these, play some large number of games right to the end starting with that move, where followup moves are made by choosing randomly from the available options.
- Keep track of the average score you end up with for each starting move.
- The one which leads to the highest average score is the one you choose. Play it, draw tiles, then repeat.
Now, we have a strategy for choosing a move which is likely to lead to a high score, without explicitly encoding any scrabble strategy at all. If we want to converge on higher scores, we play more random games per turn. To do this, benchmark and optimize. This kind of approach is embarrassingly parallel, so run it on your 24-core gamer machine or whatever you have. Oh, and feel free to put in some scrabble strategies if you like, but this might be counterproductive. The idea is that waves and chains still exist, of course, but they will be discovered by chance and used because they score well, not because you decided a priori that they would be good.
I've been itching to try this out since I watched this excellent presentation of Playing Go With Clojure, so even though the competition proper ends in a couple of days I'm happy to notice that the online scorer is going to remain up after the deadline.
posted by mjg123 at 5:58 AM on August 15, 2014
1) The optimal game is definitely not going to be a series of optimal turns. If it was, it would be an easy problem.
2) The problem space is too big to solve by brute-force (ie just check every possible series of moves and choose the highest-scoring one). Otherwise we could just brute-force it and all get the same score.
So, we have to come up with some way of reducing the number of possibilities that we check, but still try to get the highest scores possible. There are heuristics that you can use, like "waves" or "chains" or anything else you can think of, but the problem is that you don't really have any way of knowing if they are helping, and you don't have any way of improving them if they do help. A different approach, which I would like to try given more time (snap, cortex), is to use the Monte Carlo Method. It works like this:
- Given a board in a certain state and a bunch of tiles in your hand, you can easily come up with a list of possible moves and what score they would net you.
- For each of these, play some large number of games right to the end starting with that move, where followup moves are made by choosing randomly from the available options.
- Keep track of the average score you end up with for each starting move.
- The one which leads to the highest average score is the one you choose. Play it, draw tiles, then repeat.
Now, we have a strategy for choosing a move which is likely to lead to a high score, without explicitly encoding any scrabble strategy at all. If we want to converge on higher scores, we play more random games per turn. To do this, benchmark and optimize. This kind of approach is embarrassingly parallel, so run it on your 24-core gamer machine or whatever you have. Oh, and feel free to put in some scrabble strategies if you like, but this might be counterproductive. The idea is that waves and chains still exist, of course, but they will be discovered by chance and used because they score well, not because you decided a priori that they would be good.
I've been itching to try this out since I watched this excellent presentation of Playing Go With Clojure, so even though the competition proper ends in a couple of days I'm happy to notice that the online scorer is going to remain up after the deadline.
posted by mjg123 at 5:58 AM on August 15, 2014
ah, hadn't considered that the best play for any given turn doesn't necessarily mean best game over all.
Now I'm itching to write code for this, too .. I'll be interested in the results (if they share how it was done, I assume pseudo code algorithms would be interesting .. )
posted by k5.user at 8:05 AM on August 15, 2014
Now I'm itching to write code for this, too .. I'll be interested in the results (if they share how it was done, I assume pseudo code algorithms would be interesting .. )
posted by k5.user at 8:05 AM on August 15, 2014
Generally in this kind of problem, repeatedly playing the best move may or may not be optimal. Or, for example in chess it might not be clear how to define what the best-next-move is without the context of the following moves. But specifically for scrabble I expect it would be a particularly bad solution because if you land (eg) Q or a Z in your hand you definitely ought to wait until you can play it on a triple-something.
posted by mjg123 at 8:22 AM on August 15, 2014
posted by mjg123 at 8:22 AM on August 15, 2014
« Older Ruth Crawford Seeger, American composer | The Painted Horses of Sweden Newer »
This thread has been archived and is closed to new comments
posted by brokkr at 6:17 AM on August 14, 2014