Hi,
HappyMutant wrote:
[...] This mitigates the complexity of short tree searches - there are only 11 possible moves (move, turn, or wait) for each of Beethro's moves, and the monsters' moves are deterministic.
[...]
I think that the intermediate goals might be learnable by a neural network or genetic algorithm, as these tasks seem to be related to pattern recognition. The steps required to reach these goals are probably simpler and possibly hand-codable, though an element of self-modification would be important to handle strange cases.
nice analysis - my 2 pennies:
Unfortunately monster movement is deterministic, but not transparent, i.e. monster placement order has an effect on movement. There are rooms that explicitly use this feature to become solveable (or more difficult...) Or think of mazes under tar. Thus two indistinguishable inputs will potentially
need vastly different solutions. They all mean that a trial and error approach in the bot must allow him to learn from previous attempts. That alone makes the problem an order of magnitude harder.
Also in many cases the solution can not be broken down, but the order in which tasks are completed, their timing, side-effects etc. are all important. Think of a puzzle where the first part could be solved easily by hitting an orb which modifies a dungeon element in a much later state in the room such that it becomes unsolveable (close a yellow door in front of the only exit, but hide it under tar). Thus the straightforward solution was the wrong one, but it is not obvious until the very end, potentially hundreds of moves in the future. A universal bot would then need to backtrack to the start of the problem.
Good examples how small modifications can seriously inflate the difficulty of a room are the various "
Return to ..."
holds.
My guess is (i.e. no formal proof offered), that finding a solution to every drod room may generally be in the class of problems requiring exponential time and only special cases may seem easy. Thus such a bot would be next to useless. It could do the easy cases (sometimes), but choke on all interesting ones.
So, the only solution I have is that we chip in, and pay Stefan to quietly sit in a small cabinet and move a mechanical arm that plays drod to perfection...
Cheers,
Rothro
____________________________
And god spake unto me "
Be merry and glad in your heart, for it could be much worse!"
And I was merry and glad in my heart and it got worse!