Bot Name: MegaBot
Bot Race: Protoss
Author Name(s):  Anderson Rocha Tavares (corresponding author), Tiago Negrisoli Oliveira, Luiz Chaimowicz, Amanda Santos (former member), Hector Azpurua (former member)
Affiliation(s): Laboratory of Multidisciplinary Research in Games, Universidade Federal de Minas Gerais
Nationality(s): Brazil
Occupation(s): PhD Student (corresponding author)

Bot URL: https://github.com/andertavares/MegaBot
Personal URL: http://dcc.ufmg.br/~anderson/
Affiliation URL: http://www.j.dcc.ufmg.br/

Questions about your bot (please answer as many as you can, especially Q 1-3)

Q: What is the overall strategy/strategies of your bot? Why did you choose them?

MegaBot employs algorithm selection to play StarCraft. An algorithm is a game-playing bot. MegaBot decides which algorithm/bot to activate according to experience accumulated against the opponent. Basically: epsilon-greedy selection to map the opponent to an algorithm/bot and recency-weighted exponential average to update the scores of algorithms (a.k.a. Q-learning update rule).

MegaBot is able to select between Skynet, Xelnaga and NUSBot at match start. It is based on the concepts explored in a paper [1]. This year's submission improves upon last year by taking crashes into account when calculating the scores of each algorithm.

[1] Tavares, Azpúrua, Santos, Chaimowicz. Rock, Paper, StarCraft: Strategy Selection in Real-Time Strategy Games. In: AIIDE 2016. 

Q: Do you incorporate learning of any form in your bot? If so, how was it accomplished? 

We use the recency-weighted exponential average (a.k.a. Q-learning update rule) to update the scores of algorithms. After the match finishes, we assign reward -1, 0 or 1 for defeat, draw and victory, respectively. Then, we update the value of the selected bot using:

Q(a,o) <- Q(a,o) + alpha * (reward - Q(a,o))

Where Q is a matrix indexed by the bot I selected 'a' and the opponent's bot 'o'. Entries in Q are initialized as 1 (optimistic initialization).


Q: Please describe all AI techniques / algorithms used in your bot.
(For example: What parts of your bot are 'hard-coded', which use learning, search, decision trees, state machines, etc)

Bot selection is done via epsilon-greedy; value update is done via Q-learning update rule (see previous question). We are not concerned with details of the bots in our portfolio, just their performance. 

Q: How did you become interested in Starcraft AI?

In earlier stages of PhD, I (corresponding author) was looking for challenging AI testbeds. I have worked with RoboCup Rescue, TORCS, and some others. When I heard of BWAPI, I saw it would represent the ideal testbed because the game is so challenging and so motivating at the same time.

Q: How long have you been working on your bot?

The development of MegaBot started on may 2016 but we have not worked continuously since then.  Continous work on it may have not surpassed four months (very imprecise estimate).

Q: About how many lines of code is your bot?

MegaBot itself has few lines of code, but it is composed of other bots, and they are somewhat big. In total, we have about 83348 lines of code as reported by cloc command line utility.

Q: Why did you choose the race of your bot?

Protoss had bots that interacted in cyclical ways (like rock, paper, scissors) in previous tournaments and we thought that they would make good components for our portfolio.

Q: Did you use any existing code as the basis for your bot? If so, why, and what did you change?

We use Skynet, Xelnaga and NUSBot as our portfolio. We added the logic for algorithm selection, match outcome registration and so on.

Q: What do you feel are the strongest and weakest parts of your bot's overall performance?

The strongest part is the ability to activate the appropriate portfolio component against the given opponent. 
The weakest part is that it is unable to change the active bot during the match. 

Q: If you competed in previous tournaments, what did you change for this year's entry?

We now take crashes into account to update the value of portfolio components. 

Q: Have you tested your bot against humans? If so, how did it go?

The bot has not been tested against humans.

Q: Any fun or interesting stories about the development / testing of your bot?

In 2016 tournaments, we suffered a lot of losses due to crashes. We were unable to account for them, because 'onEnd' function is not called on crashes, so we could not penalize the bot that caused the crash and it was chosen again in the next match. 
We solved this by marking the execution as a crash when the match starts. If it ends normally, 'onEnd' is called and we unmark the crash 'flag'.
On the next start, if the crash flag is there, it means that 'onEnd' was not called and we had the crash. We now use this information to penalize the crash-maker and it does not get selected again. 
It took quite some time to come up with this scheme :)

Q: Any other projects you're working on that you'd like to advertise?

We are also trying to implement a similar approach in FTG-AI and microRTS (to test our learning vs state-of-the-art search approaches). These are work is in progress in: https://github.com/TiagoNO/MegaBot-FTG-AI and https://github.com/amandaccsantos/microrts/tree/burlap-integration

Optional Opinion Questions:

Q: What is your opinion on the current state of StarCraft AI? How long do you think before computers can beat humans in a best-of-7 match?

I see a lot of hard-coded stuff, whereas serious learning approaches tackle specific sub-problems (micromanagement/combats) in disconnected ways (i.e., there is no overall coordination mechanism to activate the specialized behaviors accordingly). 
I think there's a long way ahead before computers can beat humans, but I'm quite sure I'll be alive when it happens. My guess is something around 10 years.

Q: What do you feel is the biggest hurdle (technological or otherwise) in improving your bot's AI?

I'd like to upgrade to BWAPI 4.2.0, but the portfolio bots' codebase is old (BWAPI 3.7.4). 
I'm not sure whether there are enough interesting Protoss bots in 4.2.0 to create a new portfolio. 
I mean, there are surely very powerful bots, but I look for "intermediate" ones that could complement each other to create a stronger "team". The current portfolio is very interesting in this sense, because the bots interact in a rock-paper-scissors fashion (based on AIIDE 2015 results), suggesting they have complementary abilities. In fact, the nice results of MegaBot in previous tournaments also suggests this. 
On the other hand, I could upgrade the current portfolio codebase myself, but I'm quite sure I'll introduce a lot of errors if I do this.

Q: Which bots are the most interesting to you and why?

I like the elegance of OpprimoBot's code. In fact, I have started a project based on it, but unfortunately it ended due to poor build order follow-up (my fault, not OpprimoBot's).
I like UALbertaBot because of the interesting balance that has been achieved between serious research and game-playing performance. Coding was also nicely done there.
I also like krasi0 and LetaBot, they're around for quite some time and still under active development.