current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 0 down vote favorite

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

share|improve this question
    
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? –  Byte56♦ Jan 30 '14 at 23:19
    
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. –  zehelvion Jan 31 '14 at 0:50

1 Answer 1

up vote 1 down vote

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 ;)

share|improve this answer
    
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? –  zehelvion Jan 31 '14 at 0:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.