Answers.Body: <p>Writing a game AI is difficult in general and it's even harder when there's no game to play. Like in your case.</p>
  
  <p>While "Lines" is pretty neat, there's no (playing) opponent and there are no moves. apart from the setup. So what we have is an optimization problem where we need to get more point than the "opponents".</p>
  
  <p>Game playing algorithms like Reinforcement learning or MCTS are IMHO out of questions as there's no game to play. Still, it's an interesting problem, though I can't see how to make any <em>learning</em> AI. Anyway, what you need first is a simulator and an optimizer choosing promising actions.</p>
  
  <h2>Some ideas concerning the actions</h2>
  
  <p>Some actions are trivial, e.g., the <strong>eraser</strong> as there are just a few dots to erase. Trying all combination should be good enough for the start.</p>
  
  <p>The <strong>scissors</strong> can be in theory placed anywhere, but the only interesting places are just next to the oponent piece or a crossing. Additionally, you only need to consider crossings which gets "won" (reached first) by an opponent. Moreover, they only matter if they get won by an opponent having more points than you or blocking you.</p>
  
  <p>The <strong>dots</strong> to insert should similarly by placed near an oponent or so that you just win a crossing.</p>
  
  <p>The additional <strong>lines</strong> are worst, as they may be used to let you reach unconnected areas, or reach a crossing faster or simply give you additional points (then you want a long line somewhere).</p>
  
  <h2>A model</h2>
  
  <p>Most of the game can be seen as a non-directed graph with edges labeled by their length, where the crossing and the initial dots are nodes. The simulator doesn't need to work "pixel by pixel", but may instead jump to the next time, when a crossing gets reached or two "flows" meat each other. The points of a player grow linearly with time, where the slope is given by the number of their extending "flows".</p>
  
  <p>So far, I could imagine modelling it as an Integer Linear Program, but with the additional <strong>lines</strong>, it's probably no more possible.</p>
  
  <p>I'd probably let the optimization be simulator-guided, i.e., analyse whether I could get closer to winning by reaching a crossing sooner. The details are still unclear....</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-27T11:47:31.900Z
Answers.LastActivityDate: 2020-01-27T11:47:31.900Z
Answers.UserDisplayName: maaartinus
Body: <p>I am trying to find a good approach to create a computer player for the game &quot;<a href="https://gamious.com/lines/" rel="nofollow noreferrer">Lines</a>&quot; from gamious on Android. The concept of the game is pretty straightforward :</p>
  <blockquote>
  <p>Lines is an abstract ‘zen’ game experience where form is just as important as function. Place or remove Dots to initiate a colourful race that fills a drawing. The colour that dominates the race wins.</p>
  </blockquote>
  <p>The game starts with a drawing (that can be described as a set of &quot;blank&quot; lines, with connection to other lines). Dots of different colour are placed somewhat randomly on the lines. The player get a colour assigned. When the game start, paint start flowing from the dots and filling the (at first blank) lines of the drawing. You win if your colour dominates.</p>
  <p>The game gives you different tools to win (the game starts when all of them have been used) :</p>
  <ul>
  <li>[0 to 2] scissor to cut lines</li>
  <li>[0 to 5] additional dot of your own color to place on the drawing</li>
  <li>[0 to 4] enemy dots eraser</li>
  <li>[0 to 3] additional straight lines to connect different part of the drawing</li>
  </ul>
  <p>A quick example: the first image is the initial state of a round. &quot;My&quot; colour is the yellow (1 enemy = brown) and I have 4 tools (2 eraser and 2 lines). The second image shows the game running after I used the tools to put my colour in a winning position (yes, we can do better)</p>
  <p><a href="https://i.sstatic.net/8Ptar.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8Ptar.jpg" alt="starting the game" /></a></p>
  <p><a href="https://i.sstatic.net/oVsG2.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oVsG2.jpg" alt="go yellow !" /></a></p>
  <p>If I try to approach this as a <em>classical</em> optimization problem, things get messy pretty fast :</p>
  <ul>
  <li>highly non-linear</li>
  <li>high number of dimensions</li>
  </ul>
  <p>AI seems to be the right way to go, but I would like your help to get in the right direction: <em>what would be your approach to create an AI to play this game?</em></p>
  <p>To limit the scope of this question, you can consider that I already have a data structure to represent the game initial state, the use of different tools and the game &quot;physics&quot;. <strong>What I really want to do is finding how to create an AI which can learn how to <em>efficiently</em> use the tools.</strong></p>
  <p>Regarding my experience, I took 2 semesters of AI classes during the last year getting my engineering degree and have used non-linear optimization tools for a while: you can go technical, but I am not fully understand it.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-30T06:55:11.080Z
