October 31st, 2010
|12:54 am - Puzzling times|
I'm getting back into puzzles at the moment - specifically, culture-neutral, language-free logic puzzles, like sudoku and the sorts of puzzles you see published next to them. In my mind, the world of logic puzzles has advanced far enough recently that it has come of age and become a mass participation competitive mind sport.
A traditional criticism of the logic puzzle mind sport is that it has been so strongly focused around a single event, the annual World Puzzle Championships. It made for a very short puzzle season: either you qualified for the World Puzzle Championship or you didn't, and if you didn't then that was that for the year. If you were lucky enough to qualify - and while solving the puzzles is a matter of skill, being born in a country from which the competition was such that you could qualify is a matter of luck for all but the very finest - then your season would only be one contest longer. Recent developments have meant that there is a meaningful collection of competitions year-round for solvers of all standards... including the fifth to eighth best solvers in the US, who traditionally found it very difficult to find their place to shine.
I'm also drawing a distinction between the existence of puzzles to solve and the existence of puzzle competitions to solve. There have long been several sites with lots of logic problems to solve, but solving puzzles as a solo activity is somehow a little tame. I take the viewpoint that solving puzzles against the clock with your performance "under exam conditions" being compared against that of others is rather more sporting, somehow, than that of solving puzzles alone. This is contentious, of course; even restricting yourself to logic puzzles within the world of puzzles at large, there's a clear sporting element to the concept of "Who can solve the hardest puzzle?". I'm glad that there are different sporting approaches that can be taken.
There have long been several web sites with plenty of puzzles to solve; some give you puzzles to print out and solve with pencil on paper, others have applets to let you solve online. Preferences may vary, but I find the latter more convenient, not least because I still haven't got my printer set up since we moved house. Quite often these sites are not in English, or are bilingual with English as a minority option, but this isn't an issue; a logic puzzle is solved the same way in any language... though finding the instructions and learning what you have to do to solve the puzzle in the first place can be tricky! There's also an issue that some puzzles have several different names; some names can be quite similar to each other, with some puzzles being fairly slight (but fairly crucial) variants of each other. The name given in the original language of publication is often considered definitive; Japanese puzzles are often referred to by romanised transliterations.
Possibly the most famous such online solution logic puzzle site is the Janko family's puzzle collection; click on a puzzle type and you'll get to solve dozens or hundreds of puzzles of that type. The "Sortiert nach Größe" section translates to "sorted by size"; the "Sortiert nach Schwierigkeitsgrad" section translates to "sorted by difficulty". At least, I think it does; my grasp of German is extremely fragmentary and based on board games. I translate as "leicht" as "easy" and "schwer" as "difficult", so you can find the easiest puzzles of each type, start with them and work up to trickier examples.
A similar site is this collection by Seth Weiss, a member of the mathematical faculty of Lincoln Sudbury Regional High School of Massachusetts. It does feature some puzzle styles not found elsewhere; some of the applets are more immediately accessible than those for the same puzzles elsewhere, others aren't. (Your taste may vary.) In any case, it's a labour of love. Similarly, PuzzlePicnic, where I particularly recommend the Tapa applets. Many of the puzzles were originated by the Japanese puzzle publishing house Nikoli, who have an English-language site where many of the top solvers practice; from Britain, Dr. Gareth Moore promotes PuzzleMix and Sudoku Xtra online magazine, and WPC-style Puzzles has a particularly wide selection of puzzle types, mostly for printing rather than online solution. (All these links come from the UK Puzzle Association's Puzzle Links forum, which has at least half a dozen another pointers.)
If those are the practice sites, where are the competition sites? I've posted more than once about Logic Masters India, which hosts a variety of puzzle contests (usually available to the world at large!) in similar styles to that of the US Puzzle Championship, which is still used as the UK qualifier for the World Puzzle Championship. The form is that .pdf files containing puzzles are uploaded; solvers download the files and have a certain time limit to submit their answers through a web interface. The contests are devised by people around the world; for instance, motris submitted a test a fortnight ago which was extremely well-received by those who took part.
Some contests (the most serious, such as selection tests) insist on solvers participating at exactly the same time; many others permit solvers a particular time limit but quite a wide window in which each solver can choose to start the contest at a time to suit themselves. This does open a possibility of cheating by downloading the .pdf file using one account, solving the puzzles offline and then submitting the solution using another account. On the other hand, even simultaneous solution contests cannot stop one account representing answers from more than one solver, or one solver and a computer. This has so far proved a theoretical rather than a practical concern, though it's relevant that most of the most serious competitions shy away from exactly using established puzzle formats, where automated solving software may well already exist; most serious competitions use puzzle variants, often ones not seen before, to minimise the chance of this. Writing a program to solve a problem is as good a solution technique as any, though often a very slow one and ineffective against the clock.
However, even Logic Masters India does not offer puzzle contests each day; one site that does is croco-puzzle, a German-language site with puzzles and puzzle contests to solve online. Most of these are free, but an online shop sells puzzle collections as well. (There's a weekly contest where the prize is credit for the online shop.) Of most interest to me is the Überraschungsrätsel, or "surprise puzzle"; this is a daily timed contest, one puzzle long. Every day there's a new puzzle, so far in one of 29 types. Every participant who opts in has their performance on each puzzle timed; the times are published, to provide a daily high-score table, and a rating scheme attempts to assess who has been the most successful solver overall. I've really got into this over the last five or six weeks.
The croco-puzzle Überraschungsrätsel meta-game isn't for everyone, but I think the people who like it will really like it. Of course, you've got to be a fan of culture-free logic puzzles. You don't need to be familiar with all the 29 types of puzzle; I've solved 11 types of puzzle so far, of which 8 I have had to learn just for this site. (And enjoyed doing so.) You do have to be prepared to cope with the language barrier; I have been making fairly heavy use of Google Translate, but other online translation engines are available. To me, dealing with the language barrier is as much part of the fun of working out what I have to do as learning how to solve new types of puzzles.
There's an admirably low level of commitment required; you don't need to solve a puzzle every day, and indeed I've only done so about half the days. The time commitment required to solve the daily puzzle is harder to measure - you don't know how long it will take to solve a puzzle until you've solved it - but at least you can find out how long it has taken other solvers to crack the day's puzzle, and what sort of puzzle it is, before you decide whether to try it or not on any particular day. Sometimes you get a clear picture that you ought to be able to solve a puzzle in 2-3 minutes, or maybe less, which is probably a clear go-ahead; other days you see that the day's puzzle is taking even the best solvers in the world 15 minutes or more, which is probably a clear indication to give it a miss. There is no compulsory social aspect to it; it's a massively parallel one-player game.
It's the rating system that really makes the site for me, though. Your solution to each Überraschungsrätsel puzzle is timed, and your time for each puzzle is converted into a rating for the puzzle. The fastest solution to a puzzle is rated a perfect 3000, the median solution (i.e., half the solutions are faster, half the solutions are slower) is rated 1500, all solutions where the correct answer is never reached are rated 0 and all other solutions are rated between 3000 and 0 depending on how quick they were. If you attempt to submit an incorrect solution, your error is pointed out but you suffer a five-minute time penalty - which can turn a competitive two-minute solution into a seven-minute solution that's well behind the times. Multiple incorrect solution attempts attract multiple time penalties.
Getting technical, the gap between the best time and the median time is used as a measure of spread. The median time is one multiple of this gap away from the fastest time, and so is rated 1500, or 3000 halved once. A performance that is two multiples of this gap away from the fastest time, or one multiple of this gap below the median time, is rated 750, or 3000 halved twice. A performance that is three multiples of this gap away from the fastest time, or two multiples of this gap below the median time, is rated 375, or 3000 halved three times, and so on. A really slow performance might be ten multiples of this gap away from the fastest time and thus is rated 3000 halved ten times, which is just under 3, but any correct solution will be rated above zero, even if not very much.
Each solver is then given an overall rating based on the ratings they have earned for their puzzle solutions; specifically, their overall rating is (59/60 of the overall rating from the previous day) plus (1/60 of their rating for that day's puzzle). Accordingly, the puzzle solution is an approximation to a time-weighted average of the ratings of their puzzle performances, with recent performances weighted more heavily. Your overall rating does not change on a day in which you do not attempt to solve a puzzle, though attempting to solve a puzzle and never eventually submitting a correct answer - how many tries it takes you - is treated as a solution with a rating of zero, so your overall rating drops to 59/60 of what it was plus 1/60 of zero.
It's not a tremendously quick-moving average; if your overall rating was zero - which it is, to begin with - and you get a 3000-rated (i.e. fastest) solution to your first puzzle, your overall rating only goes up by 1/60 of 3000, or 50. However, keep solving puzzles with a 3000 rating and eventually your overall rating will get as close as you like to 3000. This doesn't happen very quickly; I think it takes something like 137 consecutive 3000-rated solutions to get your overall rating up to 90% of 3000, and 275 consecutive solutions to get your overall rating up to 99% of 3000. By extension: whatever the true calibre of your performances, it'll take a good hundred or two hundred solutions before your overall rating "catches up with" the level at which you are performing.
Conversely, if someone has established a high overall rating, they need to keep solving puzzles prodigiously successfully in order to maintain their rating; someone with a 2700 rating who only earns a 1500 performance, and even that is not so much disastrous as merely "no better the median", on one particular day "loses 45 and gains 25" for a net -20, but another 3000 performance will only gain +5. Solvers with high ratings stand to lose points quickly and gain points slowly; solvers with low ratings stand to lose points slowly and gain points quickly. Thus maintaining a high rating over time is very difficult and well worthy of respect. (It's theoretically possible that people might be cheating by finding out the daily puzzle using one account, solving it offline and then solving it "for real", taking as short a time as they would like, using their other account. This may well be prohibited technically somehow; there's no evidence to suggest it happens.)
The really attractive part is that this rating system has been mashed up with a "title" system borrowed from, or at least heavily inspired by, that of the European Go Federation. As well as your overall rating representing a time-weighted average of your individual solutions' ratings, a "red line average" (my term) is computed, a rolling arithmetic mean of your last two hundred distinct ratings. To begin with, you start with two hundred zero ratings being considered in the red line average, and the average rating moves relatively slowly at the best of times, so the red line average is a really slow mover; solving your first six puzzles with 3000-rated performances, an extremely improbable feat, will raise your overall rating to 50, 99, 147, 195, 242 and 287 respectively, with your red line average rising to 0, 0, 1, 2, 3 and 5. And that's if you can consistently solve puzzles more quickly than the whole of the rest of the world!
This red line average is tracked for everyone, and when the red line crosses 100 you are awarded a "20th kyu" title. (This is a slow, slow process, requiring 31 consecutive 3000-rated performances, 45 consecutive 1500-rated performances, 67 consecutive 750-rated performances, 102 consecutive 375-rated performances... that sort of thing. In short, it requires both skill and considerable dedication.) A red line crossing 200 earns a "19th kyu" title, and so forth. By extension, a red line crossing 2000 earns "1st kyu", then 2100 is required for "1st dan", 2200 for "2nd dan" and so on up to 2900 for "9th dan". Given what we said about how easy it is for your overall rating to drop from a high level, it should be clear how significant an accomplishment these high dan titles are. Titles are awarded for life; it is possible for a red line to drop back below one of these hundred marks, but the awarded titles are not rescinded.
With all this in mind, the rating table makes interesting reading. The top-rated solver is uvo, awarded the 7th dan title, and with a current rating of 2774. However, that 2774 is after a drop of 27 arising from an extremely rare poor puzzle; an example of a failed submission turning an extremely competitive two-minute puzzle into a seven-minute one that'll cause a rating drop that may take two or three weeks to recover. This solver is Ulrich Voigt, who has won the World Puzzle Championship seven times. :-) Clicking on the link containing his name will show a rating graph of his performances; you can see that he recently received a ridiculously high rating of 2804, and that his red line has been wobbling above 2700 for over six months. Considering how difficult touching 2800 is, getting 8th dan would require an overall rating hanging above 2800 for a long time, which seems exceptionally unlikely.
Some other names to look out for near the top of the ratings table: second-placed flooser is Florian Kirch, who finished tenth in the 2009 World Puzzle Championships, third-placed pwahs is Philipp Weiß, who finished eighth in the 2009 WPC, and fourth-placed Hausigel is Ulrich Voigt's brother Roland, who finished second in the world (ahead of his brother in third!) in 2002. Gulp! Another solver to look out for is misko, currently ranked thirtieth, but as you'll see from the far left column, he has solved far fewer puzzles than the others and so his overall rating is still rising to reflect his performance. His 12th-kyu title shows his red line has well over a thousand points to go to catch up with his overall rating; he has several 3000-rated solvers to his credit already. misko is the solving name of Michael Ley, a fifteen-time WPC participant who has finished fourth four times. You really are competing against the best solvers in Germany at croco-puzzle, among the very best solvers in the world.
And yet you don't need to be a great solver to enjoy croco-puzzle; I'm down at 450th place in the world with an overall rating of 127, having solved 18 puzzles to date. I've enjoyed each one, many of which involved learning how to solve a relatively quick example of a type of puzzle that was new to me and having an interesting reason to do so. Most of the solutions have seen my rating creep up and I have clawed my way past the lower reaches of the rating table, though four times I've worked my way to a correct solution so slowly that I've ended up losing a point or two on the deal. It really is a low commitment - most days I've looked at the type of the day's puzzle, or how long it's taken the best solvers, and thought I didn't fancy it - but if you can pick your battles (today's Killer Sudoku looks likely to take far longer than I would ever want to spend) then it's a lot of fun even at my relatively low level of achievement. Puzzle fans should seriously consider whether they'd enjoy giving it a go, and I'd love to see more people I know taking part.
In other puzzle news, the 19th World Puzzle Championships took place in Poland last week, one of the very largest to date; their web site has all the information. Ulrich Voigt won the two and a half days of puzzles that make up the body of qualifying, and also won the semi-final, but he faced three of the four members of the Japanese team in the final and Taro Arimatsu squeezed him out for his first world title, following on from two fifth places and a seventh place in three previous tries over the last eight years. The US snatched the team championship from Japan. The UK sent a strong team but couldn't really find their feet and finished 22nd of 26.
Unrelatedly, the clocks go back in an hour or two's time in much of Europe, but they don't go back in the US for another week. Accordingly, for the next week, the difference between US and European time may be an hour less than you expect. Be warned!
Please redirect any comments here, using OpenID or (identified, ideally) anonymous posting; there are comments to the post already. Thank you!
Current Mood: Don't talk to me about Florida