AI opponents

[jh0ker]

This issue is to keep track of the development of an AI ("artificial intelligence") player.

A first, naive implementation is now live on the ismcts branch. It is currently extremely badly integrated (I'll be working on a proper integration, please wait for that until you start contributing code, as this is also dependant on #6).

For testing purposes, you can already play against it using the /add_ai command. To increase iterations, you can use the /set_ai <iterations> command.

Technical background

Right now, the AI is using a modified version of the "Monte Carlo Tree Search", which is called "Information Set Monte Carlo Tree Search" or short: ISMCTS
The current implementation is taken from http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm
It is basically a template to work with most (if not all) imperfect information games, I've simply added the rules of UNO.

Things to consider

Efficiency

Right now, the whole thing is very inefficient. It's written in pure python, so that's kinda obvious. To address this issue, I'd like to implement the algorithm in Cython (http://cython.org/), but I think there will have to be some other changes. Quite possibly this means rewriting big parts of the UNO logic in Cython. But the code needs a re-write anyways (again, see #6).

Efficiency (2)

Problem

Another dimension to the efficiency is that I'd like to offer this service to all users of my bot instance. This means that even by improving this algorithm by say a factor of 1000 (which is not that unrealistic with Cython), it won't be all too helpful in reality. My initial tests showed little difference in the decision making for 10 to 1000 iterations, and 1000 iterations already take several seconds on my i7-powered laptop.

Solution

I have discussed this with a colleague, and his idea was to train some kind of neural network once, and then use the output of that network to determine the next card based on the circumstances. He said, once the network is trained, complexity to get the next move would be O(1) (or O(n), not sure wich)
I have access to rather powerful workstations at my university, so I could possibly use those to train the neural network with different settings of iterations. Of course I'd make the result publicly available.

Help wanted

I have limited knowledge when it comes to neural networks. I know how it works in theory, but my experience does not exceed playing around with http://playground.tensorflow.org/ I also know that there are similar techniques that actually have different names, I'm just grouping everything under "neural network" here.

To those who know more than me:

• Is using neural networks actually a valid approach?
• Which type of neural network should be used?
• How much resources
• Other remarks? Links for me to read? Educate me!