2
\$\begingroup\$

Is Integer Linear Programming a viable solution for a turn based game AI?

My current AI solution uses an ILP solver. If you are unfamiliar with ILP, it uses a collection of Booleans to find most optimal solution to a linear problem.

I'm concerned about fluctuations in performance and I"m also thinking of portability. I am using C++ to prototype. I have access to an ILP solver that works well with it. I don't know if I"ll find one that I can use on portable devices. I'm unsure if can rely on the computation time being reasonable with an N large enough to get the results I"m planning for.

I am wondering if anyone used this technique (ILP based AI) and would advice against it or in favor of it. Also are there any other (portable and effective) optimization tools that could be used for a similar result? I read about NegaScout but I did not find a book or tutorial that could provide me with a deep understanding of it.

I also read this question which did not help: Implement Negascout Algorithm with stack

\$\endgroup\$
2
  • 1
    \$\begingroup\$ To me this seems like a which tech to use question. I don't have much experience with the topic, but it seems you're not defining your question very well. Exactly what is the problem you're trying to solve? Just worried about the performance on various platforms? \$\endgroup\$
    – House
    Jan 30, 2014 at 23:19
  • 1
    \$\begingroup\$ Portability, and Variance in computation time (how bad can the unexpected worst case scenario be). I don't see how asking about ILP is which tech to use. :) I don't want to waste my time if I can help it. \$\endgroup\$
    – AturSams
    Jan 31, 2014 at 0:50

1 Answer 1

1
\$\begingroup\$

You can build a skeleton system that can technically make all moves (even if all it can do is lose stupidly), and use an artificial neural network (like FANN...) as the decision making backend.

Letting the bot in its weakest form battle against a clone of itself, you can trivially synthesize a training dataset of unlimited size by logging each game and computing statistics relevant to each move.

It can be somewhat artistic choosing the right size network but with a good dataset, it should be easy to tell when you've got it right. Be careful not to overshoot the size, or else it will tend to "memorize" the dataset instead of finding the appropriate algorithm.

I hope AI by neural networks is not too cliche ;)

\$\endgroup\$
1
  • \$\begingroup\$ I will look into this. Is it scalable? How effective is it for turn based games? How long do you guesstimate it takes to learn? \$\endgroup\$
    – AturSams
    Jan 31, 2014 at 0:54

You must log in to answer this question.

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