3 ms·

Bear with me, this won't seem immediately relevant, but I'll get to the point. I have at various times created solvers and helpers for the sorts of logic puzzl

by drostie 14y ago

Bear with me, this won't seem immediately relevant, but I'll get to the point. I have at various times created solvers and helpers for the sorts of logic puzzles you sometimes see in newspapers alongside the crosswords -- you can find a bunch of them online and with many of them, the limiting problem is simply time investment for applying automatic, pithy little rules. Just as an example, I wrote a helper script in Greasemonkey at one point for large versions of http://www.puzzle-loop.com/ http://www.puzzle-loop.com/ , the rules of which are "You have to draw lines between the dots to form a single loop without crossings or branches. The numbers indicate how many lines surround it." It's very satisfying to click once and then see an algorithm performing all of the drudge-work, leaving you to focus on the really interesting bits which you haven't yet been able to articulate as rules. One interesting problem in the above link is knowing when you're about to create a region which only has an odd number of ends inside of it. I found a very pretty way to do this in most cases. The central problem of the translation computer is that often, knowing which translation of word W is important depends on understanding the context around W, sometimes out a couple of sentences. The central problem of understanding the context of W, however, would demand a much more holistic approach than the above translation program seems to provide. The problem in both is precisely a declarative/imperative divide. We are very good at working out, given the adequacy conditions for the solution (the "rules of the game"), what sorts of automatic reflex actions we can do (the "moves" of the game, I suppose). We know the rules, we figure out the moves. Ideally, we would like to just tell a computer the rules of chess without specifying that there is something called 'value' of a piece, and that the computer should find values for e.g. the loss of a knight in comparison to the loss of a bishop. It should be able to work out the principles of effective play, if we want true machine learning. It is my contention, to tie this all together, that without something which appears like machine learning, we won't have anything which appears like machine understanding, and that a machine translation would appear like a machine understanding, due to context-sensitivity in translation: you will hand it "Knives were good for helping humans to hunt" and it will accidentally translate "good" as the equivalent for "ethical" rather than the more-likely-intended "efficient", because it correlates "helping" and "humans" with ethics.

Retric 14y ago
There are programs that given enough time will come up with piece values for arbitrary board games like chess. Non random board games are actually one of the easier things to translate into computer code, the problem is games like go are inherently difficult. I suspect with perfect play the first go player completely dominates the board just like with smaller boards that have been solved, but the ultra aggressive gameplay required to pull this off is impossible to pull off with any sort of reasonable hardware. So, it's really a question of discovering heuristics that allow computationally reasonable pay to still create an acceptable level of imperfect play, and piece values are just one of those heuristics. Perfect play in chess can ignore positional concepts and just look for paths that either force a checkmate or a tie. The problem with language translation is you need to understand the context of an idea before you can accurately translate it which is why humans have such issues translating technical content they don't understand. That said, humans can decode things that are close to linguistic gibberish so even a poor translation is often good enough. Google translate is already rather useful though a great set of heuristics despite an endless array of edge cases it fumbles though. It's a useful path that get's ever more expensive the more demanding the problem.
- mgkimsal 14y ago
  "There are programs that given enough time will come up with piece values for arbitrary board games like chess. " Would different instances of those programs potentially develop different 'values' for the pieces based on their own history and experience of playing? There are some humans that 'prefer' (emotionally) knights over bishops, and will sacrifice one before the other all the time, even when they don't win. Part of that may be that they just don't play enough to develop better strategies, and part of it may just be human attachment to ideas vs 'facts'. I'm no chess master, and I'm not saying knights are better or worse than bishops :)
- drostie 14y ago
  I guess maybe I wasn't clear. Some modern chess algorithms begin by telling the computer, "here are some numbers you must determine, and how you combine them into an assessment of the game's winnability. Go and analyze a bunch of games and statistically determine which numbers are optimal." To me, that phrasing is itself the problem. I should be able to just say "here are the adequacy conditions for a solution" and then have my computer humming away to guess and then prove possible moves which tend to quickly bring you towards a solution. Mind you, they don't have to be complete rules that solve every case -- that would probably end up implying that P = NP. But most of my logic-puzzle-helpers begin with some sort of code which says, "here is how I will define rules, here is how you should match against them and what you should do when you find a match." Then I have to work out all of these rules for myself and then tell the computer about them one-by-one. If I could just tell my computer, "work out all of the automatic reductions where the logic tree goes less than 20 steps, build rules for those, I will try to handle anything more sophisticated," that would be much better. As yet I've never seen anything like a general algorithm for this, though. :< Turning the declarative to imperative in a portable way would simplify both these programs that I'm writing, and machine translations, I feel.

by drostie 14y ago

Retric 14y ago

There are programs that given enough time will come up with piece values for arbitrary board games like chess. Non random board games are actually one of the easier things to translate into computer code, the problem is games like go are inherently difficult. I suspect with perfect play the first go player completely dominates the board just like with smaller boards that have been solved, but the ultra aggressive gameplay required to pull this off is impossible to pull off with any sort of reasonable hardware. So, it's really a question of discovering heuristics that allow computationally reasonable pay to still create an acceptable level of imperfect play, and piece values are just one of those heuristics. Perfect play in chess can ignore positional concepts and just look for paths that either force a checkmate or a tie. The problem with language translation is you need to understand the context of an idea before you can accurately translate it which is why humans have such issues translating technical content they don't understand. That said, humans can decode things that are close to linguistic gibberish so even a poor translation is often good enough. Google translate is already rather useful though a great set of heuristics despite an endless array of edge cases it fumbles though. It's a useful path that get's ever more expensive the more demanding the problem.

mgkimsal 14y ago
"There are programs that given enough time will come up with piece values for arbitrary board games like chess. " Would different instances of those programs potentially develop different 'values' for the pieces based on their own history and experience of playing? There are some humans that 'prefer' (emotionally) knights over bishops, and will sacrifice one before the other all the time, even when they don't win. Part of that may be that they just don't play enough to develop better strategies, and part of it may just be human attachment to ideas vs 'facts'. I'm no chess master, and I'm not saying knights are better or worse than bishops :)
drostie 14y ago
I guess maybe I wasn't clear. Some modern chess algorithms begin by telling the computer, "here are some numbers you must determine, and how you combine them into an assessment of the game's winnability. Go and analyze a bunch of games and statistically determine which numbers are optimal." To me, that phrasing is itself the problem. I should be able to just say "here are the adequacy conditions for a solution" and then have my computer humming away to guess and then prove possible moves which tend to quickly bring you towards a solution. Mind you, they don't have to be complete rules that solve every case -- that would probably end up implying that P = NP. But most of my logic-puzzle-helpers begin with some sort of code which says, "here is how I will define rules, here is how you should match against them and what you should do when you find a match." Then I have to work out all of these rules for myself and then tell the computer about them one-by-one. If I could just tell my computer, "work out all of the automatic reductions where the logic tree goes less than 20 steps, build rules for those, I will try to handle anything more sophisticated," that would be much better. As yet I've never seen anything like a general algorithm for this, though. :< Turning the declarative to imperative in a portable way would simplify both these programs that I'm writing, and machine translations, I feel.