[Kde-games-devel] Kmines

[Matthew Woehlke]

Ethan Anderson wrote:
>> Yes, and avoiding those games that start with 0-3 random clicks that
>> turn up 3 neighbors followed by an unlucky one on a mine :-).
> 
> Kmines and gnome mines have both solved that particular problem a long time
> ago, but yeah.

I take it from the first-click delay, it doesn't calculate the board 
until first click? Maybe I am recalling winemine (which I played a LOT 
one night a few weeks ago). So... ok, I guess this is irrelevant (though 
it would have the side-effect of avoiding the first-click delay).

>> I guess I think of "AI" as necessarily having some random factor as
>> well, or at least "complicated" rules or some form of "learning".
>> Otherwise to me it's just a rule engine.
> 
> Ok yeah, I guess that's true.  From now on when I say 'AI', I mean 'Applied
> Intelligence'.

:-D

>> @Richard: I *would* like to see an algorithm that checks for
>> deterministic solvability :-). Having no choice but to guess sucks ;-).
> 
> Yes.  But to attempt to determine that without actually going through the
> process-- isn't that like, NP complete or something?

I don't think so? Initialize the "AI"-solved board by clearing all "open 
areas" (X or more 0-neighbor spaces for some value of X), then for each 
square that is not "solved" (i.e. has more adjacent mines than have 
confirmed locations), apply solving rules. Repeat until no rules can be 
applied, or all mines have been located. If this is unable to 
successfully locate all mines, the board is "unsolvable". I guess that's 
"going through the process", but it's simply an iterative process that 
will either solve the problem or become stuck, and it's the "become 
stuck" situation that signals a "bad board".

> Sphinx is years behind Nuance, unfortunately... but it voice recognition has
> been done, and it has been done well.  Machines are getting better at those
> things all the time.  I mainly meant in a theoretical/logical sense.

I could start a religious war here, but I won't :-).

-- 
Matthew
FOSS: Giving people the cage and it's blueprints, gratis. The "L" matters.