Building a Warlocks AI

Excerpts from an interesting d-1337 conversation

Dubber

>Hmm... on second thought, I guess what I'd really like is a tool that
>will take the current game situation & render possible moves that
>aren't completely dumb.

Slartucker
There are a host of subtleties involved in defining "completely dumb" that make this problem much more complicated than it looks like. You will either end up discounting moves that you shouldn't, or you will end up with a vertiable flood of output, problematic to sort through, unless you have a ranking algorithm rather more sophisticated than any of our brains :)

Taliesin
Could whoever's writing this tool for Dubber write an add-on module for me that always picks a move guaranteed to lead to a winning game against my opponent? I mean, sure, I've been winning a lot lately, but I'm coming to the conclusion I'm putting too much effort into it. There has to be an easier way.

More seriously: this is the core of the theorised AI that's being talked about here, and writing something like that would be a hard problem. Much more work than reimplementing Warlocks from scratch.

The Cognitive Model

Dubber

>  No, serously, I've been thinking some (GASP! Dubber, thinking?!) if we
>  could understand and consolidate our ranking systems for spells while
>  other spells are potentially enroute (which is basically what I think
>  most of you do in situ) we could come up with an algorithm that might
>  actually become at least a 1500+ player (hey, I'm aiming low).

Taliesin
The problem is - for me at least - that my ranking system is almost absurdly complex to represent, and varies continuously over the course of the game, so my endgame play is very different from my opening play. Even the simple strand of how much damage I'm willing to take for what gains is something I could write thousands of words on and not convey fully.

Also, to reiterate this once again: programming the system to merely understand what the spells do, with no algorithm employed, is pretty much on a par with implementing Warlocks from scratch. All the oddball interactions we've discussed over the years would have to be included. Reimplementing the game with arbitrary rulesets and team play would be easier than producing an AI that had even a slightly non-primitive algorithm for picking spells. A 1500 ELO player would be significantly more work than that.

You're essentially asking us all to distill our respective understandings of the game into a simple axiomatic list. While I'd love to be able to do this for neatness' sake, and try to do so in some measure, it's not a problem that decomposes so tidily. Looking at even the most basic axioms I do hold to, I can readily find exceptions.

i.e.

  1. Clapping when neither player is near death before the clap is bad.
    Except when you're clapping for Haste... or Disease... or a Dispel hidden in Invisibility...

  2. Look after your monsters and they will look after you.
    Except when your health is so low that you can't afford the damage... or you see a realistic prospect of charming them back shortly afterwards... or you have a lethal attack that will go unblocked if they charm the monster... or, very occasionally, leaving one charmable as a desperate gamble in a tight game against a sound strategist is workable.

  3. Resistance is useless.
    Except, possibly, when they're likely to counter your WFP anyway; it gives you an minor extra option in the endgame.

  4. After being Charmed, input W on both hands.
    Except of course if you can finish an important spell on one hand in the next turn or so - a disruption such as a Charm, or a Poison, or Blindness, or Summon Giant... etc etc.

  5. Stabs are bad because they damage your spellflow.
    Except there are occasions where minimal damage to your spellflow results and you take out a monster that could damage your spellflow for many future turns; or if you can persuade your opponent to paralyse a stabbing hand, something which often wrecks his paralysis pretty fast.

But if we try to take another step above these and become more detached, you end up with the trite and trivial: i.e. always consider the worst case scenario or scenarios, and plan accordingly.

Dubber, old man, you're asking the impossible. What you'd end up with would be a book's worth of prose from the group, containing often conflicting pieces of advice. Turning this into a computer algorithm would be hard. Using it as food for the algorithm in your head might be practical, but I harbour no illusions that if I wrote a tome explaining the principles I use, my feelings about each individual spell, the more complex patterns I'm familiar with and my thoughts on psychology it would enable others to play as I do. It might give some of the players who read it a bit of an edge, and it would certainly give my opponents a powerful weapon against me, but it wouldn't result in a crop of Taliesins.

The Data Mining Model

Maven
... all of which is why the easiest solution would likely be to have a program just analyze the games of the best players and copy their response to each situation. The program comes up with the correct answer without having to "know" the reason why. It could also provide a list of *all* responses which these players have used, providing the list the old man wants :)

Dubber
Hmm.. Maven, I think you whacked that on the head; not 'why was it done', but 'what was done against what'.

So, we've got a scraper & a database of completed games. The elements to consider are: life remaining; potential spells to cast; potential spells to be cast against (missed something, I know). Skip the human 'whyness' and psychology.

