Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Pathery AI / Solvers / Cheating.
#1
Good news! Pathery is NP-Complete. This means that even for a simple map, an algorithm cannot prove a specific solution as being "the best" (Within a 24 hour period {Within a few years for complex maps}).
This is why we call them Pathery AI's, not Pathery Solvers.

Your human brain is (potentially) leaps and bounds better than an AI can ever be.

Now that that's said, here's what AI's can do.
They can find varying success against people. (Depending greatly on the map)
They can make small optimizations to an existing maze- like a 2-wall adjustment. (Making this optimization can take some time - depending on mapsize/wallcount).
They can achieve a 'decent result' like getting 80-90% of a theoretical 'Max' relatively quickly.

I don't want this game to become an AI-Competition. - (Though if there's interest in that - I do have http://www.mazetheory.com/ for a place where AI-Specific competitions could be held)

I will be consistently making decisions as this game progresses to increase the margin between Humans and AI.
- Special maps like "Thirty" and "Unlimited" are particularly difficult for AI's. - Interestingly they're also my favorite maps to play Smile.

- I initially started writing this with the intent for it to be a closed-sticky, but I'm gonna open this up to discussion and make that later. (That way you can correct me if I've said anything wrong ^_^)
- Snap
Reply
#2
(03-04-2013, 08:48 PM)Snap Wrote: Your human brain is (potentially) leaps and bounds better than an AI can ever be.
"Ever" makes this a pretty strong claim, haha.

So what exactly is up with TheCurse and BlueRaja's AIs? It sounded like they use assistance and not full AI; is that right? After all, I don't think they always show up at exactly midnight, which I would expect an AI to do. But if BlueRaja is 100% AI, I'm impressed.

