2
$\begingroup$

The game "Flow Free" in which you connect coloured dots with lines is very popular. A human can learn techniques to play it.

I was wondering how an AI might approach it. There are certain rules of thumb that a human learns, e.g. connecting dots on the edges one should keep to the edge.

Most of the time it appears the best approach is a depth-first search, e.g. one tries very long paths to see if they work. Combined with rules of thumbs and inferences such as "don't leave gaps". Also "Don't cut off one dot from another dot of the same colour".

But there are ways to "not leave gaps" such as keep within one square of another line. That humans seem to be able to grasp but seems harder for an AI to learn.

In fact I wonder if the rule of thumb "keep close to other lines" might even require some kind of internal language.

I mean to even understand the rules of the game one would think one would need language. (Could an ape solve one of these puzzles? I doubt it.)

So basically I'm trying to solve how an AI could come up with these technqiues for solving puzzles like Flow Free. (Techniques that might not work in all cases).

Perhaps, humans have an innate understanding of concepts such as "keep close to the wall" and "don't double back on yourself" and can combine them in certain ways. Also we are able to spot simple regions quickly bounded by objects.

I think a built in understanding of "regions" would be key. And the key concept that dots can't be joined unless they are in the same region. And we have got to a dead-end if:

  1. There is an empty region
  2. There is a region with a dot without it's pair

Still I don't think this is enough.

$\endgroup$
  • $\begingroup$ How is the question different to stackoverflow.com/questions/23622068/… ? $\endgroup$ – Manuel Rodriguez Oct 16 '19 at 18:34
  • 1
    $\begingroup$ @Manuel That is asking for a human implemented algorith. I'm asking about how a general AI would go about solving the game. $\endgroup$ – zooby Oct 16 '19 at 19:28
  • 1
    $\begingroup$ I think that these "rules of the thumb" you speak of can come from training. They don't need to be hard coded or anything. All in all I wouldn't imagine agents having much difficulty in learning flow free. We have seen AI agents solving arguably harder puzzles (e.g. rubik's cube) and the environment seems fairly simple to model and simulate. $\endgroup$ – Djib2011 Oct 17 '19 at 18:24
  • $\begingroup$ @Djib2011 Rubik's cube is a simple permutation problem. But I would say this flow game you need an visual understanding of things. $\endgroup$ – zooby Oct 17 '19 at 18:32
  • 2
    $\begingroup$ A simple permutation game with $43 \cdot 10^{18}$ states and with no indication if you're actually heading in the right direction. It should be an indication that only in the past couple of years have there been AIs capable of solving the Rubik's cube reliably without any human knowledge. $\endgroup$ – Djib2011 Oct 17 '19 at 21:52
2
$\begingroup$

A few of us have spent quite a bit of time thinking about this. I summarised our work in a Medium article here: https://towardsdatascience.com/deep-learning-vs-puzzle-games-e996feb76162

Would love to hear what you think.

Spoiler: so far, good old SAT seems to beat fancy AI algorithms!

| improve this answer | |
New contributor
kgaspard is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ Thanks for showing me your article! Very interesting. Have you heard of Kaggle? This would make a nice Kaggle competition. $\endgroup$ – zooby Oct 22 at 20:57
  • $\begingroup$ @zooby glad to hear you liked it! I have indeed heard of kaggle, but hadn't thought about making this a competition, great idea. Do you know if a reward on the lower side (a few hundred USD) would be enough of an incentive for the community? $\endgroup$ – kgaspard 53 mins ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.