Surial
I've thought about the database approach but even that has significant problems.

Exactly what do you stamp as 'similar circumstances'? If you go for the whole kit 'n caboodle, monsters, health of monsters, health of warlocks, own hand gestures, enemy hand gestures, and all relevant spell effects, then I bet you're reduced to 2, 1, or even 0 valid database entries, and then you get predictable. Also, what if the few you do find end up being losers; that is, the one whose moves you are mimicking lost that match? Clearly you need a system that can realize when certain statistics don't matter. If only do filter out the existence, or lack thereof, of resist heat/cold.

But now we're right back where we started: Now we sort of need to know what it all does; usually resist heat/cold is irrelevant but not always. Then you're down to heuristics. Which is a tricky game and strongly suggests your AI will be workable but far from perfect.

And I haven't even begun to look at parafc and maladroit gumming up the works and further reducing the target set of similar moves, and then there's also invisibility and blindness to consider - you do have to look at effects and do some basic realizations as to what was below those questionmarks. You could theoretically match against similar events during the flow of another game which featured an invis/blindness at the same moment.

Still tricky. I'm willing to bet very good money that this is the fastest way to a 1700+ ELO AI, but a walk in the park it is not, and I doubt it'll ever break 1900 ELO. (That is, have a shot at #1).

I'm certain it's possible to make an AI that can beat us all, but it'll be hellishly difficult to make.

The Educated Data Mining Model

Slartucker
Actually, I would want to use the following learning format rather than a scraper:

Have a bot 'follow around' a willing master warlock. Each time they input a move, have them also input:

  • What parts of the environment determined their move (i.e., what could have been different with no effect on their decision of what to do? I picture click-and-drag spellflow chunks and life meters. For environmental stuff (monsters, conditions, etc) probably just indicate yes/no relevance for what IS present, rather than having to input every turn that your move was not based on opponent's lack of fire resistance...)
  • Is it definitely the best move, probably the best move (depending on what the opponent does), or a real toss-up?
  • Did psychology or metagaming play a significant role in their move choice?

    Build up a database of those entries. Ideally find an exact match when the bot then looks for a move to use in a game, if not find the most similar match. This provides a number of advantages over the scraper and the cognitive model:

    1. NO ranking algorithm is needed (though you want the warlock to be able to flag moves they decide, in retrospect, were unwise)
    2. NO encoded knowledge of spells or rules needed at all!
    3. Will not overgeneralize based on scraped data
    4. NO shoddy approximations of maxims are needed (the maxims appear in their natural, ephemeral elegance in the raw output of the warlock)
    5. Has the potential to fairly easily account for a (very limited) set of psychological factors, the player-specific ones... for example, it could capture the usefulness (100% of the time, at present!) of S/W opens against Tchichi.

    It will take a little while to build up a data pool, but each move provides information (accurately) for many more potential moves than with the scraper. The scraper has no ability to target its generalizing accurately unless you program interpretable rules and deal with shoddy maxims, and I think Taliesin has already debunked the usefulness of attempting to do that. And unlike a cognitive model, this one can be plausibly built!

    So, beat my idea down, what have I overlooked? :)

    Taliesin
    Sounds fine in theory, you should have a workable AI somewhere inside a decade.

    Oh, you wanted it faster than a decade? :P You'll have to play more games then!

    (More seriously: you end up with the same problem as with the raw data search, i.e. not enough relevant hits for any given situation. It will probably adjust to situations involving short, common spells relatively quickly, especially in the opening, but it would probably take tens, perhaps hundreds of thousands of games before you had a half-decent selection of responses to Poison attacks, say - this is merely an artefact of how commonly Poison is cast and the wide variety of methods of enforcing it, plus the difficulty of defending successfully against it).

    The State-Space Crunching Model

    Taliesin
    The advantage a computer has over a human in strategy game AI is in its capability to evaluate vast numbers of possible moves; its evaluation may be cruder, but as it looks more and more moves ahead, it gets a progressively better picture of what the best move to play now is. We call the array of possible moves the "state-space" in AI - i.e. each position is a "state" for the game to be in, and the "state-space" comprises all possible states for the game to be in within however many moves you're looking ahead. The traditional way of implementing a strategy game AI is searching this state-space for positions that evaluate as favourable.

    Obviously this is a different means of implementing an AI than regurgitating games that have already been played, and a much better one if you want to look at likely positions several moves ahead. If you're looking three moves ahead using the regurgitation route, what you'll actually get on your futures list is what people have successfully played, not all possible variations; however, if you happen to be in a bad line anyway, all the suggestions you get may rely on the opponent doing something abysmally stupid (because the opponents who didn't do something abysmally stupid won). I'm not sure why you'd want the futures list for an AI anyway, if it's not crunching the state-space...

    Incidentally, I would like to go on the record as stating that I categorically disapprove of the notion of any sort of helper tool of this nature being developed (i.e. non-AI) and I would be chary even of an AI being developed if I thought it was going to be any good. I can't see much use for the former that doesn't involve cheating, and the potential for cheating with a good AI is pretty strong too. It happens plentifully with chess online, and I've no desire to find myself lining up against AIs in Warlocks.

    Nawglan
    On that note. RB did tell me it was OK to create a bot to play warlocks. He did not want it to be automated (real time) but said that if it made a move a few times a day that would be ok. I would have to manually create games for it to participate in. It also had to clearly state in the user id and on the player page that it was indeed a bot and not a human player.

    The Neural Net Approach

    Yaron
    I spent some time thinking about this problemÊa couple ofÊyears ago, and ended up dropping it because of lack of sufficient programming skills and, of course, laziness.

    Here are the thoughts I had, for what they're worth.Ê My ideaÊis based on a (rather big) neural network.Ê I had two different ideas for how it should be set up, but both are based on the idea of "spell-in-time" neurons.Ê This kind of neuron deals with the possibility of a certain player casting a certain spell at a certain time.Ê Examples:Ê a "me-FoD-in-5" neuron would "go off" wheneverÊthe AIÊcan cast an FoD in 5 turns (i.e., has PWP in one hand), while a "opp-Fear-in-1" would turn on whenever the opponent can cast fear next turn (i.e. has SW in one hand).

    Version 1:

    The input neuronsÊconsist of 3 ofÊeach spell/time neuron:Ê one for the opponent, one for the AI's LH, one for the AI's RH.Ê Each neuron lights up if theÊcorresponding player/hand can cast the corresponding spell at the corresponding time.Ê There are also some other input neurons representing other aspects of the situation - health levels, existing enchantments, etc. (you don't have to consider existing disruptions - they are already represented by which spells are possible).

    The 13 output neurons represent the 5Êstandard gestures for each hand (+stab), and clap for bothÊhands.Ê The AI plays according to the highest scoring neuron for each hand.

    Version 2:ÊÊOnly have one set of spell/time neuronsÊ- for the opponent (and the general input neurons for health etc.).Ê Another set of spell/time neurons acts as output.Ê So, for a given set of inputs (opponent's gestures so far), you get a ranking of spells you want to cast, and when.Ê Then, you pick the best option that is actually possible based on what your hands look like (i.e, "Fod-in-1-turn" will almost always rank highest, but will only get cast if you actually have PWPFSSS in some hand).

    Version 2 is more manageable size-wise, but has some limitations - especially regarding the effective combination of spells from both hands.

    Both are rather large, though, and we haven't even started discussing targetting, not to mention monsters.

    The next problem with neural networks is how to train them.Ê The more ambitious way is letting nets fight each other, and self-select with some genetic algorithm.Ê This could theoretically produce a super player that will teach us all new tricks, but in practice will probably:

    1.Ê Take super-computeresque amounts of CPU-time.
    2.Ê Not work.

    A more reasonable approach would be to train the net using traditional back-propagation, using the games of the better players as data points.Ê For those of you unfamiliar with the jargon, the idea is to parse games turn by turn, give the network inputs as if it was actually playing the game that turn, and then adjust its parameters so as to produce the same result the player came up with (back propagation is the name of the (rather simple) algorithm that does all that).

    This method is a little more likely to work, but of course, we won't be getting anything new.Ê At best, the AI will be able to imitate the style of the players used for the data.

    Taliesin
    Trying to handle something like this as a neural network in the manner described sounds implausible to me - it's very hard to get a neural network to pick sensibly from a wide range of outputs, even if the game were simply a matter of damage dealt; with monsters, disease/poison, FoD and the much nastier disruptions and hidden gestures, I don't think a neural network stands a chance. I'd expect a neural network playing other neural networks to learn to converge on something that works well on hopelessly bad players - P/> - and then stay there, and that's a best case scenario.

    There's the old story of the researchers trying to get a neural network to distinguish between tanks and trucks. They fed it photos of each, and it became remarkably good at distinguishing which was which in the test data. Then they fed it some arbitrary photos of tanks and trucks. It didn't work. After some time spent attempting to debug its workings, they realised that the input photos of the trucks had been taken with a cloudless sky; the tank photoshoot had been conducted on an overcast day. The system had grown quite good at distinguishing what shade of sky was dominant in each image.

    There are good reasons why neural networks aren't generally seen as the main component of high-level strategy game-bots.

    An expert system however might be a better idea - search for every occurrence of the current pattern in the data gathered to date, see how the games ended, pick the most successful pattern. Begin with the matches which cover the most moves etc. This gives you a crude state-space search equivalent with a human-determined heuristic. It'll need a hell of a lot of data munging though.

    Warlocks vs. Chess

    Dubber
    My impression is Warlocks (without monster consideration) has fewer data points/variables/problems/considerations than chess does (I'm likely wrong, btw, I'm only a strong duffer in chess, too) but successful AI have been programmed for it.

    Surial
    One of the ways in which traditional 'chess-player' AI strategies fail to work for Warlocks is this:

    In chess, it's relatively easy to assign a point value to a given state; pieces that you're missing are negative points, pieces the opponent no longer has are positive points, a general 'positional point value' for your pieces count positive, and the enemy's position's value counts against you, and, voila, a point value to use in evaluating the state space. It's all optimization from there. Yes, sometimes this misses a crucial event (positionally it's not all that good but there happends to be a mate-in-two available in a given state, which, assuming the chess playing AI doesn't look that far ahead misses completely)... but as a general rule it'll do something sort of half-way indicative of winning chess play.

    You can assign points to current health, available monsters, and stuff like resistances fairly easily, but it rapidly becomes impossible to assign a serious point value to any other 'atomic' facts of a state. Exactly how valuable is having a poison on the enemy if the enemy's already got PDW ready to go and you have no counter to stop it? Yes, you could program a 'special case' for such a thing, but the amount of special cases abound for just about everything, and then you'll never be finished with your AI.

    Taliesin
    This problem exists in chess AI too. How valuable is being a queen up if next move you suffer an unstoppable checkmate?

    If you're at the point of casting Poison, you should be searching a sufficient number of moves ahead to foresee the counter and re-evaluate. If you're four moves back and seeing Poison as a possibility, and not searching far enough ahead to see the counter, you'll maybe take the wrong road; but it's the same wrong road a chess computer would take with a queen-winning strategy that led to a mate just off its radar. Special cases nothing, state-space search is the way it's done.

    Surial
    Aside from the atomics of a state, you're also looking at 'positional play' - something that's represented by your hand gestures and your enemies'. In chess, the positional setup of each player is roughly independent; you can look at just one player's pieces, come up with a rough point value, then look at just the other player's pieces, come up with a rough point value for that, and if you then state that the player with the higher 'score' is ahead, that works out far more often than not.

    Taliesin
    No. Position in chess is quite separate and distinct from material, which is what the piece values correspond to. Health and monsters correspond to material in chess quite adequately. It's possible to be heavily materially up in chess yet positionally be about to lose; or even be more subtly positionally down (which is the entire point of a gambit play). This distinction is clearly made in most chess literature. Calculating position as opposed to material in the AI cannot be done by pattern-matching - computers are absurdly bad at this compared to the human mind - and is instead generally handled by state-space search (admittedly with some heuristics to prune the tree).

    Surial
    In warlocks, the value of a given position is extremely dependent on the enemy's hand gestures. a DPP or DSF (Maladroit) is utterly worthless if your enemy's got PPWS left and ?DWS right; the general best move from there is 'S/S' anyway, and neither Amnesia nor Maladroit can do a thing to stop it from happening. In other situations, those spells could be absolutely killer; think of DWWFW left and WFPSF right when an amnesia hits; you just prevented a giant and a poison. That's worth gold.

    Hence, trying to assign a general point value to 'I have DP on my left hand', is nigh impossible. There's no simplistic thing that you can reduce a play to save actually killing your opponent; and before you're at a kill from any normal non-end-game play, your CPU will be hopelessly lost churning away at impossibilities.

    Taliesin
    But having a knight on e5 has no general point value either except as considered as part of a larger positional whole. You need to incorporate your opponent's position to evaluate your own in chess as in Warlocks. These are exactly the same problems as chess you're talking about, it's just that material counts for slightly less and position slightly more. However, position is relatively less complex in Warlocks - it's unlikely that a move you made on turn 14 will only come back to bite you in the ass on turn 27, whereas in chess this is a very distinct possibility (think doubled pawns etc). Chess AI techniques would work admirably for Warlocks, but building a chess AI is a distinctly non-trivial task.