I'd be down for an AI competition. But I suspect there won't be enough interest, in which case I'd love to discuss/collaborate on AI.
Reply
#3
mine is not an AI after all, so i´d prefer the term solver. it doesn't post solutions on the site, only reads the map data from it.
a program that can do 100% for maps like thirtyTwo or mirror image doesn't exist yet, and probably will for a long time. (actually since its a random based solver it could, chances for that are just unimaginable low)
for simple maps like simple, normal or complex (with a few exceptions) the solution is found pretty fast, for anything else it comes up with a crappy solution which i then try to improve manually. thats how i use that...
competition with that would be kinda strange, since its algorithm relies almost only on randomisation, so neither the result nor the solving time are deterministic at all.
(actually it doesn't even terminate, just runs til i stop it)
i suspect there are at least a hand full of other people using software like that, we just gotta lure them out of their holes...
if we do some kind of competition, we´d probably have to use a map the solvers can't max out even close. also, no manual mazing, since ironically that´d be cheating... ^^
SNAAAAAAP, do stuff! I broke it again...
Reply
#4
One thing AIs will never do is they will never miss an improvement that is not visually obvious. Case in point: the Normal from March 4th. This was not ridiculously difficult, but it's nontrivial and nonintuitive to notice the group of 3 blocks doesn't need any support to add moves with perfect efficiency.

This isn't a big deal, though. Just gotta learn to think crazy.
Reply
#5
improvements and optimisations are the (only) strength of the programs. its ridiculously easy to try each used wall on any possible position for an improvement.
however the grouping or finding the rough path direction is their big weakness, thats why e.g. the Thirty Too is yet impossible to master.
i don't even do any explicit grouping etc, it just happens as a series of small improvements from the random seed. of course that is as inefficient as it sounds...
SNAAAAAAP, do stuff! I broke it again...
Reply
#6
(03-06-2013, 05:16 PM)vzl Wrote: One thing AIs will never do is they will never miss an improvement that is not visually obvious.

Actually computers are pretty terrible at most things that are "visually obvious" to humans. Example:

[Image: 2013-03-06_1929.png]

The improvement to take this maze from 418 to 430 is "visually obvious" to most of us, but extremely difficult for an AI to find. The reason is that this is pattern matching, which humans are notoriously good at, and computers notoriously bad at.

This is the reason why the best Go computers in the world cannot beat even half-decent amateurs, and why my AI cannot match even the worst human players on Ultra Complex. Which is why I'm ridiculously excited about the upcoming release of weekly maps Big Grin
Reply
#7
TheCurse Wrote:competition with that would be kinda strange, since its algorithm relies almost only on randomisation

Why would that be strange? Even if each algorithm uses a lot of randomness, the difference is in the quality of the algorithms...

(03-07-2013, 11:39 AM)BlueRaja Wrote: Actually computers are pretty terrible at most things that are "visually obvious" to humans. Example:

I think you misread vzl

(03-07-2013, 11:39 AM)BlueRaja Wrote: The improvement to take this maze from 418 to 430 is "visually obvious" to most of us, but extremely difficult for an AI to find. The reason is that this is pattern matching, which humans are notoriously good at, and computers notoriously bad at.

Whoah, my friend and I had a long discussion about how to get my AI to solve that exact problem, and some similar ones (e.g. shift this set of walls over a bit, to obstruct more on one side or to make more room on the other).

EDIT: BlueRaja - I think your claim about Go AI might be a bit outdated Smile ... or you have super high standards for "amateur"

BlueRaja/TheCurse: I'm guessing AI competition won't happen, so are you interested in collaborating? I've only put a few man hours into my thing, which you can find with some weak google-fu. Your AIs are probably much better than mine and I'd be happy to work on yours instead. I don't have that much free time, but I want to see super awesome Pathery AI!
Reply
#8
well, just put some more hours into it then. ^^
collaborating would mean i´d have to comment my code and explain stuff, since its brutally performance optimized its not really good to read. that sounds like work... >_>
blue and me don't really have our solvers compete to each other, but sometimes i ask him for his solver results for some mazes to have something to compare to.
on that basis a "competition" is easy ^^
we could discuss stuff like wall placing algorithms ´n such though, i´m out of new ideas there...
also, i´m interested in anything that brings performance. like, is there a way to calculate the path without doing an actual BFS for that? or caching BFS information through different wall sets etc.
everyone started with just some hours work on it, just don't stop trying to make it better. Tongue
if you need some ideas or help of any kind just ask.
SNAAAAAAP, do stuff! I broke it again...
Reply
#9
(03-07-2013, 07:12 PM)TheCurse Wrote: like wall placing algorithms ´n such though, i´m out of new ideas there...
also, i´m interested in anything that brings performance. like, is there a way to calculate the path without doing an actual BFS for that? or caching BFS information through different wall sets etc.

Yes, there are a large number of things you could do to improve your performance - not checking for improvements on every tile of the map being chiefly among them. If improving more than one tile at once, there are a few other optimizations you can do to rule out unnecessary cases (like making sure you never check the same groups of tiles more than once, and ignoring any groups that disconnect the graph). You can also completely ignore tiles that can never be part of any best path. I've also had limited success using a few techniques to identify towers that are most likely in the best path, which greatly reduces the search-space; though this can majorly backfire if, say, the 125 that's hard to find is completely different from the 124 that's easy to find.

And if you really want to get fancy, you can get a large speedup by reusing information between pathfinding searches - if you're having troubles with your BFS pathfinder, though, you may want to skip this one, as understanding LPA* is an order of magnitude more difficult.

I've been meaning to write a few blog posts about the subject for a while, but have been lazy. With all this interest, though, maybe I'll get around to it soon.
Reply
#10
well i´m at the point where performance doesn't gain much anymore. it makes stuff faster, i always like that. but it doesn't make better solutions after a while. (or rarely)
there is a certain pretty uncertain point when using random seeds, where the chance for a new result being better than the old is pretty low...
most of the stuff you mention is implemented already, like not checking every tile but just the ones that can affect the path (which strangely only brings significant performance boosts on small or maps), ruling out impossible tiles (that last case described there wouldn't be detected, but as i´ve seen that very rarely occurs. for reducing the search space some priorizing is done, but i gotta disable that for mirror image, it´d block too often... maybe i can improve a little with different priorizing factors, dunno.
i tracked the multiple checking of equal combinations, seems not even worth to count, was about once in 10-50million checks, something like that. (just remembering, that was several improvements ago, perhaps i should track that again...)
maybe i´ll look into one of the other path algorithms, dunno why but i like caching stuff ^^
but that one main point still riddles me, there´s gotta be a better way of placing walls than just create a semi random preset and systematically improve that by more or less bruteforce...
(or at least, get a better preset than just semi random)
SNAAAAAAP, do stuff! I broke it again...
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)