2
$\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 not you-need-a-specialized-AI-degree-to-understand-the-answer technical

$\endgroup$
  • $\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 Dec 30 '18 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 Dec 30 '18 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 Dec 30 '18 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 Dec 30 '18 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 Dec 31 '18 at 11:50
0
$\begingroup$

The development of AI controllers for games isn't based on mathematical algorithms, but has to do with classical software engineering. The interesting phase is between initializing the project and before the first prototype is created. The steps before the first AI prototype is ready are easy to name: requirements engineering, dataset recording with expert demonstration, natural language description and creating a Domain specific language. The tools in doing so are not located in classical programming but the steps are done with a texteditor, painting software and with video editing software.

Instead of giving detailed examples of all the steps, i only want to introduce the first one: requirements engineering. The result of this step are notes written in English which are describing what the AI agent should do. Is he forced to win the game and beat all humans, or is it enough if he plays a bit according to the rules without become the next champion? Another requirement may be, that the agent is able to select an item on the screen, that means to simply find the correct position of the button. A third requirement might be, that he is able to assume how much colored lines are available in the game.

$\endgroup$
  • 1
    $\begingroup$ By "tools", I meant the 4 ones given by the game : scissor, rope, eraser and additional dots. Unless I am mistaken, you answered the question "how to develop a software", not the one I asked. I edited a little my question. $\endgroup$ – Olivier Dec 30 '18 at 15:54
  • $\begingroup$ Did i understood you right, that you're not interested in developing a game AI which can play the game “lines”? Instead, you want to educate what the best practice method is in dealing with non-linear problems? Perhaps we will find some consensus, that problem solving in games has to do with natural language abstraction. $\endgroup$ – Manuel Rodriguez Dec 30 '18 at 17:08

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.