|
|
Post by Lars Ericson on Jul 10, 2015 18:50:03 GMT -8
A typical game has 6,670,903,752,021,072,936,959 incorrect solutions. Given the size of the space, it is extremely unlikely that MCTS will happen upon the right solution, i.e the chances are 1/10^21. If you are a clever Irish mathematician, you can get this down to 5,472,730,538 with just the right algorithm. www.technologyreview.com/view/426554/mathematicians-solve-minimum-sudoku-problem/How do we expect a general game player to infer this algorithm? Quantum computer? I know it's in the list because it's fun, but I hope you don't expect players in the qualifiers to do better than not time out. Note, I fixed a timeout problem I was having through the magic of catch/throw, which it's my first time on Java. But there is no factoring or latch/inhibitor or state reduction thing that is going to make my gadget find a Suduko solution. |
|
|
|
Post by Jarrod Torriero on Jul 10, 2015 20:11:43 GMT -8
I know that quite a few general game players can solve Sudokus, usually by using a specialized code path for solving single player puzzles. There are a number of factors that can make Sudoku a LOT easier if the bot can take advantage of them:
1. The effect of a move on the game state is independent of the existing game state (except for terminality calculations). Consequently, any sequence of moves is necessarily equivalent to any other sequence containing only the same moves, regardless of order.
2. Once a square is filled, its value is latched.
3. Whilst it's hard to find a complete solution straight away, (2) makes it so that it's often quite easy to prove that any correct solution must contain a given move M, and given (1), the player can in such cases unconditionally play M straight away, significantly trimming the search space each time it does this.
Etc.
I admit to being unsatisfied with the notion of dropping into different code paths based on hard-coded conditions, but it is certainly far more efficient and easy to code than any more general alternative.
|
|
|
|
Post by alandau on Jul 10, 2015 23:26:58 GMT -8
|
|
|
|
Post by bertrand on Jul 11, 2015 1:53:40 GMT -8
That is one of the main reason why we added Sudoku, on top of the fact that it is a really popular game. We, at Stanford, are not entirely satisfied with what MCTS gives us. It is a very powerful tool, that improved the play level immensely, but we don't think it's the end of all things.
MCTS is not "interested" in the structure of the game, if makes no attempt at "understanding" it. I know I am using terms that are much closer to psychology than computer science, but I want to emphasize how we feel that understanding the game structure (i.e : discovering patterns, eliminating redundancies, optimizing the game tree size, splitting the game in subproblems, etc...) is the crux of GGP.
|
|
|
|
Post by Lars Ericson on Jul 11, 2015 7:02:50 GMT -8
OK, some takeaways:
1. You can do a lot more with single-player games than multi-player games
2. MCTS is probably your play-time fallback, all of this analysis needs to be done in metagame
3. The analysis has to take advantage of restricted structure of GDL (always terminates), so you're not solving the Halting Problem
Still it's kind of magic that you can come up with a solution when it takes some pretty good Irish mathematicians a year to factor the space and count the number of solutions in the factored space.
|
|
|
|
Post by Lars Ericson on Jul 11, 2015 9:11:10 GMT -8
Oh and I guess you can re-do analysis with long play clock to simplify rule set as you go along, by adding the current state as a set of propositions, so yeah so much work to do.
|
|
|
|
Post by Lars Ericson on Jul 11, 2015 9:23:50 GMT -8
Also on the Sancho blog for single-player games: " In Hunter the maximum achievable score is actually 87, though this is not (readily) inferrable from the rules, so although we find a maximum-scoring solution fast, we cannot be sure it is maximal, and so do not cache it".
Why not keep a map of the maps indexed by score and follow the best-scoring path you've found up to that point as you go along?
|
|
|
|
Post by Steve Draper on Jul 11, 2015 9:51:21 GMT -8
Because if you always follow towards the best you've seen so far you may miss the best. Consider a puzzle where a very-easy-to-find solution (say an immediate termination at depth 1 move from the initial state) scores 99. There are 100 score solutions, but they are deep in a complex game tree, which you have not fully solved by the time move 1 has to be submitted. If you submit the move that leads to the subtree with the best score seen so far you will immediately terminate and score 99. Now in such a stark example as I have outlines MCTS would do the same thing, but by manipulating solution density in the gamespace and setting less stark goal values it's easy to generate games where a greedy follow-best-seen would [with a high probability] commit to a sub-optimal route when MCTS would not.
|
|
|
|
Post by Lars Ericson on Jul 11, 2015 17:52:35 GMT -8
|
|
rxe
Junior Member
Posts: 61
|
Post by rxe on Jul 18, 2015 13:35:14 GMT -8
(posting in correct place...) Well, I found that statistical search can solve most of the sudoku games (the easier variations anyway), with the addition of a very simple heuristic. I won't tell you the heuristic but if you stare at this long enough, i am sure it is guessable  (<= terminal (not playable)) |
|
qfwfq
New Member
Posts: 29 
|
Post by qfwfq on Aug 3, 2015 12:06:41 GMT -8
I also use a trivial heuristic that greatly reduces the search space. It's still big enough that qfwfq can only occasionally solve it within the metagame time, though (also because the puzzle solver is single threaded).
|
|
|
|
Post by steadyeddie on Aug 7, 2015 11:58:29 GMT -8
I use regular MCTS rollouts with no understanding to solve suduko. It doesn't work with suduko 3+ (yet- that blasted 1 3 3 1 move if anyone else has solved it like I do), but for 1, 2 and whatever that Suduko 10 was in the champs it works.
As a newbie I'm not sure if sharing is allowed. Does that spoil it for everyone else, or do people not reveal ideas to stay competitive?
|
|
|
|
Post by Jarrod Torriero on Aug 7, 2015 15:05:26 GMT -8
How many rollouts per second do you get in the low Sudoku grades? I'm getting 6348 rollouts per second (from the root) in Sudoku Grade 1, and when I tried having my bot play it with a 45 second play clock it screwed up on its very first move.
(Also, if there's any sort of taboo against sharing, I'm not aware of it - Sancho, for one, is open source)
|
|
|
|
Post by Steve Draper on Aug 8, 2015 5:37:26 GMT -8
You should definitely share as much as possible (IMO). I try to document techniques we use in Sancho on the Sancho blog (when I get time), and the more openly things are shared the faster the field as a whole is likely to progress. Obviously academic papers are already shared (if you know where to look), but there are a lot of 'amateur' efforts now which have resulted in a number of high ranked players, so the more we all can open up the better for everyone. @jarrod - in Sudoku grade IV (which is the first log I randomly laid my hands on) we get approx 39K rollouts/second, but it's almost entirely irrelevant because the move partitioning (see blog article on it at sanchoggp.blogspot.com/2014/08/puzzling-it-out.html) allows us to make quite a restricted search - the log shows it taking 5ms to solve from the start of the search, which implies only a few hundred rollouts. Grade IV might be one of the more constrained ones though (I'm not sure) |
|
|
|
Post by steadyeddie on Aug 8, 2015 13:02:59 GMT -8
OK, then. It's a bit basic. I solve Suduko without partitioning, or any heuristics, by saying that if all my rollouts are scoring nothing, I'll use the rollout depth as the score. That way I'm maximimizing the number of moves I'll stay alive. As it happens that approach solves Sudoku 1 in metagaming, and in Sudoku 2 it manages 8 "good moves" and then spots a solution (as a rollout scores the touchdown). Maybe as my player gets faster it'll get there on Sudoku 3+. Also, unfortunately this approach doesn't work elsewhere as far as I know, so maybe instead I'll need to actually add something cleverer, but not yet.
|
|
