3 ms·
Probably not formally, but I do tend to find that how much I enjoy a game correlates inversely with how easily I can imagine teaching a computer to play it. Mo
by JoshTriplett 11y ago
Probably not formally, but I do tend to find that how much I enjoy a game correlates inversely with how easily I can imagine teaching a computer to play it. Most of the time, if I start thinking "I could write an algorithm for this game", I very quickly lose interest in playing it.
So, I enjoy games where I feel like I can recognize patterns that have some depth and complexity, that make me feel like I can develop some skill, that don't seem trivially teachable to a computer.
- lostcolony 11y agoThis is why I never enjoyed Sudoku. I finally just spent some time in between classes writing a solver that solved it in as optimal a fashion one can deterministically solve it in, and said "Okay. Done. I will never feel any guilt over dismissing these again". (EDIT: Writing the solver was actually enjoyable though; far more than manually solving a Sudoku ever was)
- philh 11y ago> in as optimal a fashion one can deterministically solve it in I'm curious what you mean by this? Sudoku is mechanically solvable, but not all sudoku puzzles feel that way, to me. Uh, I haven't actually done sudoku in a long time, so let me talk about kakuro (https://en.wikipedia.org/wiki/Kakuro https://en.wikipedia.org/wiki/Kakuro) instead. I think the feelings I have about them are similar. So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column. And getting a computer to implement that sort of algorithm would be challenging. (http://www.sudokuhints.com/ http://www.sudokuhints.com/ seems to do something like it for sudoku, to let it give you a number and tell you how you could have found that number yourself. But trying a fiendish puzzle, it's not explaining itself very well.) (Obviously, if you don't enjoy sudoku, that's fine. I'm not trying to convince you that you should. It just feels to me like the skills I use for sudoku, aren't ones that I could trivially teach to a computer.)
- arohner 11y agoDo you count backtracking as 'mechanical'? This could be relevant to you: http://norvig.com/sudoku.html http://norvig.com/sudoku.html
- philh 11y agoI count backtracking as mechanical; but I was also using it in a perhaps overly-broad sense, which includes that solver.
- JoshTriplett 11y agoSolvers aside, many puzzles like Sudoko require another family of algorithms, to generate puzzles that a human can solve without brute force. Finding the right hints to offer seems rather orthogonal to writing a brute-force solver. > So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column. For Sudoku puzzles generated for humans, the simplest algorithm doesn't require any backtracking or brute force at all: note for every square which numbers can still potentially work there, and at each step, select one of the squares that has only one number, fill in that number, and update all other squares accordingly. Any puzzle that that algorithm can't solve qualifies as "hard". One of the rules I use (in that and similar puzzles) for harder puzzles: if you've determined that a pair of squares can each only have X and Y, or a trio of squares can each only have X, Y, and Z, then you know those squares contain those numbers, just not which square contains which number. So you can (for instance) eliminate X and Y from the possibilities for other squares accordingly, which may then provide more steps. Puzzles where I can recognize and apply higher-level, complex rules like that have more staying power with me. However, it may or may not make sense to teach a computer that special-case rule. A solver may find it easier, rather than recognizing that pattern, to instead just do a search, with transposition tables and similar to avoid duplication. Providing special-case reasoning rules for specific patterns may speed up or slow down such a search, depending on how often the pattern occurs, how much brute-force it eliminates, and how much computation recognizing it requires.
- Frqy3 11y agoBack when Sudoku was a big craze I noticed a relationship between people's approach to it and their chosen career path. Quite a number of engineers I knew had written solvers of various sorts and rarely solved the puzzle by hand, the company accountant wrote little tally numbers in the box corners and worked by a process of elimination, and a lawyer whom I travelled with for many plane flights spent hours on them using some ad-hoc hunt and seek approach.
- cyphax 11y agoOh man, please don't tell me I'm secretly an accountant!
- c3534l 11y agoInterestingly, Sudoku is known to be NP-complete.