3
$\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$
4
  • 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
  • $\begingroup$ @Djib2011 Yes, that's true. I should take a look at how it does that! I wonder how... I don't even know how a human worked out how to solve it! $\endgroup$ – zooby Oct 17 '19 at 22:00
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!

$\endgroup$
4
  • $\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 '20 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 Oct 25 '20 at 22:03
  • $\begingroup$ Don't see why not. Some competitions don't have any prizes. $\endgroup$ – zooby Oct 26 '20 at 2:12
  • $\begingroup$ Welcome to SE:AI! This answer has been flagged for being link-only. Could I impose on you to give a short summary of the Medium article here? $\endgroup$ – DukeZhou Oct 27 '20 at 1:23

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.