4
$\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.

Improve this question
$\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, 2019 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, 2019 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, 2019 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, 2019 at 22:00

1 Answer 1

Reset to default
3
$\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
$\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, 2020 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, 2020 at 22:03
  • $\begingroup$ Don't see why not. Some competitions don't have any prizes. $\endgroup$
    – zooby
    Oct 26, 2020 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, 2020 at 1:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .