1
$\begingroup$

I am trying to find a good approach to create a computer player for the game "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

go yellow !

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Neil Slater
    Commented Dec 30, 2018 at 6:55
  • $\begingroup$ @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" ? $\endgroup$
    – Olivier
    Commented Dec 30, 2018 at 9:36
  • 1
    $\begingroup$ 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 $\endgroup$
    – Neil Slater
    Commented Dec 30, 2018 at 10:14
  • 1
    $\begingroup$ 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) $\endgroup$
    – Dennis Soemers ♦
    Commented Dec 30, 2018 at 16:21
  • $\begingroup$ @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 :) $\endgroup$
    – Olivier
    Commented Dec 31, 2018 at 11:50

1 Answer 1

Reset to default
-1
$\begingroup$

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....

Improve this answer
$\endgroup$

You must log in to answer this question.

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