AI spends too much time evaluating impossible actions
Opened this issue · 4 comments
I've been profiling the simulator. Web stuff aside, a very large amount of time is being spent in chooseByPriorityAndValue, particularly when it calls actionPriority.
actionPriority ends up evaluating the relative merits of every action in the game for the current game state every time it is called. This is very wasteful.
In most cases, simple AIs will have a very simple decision, e.g. do I play my Smithy? In many cases, the answer is always yes. As things stand, though, that AI is stuck considering how it'd rank its Smithy against a Spice Merchant, even if Spice Merchant isn't available in the game.
I'm not sure exactly how to fix this without really messing with how AIs are written, but it has a big impact on performance (around 20% of the sim run time, likely more for allocation/GC).
I've been thinking about this a little more. I think we'd save a lot of execution time and GC churn converting the default actionPriority to an equivalent actionValue and similar for treasurePriority.
Specific AIs could still implement actionPriority or treasurePriority as normal, and that would override the default code. Presumably actionPriority for a specific AI would be very lightweight and focused.
Doing this in a maintainable way would be tricky, but it wouldn't break the existing API. The speed benefits are probably worth the tradeoff in maintainability.
I have a branch where I've been working on assigning everything an actionValue. I've just put it aside for a long time. It's a whole lot of numbers to keep track of...
I was looking at heuristics.coffee the other day and had an idea. The player has a lot of information about a card's exact effect at any point in the game. For instance, we know precisely how many cards Crossroads will draw and how many actions it will give us. Similar for Conspirator, Shanty Town, Money Lender, etc.
What if cards could provide that information? They could have a "characterize" method that would provide the kinds of numbers that heuristics.coffee gives, but specific to the current game state.
That could simplify the actionValue of many cards down to a simple calculation. After that, it's a matter of handling the cards that have an effect which is hard to quantify (Native Village, Golem, etc).
Beyond what's in heuristics.coffee, I think we'd want to add a list of, for lack of better words, "likes" and "dislikes" for a card. I don't think this is an AI thing, just a fact that certain cards improve in certain conditions. Library wants a small hand. Crossroads wants a big hand with lots of green. Baron wants an Estate in hand. Shanty Town wants to go last.
For cards like Pawn, which involve a decision, we could ask the AI what it would do with Pawn if played now and just return that back to it.
Anyhow, that's the sketch of an idea. I'm sure there are more considerations, but I think something like that could make actionValue easy and open up possibilities for the AI elsewhere.
I came up with a fix to this that keeps things defined in a manner similar to how they are now, but shaving off around a third of our total execution time. I need to clean it up, but I should have it out in a day or two whenever I find the time. 9s to run 1000 simulations in Google Chrome on my machine. Exciting!