PortfolioAI "minimax" loop

[Anderson Tavares]

Hi everyone,

I'm looking through PortfolioAI's code and how it selects an action.

It seems that it plays out all scripts against each other to fill a score matrix, in computeDuringOneGameFrame, then it selects the action prescribed by the best script in getBestActionSoFar.

My question concerns the criteria for selecting the "best script".

Starting at the line commented as 'minimax' (line 164), it traverses the score matrix and it seems that it determines in which row there is any column with the highest ratio of score / #playouts. Is this interpretation of the "minimax" loop correct?

This criteria is somewhat exploitable, because if in that same row there is a column with very low score, this means that there is a script that beats the 'best' by large margin and the opponent could use it as a counter-strategy... Wouldn't it be better to calculate the Nash equilibria (which corresponds to the actual minimax) from that matrix and then select a script accordingly?

Thanks in advance for any feedback in this sense.

Best regards,
Anderson

[Santiago Ontanon]

I have to admit that I did not put much thought into that AI, since I implemented it for a paper, but we never ended up using it. So, it's been left in the status that it was the first time around I coded it. But I think you are correct in that it might be exploitable :)

The current code just tries to do this:

- For each of the possible strategies of the Max player, the inner loop (line 170), determines which is the best answer of the opponent (Min)

- Then, the outer loop (line 167) determines which is the strategy of the Max player that would result in the maximum score (Max of the Mins).

But in any case, you are completely right that this is exploitable, and that what we should do is compute a Nash equilibrium. Reminds me of the Saffidine, Finnson and Buro paper a few years ago ( http://cadia.ru.is/wiki/_media/public:cadiaplayer:hif_aaai12b.pdf ), which I'm sure is related!

[Anderson Tavares]

Hi, thanks for the clarification and the pointer to Saffidine et al's paper!

I got a little puzzled imagining what PortfolioAI would choose if scripts had cyclical interactions (like rock-paper-scissors) and then I went to analyse its code :)

For me it seems that PortfolioAI almost implements the approach of [1], where a payoff matrix is filled via playouts and Nash Equilibrium is calculated. For PortfolioAI, just the Nash part is missing... I might do some work on it and send a pull request if I get somewhere interesting. I'll probably use Gambit [2] library for equilibrium calculation, which was not written in Java. Is it ok to send a pull request (providing required dependencies)?

[1] Sailer, F.; Buro, M. & Lanctot, M. Adversarial planning through strategy simulation. CIG 2007.
[2] http://www.gambit-project.org/

--
Anderson Rocha Tavares
http://dcc.ufmg.br/~anderson

[Santiago Ontanon]

Absolutely! pull requests are always welcome!! one thing to be careful would just be to make sure that the integration with Gambit is cross-platform (as long as it works in Linux/Mac/Windows it's ok) :)

[Anderson Rocha]

Hi, I'll pay attention to keep things cross-platform :)

I'm thinking on the alternative of formulating a linear program myself and solve with LPSOLVESolver, which is in Java already...

Anyway, let's hope I can get it done either way :)

--
Anderson Rocha Tavares
http://dcc.ufmg.br/~anderson

2017-04-10 18:06 GMT-03:00 Santiago Ontanon <santi....@gmail.com>:

Absolutely! pull requests are always welcome!! one thing to be careful would just be to make sure that the integration with Gambit is cross-platform (as long as it works in Linux/Mac/Windows it's ok) :)

--
You received this message because you are subscribed to the Google Groups "microRTS" group.
To unsubscribe from this group and stop receiving emails from it, send an email to microrts+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/microrts/eb23cb4e-010d-4741-9b44-4425f4e6af7d%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.