Answers.Body: <p>A few of us have spent quite a bit of time thinking about this. I summarised our work in a Medium article here: <a href="https://towardsdatascience.com/deep-learning-vs-puzzle-games-e996feb76162" rel="nofollow noreferrer">https://towardsdatascience.com/deep-learning-vs-puzzle-games-e996feb76162</a></p>
  <p>Would love to hear what you think.</p>
  <p>Spoiler: so far, good old SAT seems to beat fancy AI algorithms!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-22T20:57:26.233Z
Answers.Text: Thanks for showing me your article! Very interesting. Have you heard of Kaggle? This would make a nice Kaggle competition.
Answers.UserDisplayName: zooby
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T22:03:58.930Z
Answers.Text: @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?
Answers.UserDisplayName: kgaspard
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-26T02:12:48.450Z
Answers.Text: Don't see why not. Some competitions don't have any prizes.
Answers.UserDisplayName: zooby
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-27T01:23:03.117Z
Answers.Text: 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?
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-22T20:29:26.310Z
Answers.LastActivityDate: 2020-10-22T20:29:26.310Z
Answers.UserDisplayName: kgaspard
Body: <p>The game "Flow Free" in which you connect coloured dots with lines is very popular. A human can learn techniques to play it.</p>
  
  <p>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.</p>
  
  <p>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".</p>
  
  <p>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.</p>
  
  <p>In fact I wonder if the rule of thumb "keep close to other lines" might even require some kind of internal language.</p>
  
  <p>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.)</p>
  
  <p>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).</p>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <ol>
  <li>There is an empty region</li>
  <li>There is a region with a dot without it's pair</li>
  </ol>
  
  <p>Still I don't think this is enough. </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-17T18:24:50.513Z
Comments.Text: 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.
Comments.UserDisplayName: Djib2011
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-17T18:32:37.353Z
Comments.Text: @Djib2011 Rubik's cube is a simple permutation problem. But I would say this flow game you need an visual understanding of things.
Comments.UserDisplayName: zooby
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-17T21:52:20.910Z
Comments.Text: 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.
Comments.UserDisplayName: Djib2011
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-17T22:00:31.993Z
Comments.Text: @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!
Comments.UserDisplayName: zooby
Tags: <game-ai><game-theory>
Title: How can an AI play Flow Free?
UserDisplayName: zooby
ThreadText: # How can an AI play Flow Free?
  
  (Asked by: username_0 on 2019-10-16)
  
  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.
  
  **Tags:** game-ai, game-theory
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: @Djib2011 Rubik's cube is a simple permutation problem. But I would say this flow game you need an visual understanding of things.  
  > **username_1**: 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.  
  > **username_0**: @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!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-10-22. Score: 3 | Accepted answer
  
  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!
  
  > **Comments:**
  > **username_0**: Thanks for showing me your article! Very interesting. Have you heard of Kaggle? This would make a nice Kaggle competition.  
  > **username_2**: @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?  
  > **username_0**: Don't see why not. Some competitions don't have any prizes.  
  > **username_3**: 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?  
  
  ---
  
  