Comments.Text: Could you explain how your input is structured? Are you starting with a bitmap image of the game, so your first challenge is requiring a system that can comprehend the game based on a screen image? If not, what data structure are you using?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-30T09:36:26.697Z
Comments.Text: @NeilSlater To reduce the scope of the question, you can consider that the game is already represented by the data structure you prefer (2d image recognition would be fairly easy). What do you mean by "input system" ?
Comments.UserDisplayName: Olivier
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-30T10:14:52.917Z
Comments.Text: I didn't say "input system". I was using the word "system" in a general hand-wavy way - could also be "component" or "pre-processor" or whatever. Either way the problem is more complex if you add a requirement for machine vision and that the AI has to solve the game using the same I/O as a human player. You have clarified that you have that solved already though, thanks for the edit
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-30T16:21:22.610Z
Comments.Text: If you can get the game state representation to be the most convenient one possible (probably a graph with all the relevant points and their connections, plus their current colours), and you can efficiently implement the "rules" of the game... my go-to algorithm would be Monte-Carlo Tree Search. If you have to work with raw pixels, you're likely better off learning a policy end-to-end from pixels (i.e. Deep Reinforcement Learning, with extra precautions due to it being a two-player game rather than single-player)
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-31T11:50:51.197Z
Comments.Text: @DennisSoemers Thanks for your input. What bothers me the most is the "add new line" tool. "Scissor", "eraser" and "new dots" are easier to score and to optimize. But "new line" is harder... Regarding the MCTS algorithm, it seems similar to optimization with random restart, the hard part is to choose the moves with some intelligence (instead of playing randomly)... Right know I am trying to find for each tool a matrix linking the tool position to the final score, so I could optimize tool by tool, but no luck so far. I will try the MCTS next week :)
Comments.UserDisplayName: Olivier
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-31T11:57:30.757Z
Comments.Text: @Olivier MCTS became popular specifically in domains where it is difficult/impossible to construct good heuristic evaluation functions by hand (such as the game of Go, and General Game Playing where agents should be able to play pretty much any game without knowing which games they're gonna be playing in advance). The basic intuition behind it is to play lots of games (semi-)randomly, use the average outcomes (wins/losses) of many such simulations as evaluation functions. Plus some tree building to ensure convergence to minimax when given an infinite amount of time.
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-31T11:59:26.540Z
Comments.Text: @Olivier That does assume actually that you have access to a "simulator" or a "model" of the game though. That you can simulate the outcomes that would result from given trajectories / sequences of actions.
Comments.UserDisplayName: Dennis Soemers
Tags: <game-ai><reference-request>
Title: What kind of AI technique can I use to play the "Lines" game?
UserDisplayName: Olivier
ThreadText: # What kind of AI technique can I use to play the "Lines" game?
  
  (Asked by: username_0 on 2018-12-29)
  
  I am trying to find a good approach to create a computer player for the game "[Lines](https://gamious.com/lines/)" from gamious on Android. The concept of the game is pretty straightforward :
  
  > Lines is an abstract ‘zen’ game experience where form is just as important as function. Place or remove Dots to initiate a colourful race that fills a drawing. The colour that dominates the race wins.
  
  The game starts with a drawing (that can be described as a set of "blank" lines, with connection to other lines). Dots of different colour are placed somewhat randomly on the lines. The player get a colour assigned. When the game start, paint start flowing from the dots and filling the (at first blank) lines of the drawing. You win if your colour dominates.
  
  The game gives you different tools to win (the game starts when all of them have been used) :
  
  * [0 to 2] scissor to cut lines
  * [0 to 5] additional dot of your own color to place on the drawing
  * [0 to 4] enemy dots eraser
  * [0 to 3] additional straight lines to connect different part of the drawing
  
  A quick example: the first image is the initial state of a round. "My" colour is the yellow (1 enemy = brown) and I have 4 tools (2 eraser and 2 lines). The second image shows the game running after I used the tools to put my colour in a winning position (yes, we can do better)
  
  [![starting the game](https://i.sstatic.net/8Ptar.jpg)](https://i.sstatic.net/8Ptar.jpg)
  
  [![go yellow !](https://i.sstatic.net/oVsG2.jpg)](https://i.sstatic.net/oVsG2.jpg)
  
  If I try to approach this as a *classical* optimization problem, things get messy pretty fast :
  
  * highly non-linear
  * high number of dimensions
  
  AI seems to be the right way to go, but I would like your help to get in the right direction: *what would be your approach to create an AI to play this game?*
  
  To limit the scope of this question, you can consider that I already have a data structure to represent the game initial state, the use of different tools and the game "physics". **What I really want to do is finding how to create an AI which can learn how to *efficiently* use the tools.**
  
  Regarding my experience, I took 2 semesters of AI classes during the last year getting my engineering degree and have used non-linear optimization tools for a while: you can go technical, but I am not fully understand it.
  
  **Tags:** game-ai, reference-request
  > **Comments:**
  > **username_1**: Could you explain how your input is structured? Are you starting with a bitmap image of the game, so your first challenge is requiring a system that can comprehend the game based on a screen image? If not, what data structure are you using?  
  > **username_0**: @NeilSlater To reduce the scope of the question, you can consider that the game is already represented by the data structure you prefer (2d image recognition would be fairly easy). What do you mean by "input system" ?  
  > **username_1**: I didn't say "input system". I was using the word "system" in a general hand-wavy way - could also be "component" or "pre-processor" or whatever. Either way the problem is more complex if you add a requirement for machine vision and that the AI has to solve the game using the same I/O as a human player. You have clarified that you have that solved already though, thanks for the edit  
  > **username_2**: If you can get the game state representation to be the most convenient one possible (probably a graph with all the relevant points and their connections, plus their current colours), and you can efficiently implement the "rules" of the game... my go-to algorithm would be Monte-Carlo Tree Search. If you have to work with raw pixels, you're likely better off learning a policy end-to-end from pixels (i.e. Deep Reinforcement Learning, with extra precautions due to it being a two-player game rather than single-player)  
  > **username_0**: @DennisSoemers Thanks for your input. What bothers me the most is the "add new line" tool. "Scissor", "eraser" and "new dots" are easier to score and to optimize. But "new line" is harder... Regarding the MCTS algorithm, it seems similar to optimization with random restart, the hard part is to choose the moves with some intelligence (instead of playing randomly)... Right know I am trying to find for each tool a matrix linking the tool position to the final score, so I could optimize tool by tool, but no luck so far. I will try the MCTS next week :)  
  > **username_2**: @Olivier MCTS became popular specifically in domains where it is difficult/impossible to construct good heuristic evaluation functions by hand (such as the game of Go, and General Game Playing where agents should be able to play pretty much any game without knowing which games they're gonna be playing in advance). The basic intuition behind it is to play lots of games (semi-)randomly, use the average outcomes (wins/losses) of many such simulations as evaluation functions. Plus some tree building to ensure convergence to minimax when given an infinite amount of time.  
  > **username_2**: @Olivier That does assume actually that you have access to a "simulator" or a "model" of the game though. That you can simulate the outcomes that would result from given trajectories / sequences of actions.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2020-01-27. Score: -1
  
  Writing a game AI is difficult in general and it's even harder when there's no game to play. Like in your case.
  
  While "Lines" is pretty neat, there's no (playing) opponent and there are no moves. apart from the setup. So what we have is an optimization problem where we need to get more point than the "opponents".
  
  Game playing algorithms like Reinforcement learning or MCTS are IMHO out of questions as there's no game to play. Still, it's an interesting problem, though I can't see how to make any *learning* AI. Anyway, what you need first is a simulator and an optimizer choosing promising actions.
  
  ## Some ideas concerning the actions
  
  Some actions are trivial, e.g., the **eraser** as there are just a few dots to erase. Trying all combination should be good enough for the start.
  
  The **scissors** can be in theory placed anywhere, but the only interesting places are just next to the oponent piece or a crossing. Additionally, you only need to consider crossings which gets "won" (reached first) by an opponent. Moreover, they only matter if they get won by an opponent having more points than you or blocking you.
  
  The **dots** to insert should similarly by placed near an oponent or so that you just win a crossing.
  
  The additional **lines** are worst, as they may be used to let you reach unconnected areas, or reach a crossing faster or simply give you additional points (then you want a long line somewhere).
  
  ## A model
  
  Most of the game can be seen as a non-directed graph with edges labeled by their length, where the crossing and the initial dots are nodes. The simulator doesn't need to work "pixel by pixel", but may instead jump to the next time, when a crossing gets reached or two "flows" meat each other. The points of a player grow linearly with time, where the slope is given by the number of their extending "flows".
  
  So far, I could imagine modelling it as an Integer Linear Program, but with the additional **lines**, it's probably no more possible.
  
  I'd probably let the optimization be simulator-guided, i.e., analyse whether I could get closer to winning by reaching a crossing sooner. The details are still unclear....
  
  
  ---
  
  