The resulting agent is very strong and has comparable performance to Reaper under some rule sets. However the main difference between existing agents and Oponn is that Oponn gets stronger the longer you let it think. The more time you give it, the deeper it can go in the search tree. Letting it think for 2 seconds per move means that its as strong as Reaper in 4 player games. Letting it think for 0.5 seconds per move and its roughly the equivalent of Killbot or EvilPixie. Letting it think for 10-20 seconds per move and it will significantly outperform both. Of course as computers continue to get faster, Oponn will get stronger.
I'd be quite keen to allow Oponn to be included as a downloadable agent in Lux. I've surmised that Lux is about to launch on Steam and I was wondering if Oponn might be included in time? It still doesn't quite play a comprehensive list of all the game modes, but if it is going to be included it should only take a couple of days to add them in. Does anyone know how I might go about this?
If anyone's interested in looking over how its implemented or taking a look at its results against the existing agents let me know and I can send you a link to my dissertation.
Oponn sounds awesome!
We're happy to add new agents as downloadables in Lux. The plugin manager even has versioning capabilities, so you'll be able to update beyond the original release if desired.
To get an Agent included, you should email all the java files to firstname.lastname@example.org, along with a picture you'd like used for it in the plugin manager. We need to view the java source files to verify that nothing bad is being done, since we then distribute the compiled code file to our users.
Looking forward to playing your AI soon
As Dustin has suggested I'm trying to patch support for increasing card sequences into Oponn before release. In theory this is really easy as the MCTS algorithm really doesn't care how the card cashing works, and should automatically account for whatever sequence is used. It just needs to know what the upcoming sequence is. However I've run across a hitch because I can't seem to query from the Lux API where in the card sequence the game is.
Take for example the sequence "4 6 8 10 15 20 25 10 10 10". Say I query the Lux API
Code: Select all
I can manually inspect an opponent's cards at the start of each turn and infer when they've cashed but that seems very clumsy. Anyone have any better ideas?
In coming months, I'm planning to expand the range and granularity of events that are recorded server side for game archival and replay purposes, and increase the availability of such information through the AI SDK. If you have any suggestions for specific types of data that would help you create better agents, then please let me know.
It's also worth noting that we'll be expanding possible card cash progressions to include both exponential increases, as well as adaptive values that will rise and fall after each turn based on multiple factors such as turn number, round number, average army counts, bonus incomes, players remaining, etc.
The "4, 6, 8, 10, 15, 20, 25, 10, 10, 10" progression is almost never used in online games. In fact, I'd recommend it be removed from future releases of Lux, and suggest you ignore it. You should assume cards values either remain static or increase after each cash.
(Granted, cash values might decrease after adaptive values have been integrated into Lux, but that's another discussion for another time.)
I'm eager to review your code and test your bot across a variety of map and game settings. I've run tens of millions of simulations in the past, and would like to put yours through its paces against all other Lux AIs.
Finally, one question: have you included attack cessation triggers in your code? One of my pet peeves about Reaper and BotOfDoom is their inability to abort mid-turn when odds of success have dropped below a reasonable threshold, or after missing one part of a multi-pronged attack thus making an intended kill entirely impossible. It'd be swell to play against a bot that could avoid such obvious asshattery.
I have so many suggestions! Most of them I've managed to work around with sufficient creativity, but there's a couple that have been a real pain. I've also sent Dustin a private message about a massive exploit which AI agents can use in the API. I'm not going to mention it here until its fixed I guess. Would you like me to start a new thread for the more general ones or just create a list here?In coming months, I'm planning to expand the range and granularity of events that are recorded server side for game archival and replay purposes, and increase the availability of such information through the AI SDK. If you have any suggestions for specific types of data that would help you create better agents, then please let me know.
I'm looking forward to hearing some results. How do you rank them? I've used Elo ratings for my dissertation but its not ideal. I was considering implementing TrueSkill rankings but it seemed like a lot of effort. The only problem that you might have is that Oponn is not as quick as the bots your used to! It entirely depends on how many iterations you ask it to perform (and correspondingly how strong it'll be).I'm eager to review your code and test your bot across a variety of map and game settings. I've run tens of millions of simulations in the past, and would like to put yours through its paces against all other Lux AIs.
So currently Oponn has the opposite problem! It re-evaluates after each attack so if it does dip below the minimum needed to carry out a plan it will abort. Actually I say "plan" but Oponn has no plans. In the normal sense it doesn't even know how to play Lux. It doesn't know that holding continents is good. It doesn't know that attacking to get a card is a good idea. It is only told which moves are legal to make in each situation. After a clever mechanism of deciding which path to go down in the search tree it then plays lots of games assuming every player plays entirely random moves. It then looks at the win-loss statistics for the different paths in the tree to decide which is the best move.Finally, one question: have you included attack cessation triggers in your code? One of my pet peeves about Reaper and BotOfDoom are their inability to abort mid-turn when odds of success have dropped below a reasonable threshold, or after missing one part of a multi-pronged attack thus making an intended kill entirely impossible. It'd be swell to play against a bot that could avoid such obvious asshattery.
(Therein lies the real challenge.)
ELO can easily be adapted to multiple players. TrueSkill is in fact ideal given the uneven distribution of relative strengths and the small number of bot types doesn't really matter at all. I'd be interested in hearing what you use though!ELO isn't appropriate given the six rather than two player nature of RISK. TrueSkill isn't ideal either given the small sample size of available Lux bot types and the uneven distribution of relative strengths.
So most of these are automatically taken care of by MCTS. Certainly even very small numbers of MCTS simulations should capture the concepts of securing continent incomes, balance of strength between players, border defenses versus current incomes, card cash values, individual card counts, player turn order, farming for cards, avoiding self-blocks in future turns. Large numbers of MCTS simulations will capture pre-positioning and predicted pathing for future kills and what possibilities exist for multiple kills in a single turn.I'm skeptical that Oponn will be truly successful in games with humans given common maps and settings popular in Lux. There are a great many things that must be evaluated before each turn in terms of securing continent incomes, balance of strength between players, border defenses versus current incomes, card cash values, individual card counts, player turn order, farming for cards, avoiding self-blocks in future turns, pre-positioning and predicted pathing for future kills, determining whether or not kill paths go through third parties, if so what possibilities exist for multiple kills in a single turn
What is important to emphasise that MCTS does not "consider" any of these. These are all emergent properties from playing lots of random simulations and the way in which MCTS chooses where to start the simulations in the search tree.
This leaves determining whether or not kill paths go through third parties which I'll talk about below.
So there are two questions. Whether MCTS can beat other bots, Reaper and BotOfDoom and whether MCTS can compete with players.IMHO, MCTS alone might get you to Reaper and BotOfDoom levels of general strength, neither of which approaches average human skill in online games, but you won't progress much further without implementing and integrating your own human understanding of RISK strategy.
Getting agents to compete against players is incredibly difficult as I'm sure everyone on these boards are aware. The nuances of both explicit and implicit agreements between players are almost impossible for agents to comprehend and track. The psychology of Lux is really one vast iterated prisoners' dilemma. To be honest vast swathes of AI are going to be needed to be solved before any computer can play taking these factors into account. Planning, NLP, knowledge representation, automated reasoning, are all needed to name just some of the areas of AI. In fact the problem might well be AI-complete. So can Oponn play at an expert human level? No
Now is MCTS better than the other existing bots? The trivial answer is give me a 32-core machine and watch Oponn beat the socks off Reaper, BotOfDoom, Killbot whichever agent you care to name. Given long enough time to think the theory guarantees MCTS will play perfectly under the assumption that no psychological games are being played over the top. Now obviously most of us won't be running Lux on such machines in the next 5 years but in 6 or 7 years time? Quite likely. Every year Oponn will get stronger without me even touching its code whereas Reaper, BotOfDoom will remain forever static.
I believe any hypothetical agent in the future that does indeed play at a human level will be running MCTS or something very similar as the strategic analysis algorithm underneath whatever awesome semantics comprehension and automated reasoning algorithms we invent in the next couple of decades.
(So many ways of skinning this proverbial cat, y'know?)
I understand and appreciate the underlying theories here, but there's an infinite monkeys and typewriters aspect to both MCTS specifically and much of AI development in general that makes me uncomfortable. Given the randomness and complexity of RISK, I have less faith in MCTS's ability to approximate high level human skill absent some manual intervention, both today and in the foreseeable future. The universe of possible moves and outcomes is simply too large. I'd also argue that one grand unified perfect strategy for RISK does not exist per se, and you can't divorce the logical and illogical aspects of the game from one another, especially when other players, both human and artificial, are playing with uniquely limited and imperfect strategies themselves. Being able to predict how those individuals will move and respond to moves is a skill necessary for high level performance, and one that might not quickly emerge from an ever increasing number of simulations. In other words, being able to perform almost perfectly well for one turn is one thing, but being able to influence the moves of other players in order to guide the entire game over time towards your preferred outcome is quite another thing entirely.
∞ paranoiarodeo shrugs ∞
(That said, I respect and enjoy your enthusiasm for this project, and look forward to playing with your code. I have no doubt that your approach is exponentially better than previous Lux bots, but that might not be saying much given current skill levels.)
That sounds pretty sound. Place was factored into my Elo rankings but kills definitely weren't. I hadn't really thought about starting position, it definitely makes sense to account for it if you only have a small number of games to base your ratings on. I wonder how many games are enough before it averages out... As for turn order, I ran some experiments and found that it seemed to matter very little. Admittedly that's for bots. Is it accepted wisdom/well documented that turn order is important in human games? Maybe its not so much absolute turn order but who you're before/after? (I am not a strong player!)Personally, I factor both place and kills into my rankings as I believe both reflect quality of play to some degree that winning percentage alone does not. Sometimes I include some duplicate bridge like adjustments by evaluating the relative strength of starting positions and turn order then factoring some amount of expected outcome into individual results too
Ah but, to continue the metaphor, my infinite monkeys all get given a banana each time they type out a sentence of HamletI understand and appreciate the underlying theories here, but there's an infinite monkeys and typewriters aspect to both MCTS specifically and much of AI development in general that makes me uncomfortable. Given the randomness and complexity of RISK, I have less faith in MCTS's ability to approximate high level human skill absent some manual intervention, both today and in the foreseeable future. The universe of possible moves and outcomes is simply too large.
I agree the search space of Risk is VAST!! MCTS tries to alleviate that by prioritising exploration of promising sub-trees. This is in fact very similar to how humans analyse positions. How successful it is is open to debate and I'm sure you'll come up with your own conclusions. However I think this exact argument is why the current generation of bots are doomed as an approach. The search space is simply to large to hand code a set of rules that covers every conceivable situation. Humans are so good at Risk because they come up with new plans and approaches when they encounter a new situation.
Its funny you should mention this Oponn actually does this with the existing Lux agents. It runs internal models of them to improve the accuracy of its simulations. It's quite good when playing without this modelling or against other non-Lux agents, but with it enabled and against the Lux agents it is lethal! Well actually lethal is the wrong word. It is actually extremely peaceful. It manages to avoid nearly all fights and lets the Lux agents knock each other out. I've been playing it in 4 player games with EvilPixie, Boscoe and Quo this afternoon (using only 1000 iterations) and it has yet to lose a game.I'd also argue that one grand unified perfect strategy for RISK does not exist per se, and you can't divorce the logical and illogical aspects of the game from one another, especially when other players, both human and artificial, are playing with uniquely limited and imperfect strategies themselves. Being able to predict how those individuals will move and respond to moves is a skill necessary for high level performance, and one that might not quickly emerge from an ever increasing number of simulations. In other words, being able to perform almost perfectly well for one turn is one thing, but being able to influence the moves of other players in order to guide the entire game over time towards your preferred outcome is quite another thing entirely.
I have tried to incorporate opponent modelling and classification against non-Lux agents as well but this is where I hit a problem in the API that I described in my private message to you. Namely I have no way of detecting what the other players do in their turns... therefore I can't even begin to create a model of their behaviour.
Turn order can be decisive in some circumstances. For example, consider the most popular game in Lux these days: Biodeux; 30% continent bonus increase; 5, 10, 15 cards; etc. Amongst current bots, one can expect the first and second movers to win six times as often as fifth or sixth move. Some of that relates to the fact that the most popular biohazard generator setting creates a map with 34 countries, therefore fifth and six movers are one country short compared to other opponents, and one army short given how Lux randomly distributes armies based on country count. (Obvious math and logic fail, I know.) However, the truth of the matter lies in the fact that the map has many small continents, therefore early movers have more choices for securing early income at minimal cost; an advantage that snowballs in subsequent rounds. Given my own long experience against human players, I would also say that early turn position is a significant advantage whenever card kills might dictate the flow of the game. I always prefer to move as early as possible. When moving later in the order, I play much more aggressively in the opening rounds, knowing such aggression is more subject to random dice odds, but without which I'm more likely to die before the middle game, when there is more potential for my own creativity to triumph.
(This is where I tell you that various maps and settings can constitute a substantially different game. Oy.)
As for you saying that you model opponents in your simulations? Fascinating! If so, then it's obvious that your year of research and programming was no mere hobby. Bravo, sir! However, I would warn that modeling human opponents is infinitely more difficult than approximating the behavior of Lux's simplistic bots. Not impossible, but truly difficult, and best understood from your own player experience, rather than what you might gleam from pure data collection. (Even given more advanced access to prior game data and events.) The hard truth of that matter is that bots rarely if ever win against four or five humans. In part, because humans tend to target bots before humans, but even so, 'cause current bots aren't competiitve against average humans. I guess that's something I'd like to emphasize. Creating a bot that could win against five humans just one-sixth of the time would be a huge milestone. None of us should underestimate how difficult doing so will be. Creating a RISK bot of average human strength would be a huge accomplishment. Truly huge. Huge!
Honestly? I would suggest that you put aside your bot work for awhile, and get your hands dirty as a human player in more online games. Again, I respect the impulse to rely upon the possibility and potential of your AI, but I must suggest that you'll get ahead faster if you know the nuances of the game better yourself. Brief example? There are moments of pivotal action in most games. Specifically, I would highlight moments when a player has four cards, can cash, can kill another opponent with four cards, therefore cash again post-kill. Round eight in particular; eleven, fourteen, etc. Such moments of cascading card kills are when and where some humans can kill three, four, or even five opponents within a standard 30s small map turn timer.
Knowing how to most efficiently pre-position yourself for those moments of potential multiple kills is a skill that elevates some humans far, far above others. Not just targeting one possible victim, but recognizing your position in the turn order, who is moving after you, and how best to target multiple opponents who may or may not cash on three cards, and therefore go to four cards or not. Or knowing when you should more certainly focus on one potential target alone rather than allowing yourself multiple but less likely targets given divided focus.
(As well as knowing how to make yourself more difficult to kill for those moving before you in such situations.)
Infinite monkeys and typewriters? They'd figure that out eventually, I guess. But how can you nudge your AI towards recognizing such obvious moments of resonance today?
Apologies for those who were looking forward to playing Oponn. One more week.
Can I ask what platform you're playing it on? If you're playing on Android it may be that your processor isn't powerful enough to run it at the default number of iterations in a reasonable amount of time. As Dustin suggests, there is a settings file in which you can tweak the number of iterations. You can also turn "debug" on to see what Oponn is doing which should give you some indication of what's going on.I can't seem to get the bot to work. Without timer, it would not place any armies. With the timer, the timer just ran down. Is there some special setting for it?
If you still have problems let me know!
I'm very interested in your dissertation, could you PM/post a link to it? I'd love to see what techniques you've used and what the results are.If anyone's interested in looking over how its implemented or taking a look at its results against the existing agents let me know and I can send you a link to my dissertation.
Looking at it, I am not very surprised it outperforms the other bots. It uses hardcoded models of the other bots to predict their behaviour and uses that in the MCTS algorithm. This feels like cheating :p
MCTS is so awesome exactly because you don't need any domain knowledge in the play-out phase, it uses random moves to simulate till a game ends and then run another 1000(?) simulations to game end and picks the initial move which leads to the most promising (random) results