was based on the general idea to ask a question which reduces the search space (i.e. the number of still possible combinations) as much as possible. A further constraint was: it only askes combinations which still where consistent with the given answers, i.e. possible. This is both a strength (there is a better chance of getting an immediate hit) and a weakness (asking an impossible combination might reveal more information, sometimes).
The algorithm starts with a random question, and then uses the answer to generate and store a set of all those combinations which are consistent with the answer given. Based on this stored set, it computes, for each element and for each possible answer, then number of possible combinations after that answer, and remembers that combination which, independent of the answer, yields the minimal set in the next round. (This is "playing safe", so to speak: minimizing number of guesses in the worst case). There is another strategy, which does'nt rate a question by the worst possible outcome, but by the average set size for the possible answers, and so minmizing the number of guesses necessery in the average case, but I never tried that one.
On my first computer (a Nascom II single board computer of British origin, based on a 4Mhz Z80, 32 KByte of RAM, an internal TV interface, and a Microsoft Basic in a separate 8 K ROM), I implemented this in about 3 KByte of assembler code, and was able to play a 5*8 game in that space. I had to cut off the search for the optimal question, though, for the initial search.
Of course, implementing this algorithm on a mid-range PIC was out of question.
A PIC16F84 has 68 bytes of RAM, plus 64 Bytes of EEPROM. The latter space is of no use for this kind of work (to sensitive, to slow), and some of the RAM is needed for bookkeeping, communications and such. So there is not even enough space for storing the complete search space of a trivial, say, 4*3 game.
So I took a different approach. Instead of computing and storing a large set of still possible combinations (and shrinking it after each answer), I stored the answers, and computed the set of the still possible answers, dynamically. A funny side effect of this is the fact that contrary to the algorith outlined above, which gets faster and faster after each question, this one gets slower and slower, after each try.
For a 4*7 game (four places, seven "colors"), an answer to a guess fits in three bytes, and there are five guesses necessary at most, so there still is plenty of room left for calculating. On the other hand, the program fills up both RAM and ROM (well, flash RAM) almost completely, after all temporary variables and all necessary utility functions are added. In a way, a 16F84 has just the right size for this kind of problem, and it is more than fast enough.
back (better use the back button on your navigation bar!)