3 ms·

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 in

by 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.

jules 14y ago
You should look into constraint satisfaction algorithms and SAT solving algorithms. With these you can encode almost all logic puzzles meant for humans fairly easily. For example for sudoku you just say that each cell contains a number {1..9}, and that all the rows, columns and blocks cannot contain duplicates. This is usually done with a declaration like alldifferent(cell1, cell2, cell3 ..., cell9), where alldifferent is a built-in constraint in any constraint solver worth its salt. These algorithms usually solve the complete logic puzzle in less than a millisecond. Note that these are algorithms for combinatorial logic problems/puzzles, not for searching game trees.

by drostie 14y ago

jules 14y ago

You should look into constraint satisfaction algorithms and SAT solving algorithms. With these you can encode almost all logic puzzles meant for humans fairly easily. For example for sudoku you just say that each cell contains a number {1..9}, and that all the rows, columns and blocks cannot contain duplicates. This is usually done with a declaration like alldifferent(cell1, cell2, cell3 ..., cell9), where alldifferent is a built-in constraint in any constraint solver worth its salt. These algorithms usually solve the complete logic puzzle in less than a millisecond. Note that these are algorithms for combinatorial logic problems/puzzles, not for searching game trees.