General AI Suggestions

[jatill]

I only took a couple AI courses in college, so when I create AI games I generally wing it. I've met my match now, though, and need some expert advice. So 2 questions:

1) Can anyone recommend a great resource for learning about video game AI programming?

2) The game I'm working on now is basically a chess variant, but each player moves all of their pieces each turn. Any suggestions on a particular AI method to use?

Thanks.

[Snacko]

1) Google, as the AI paradigms shift from time to time the newest ideas come from research papers. However if you want the basic thread of the mill you can find anywhere on the web you can buy one of those AI Game Programming books.
2) several AI schemes you can use pretty much any time
- good old minmax, it will show good results if you have full information and enough cpu cycles to have a deep enough tree
- Monte Carlo simulation with UTC or other MC variant which allow you to randomly sample the problem space; this can have advantages over minmax if there is a multitude of possible futures which diverge rapidly, because with minmax you can't get deep enough trees (time constrain)
- neural nets and neural nets assisted with genetic algorithms; this can be very tricky as it's hard to describe your problem in NN terms, however a well evolved net can detect better moves trough it's memory

[jatill]

-Minmax is the only AI I've used in the past, but I think in this case it just won't work since there are 10^10 choices each turn of the game.
-I'm interested in MC, and will probably try that. I suspect that it will result in poor AI, though, since like chess, at least 95% of possible moves are horrible. Hopefully I can come up with some heuristics to prune the trees. What is UTC?
-I'm completely unfamiliar with neural nets. I'll have to do some research there.
Thanks Snacko.

[Snacko]

UTC stands for Upper Confidence bounds applied to Trees sounds complicated but basically it keeps some memory of what other MC runs accomplished. There's a site about it being applied to Go http://senseis.xmp.net/?UCT .

A good example of a simple NN AI is Black Jack paper you can read http://lslwww.epfl.ch/~anperez/BlackJac ... avaBJ.html . It also has Java code you you can see how exactly it's coded.
Also there's Blue Moon and Race for Galaxy NN AIs which only have one hidden layer and the C code is pretty easy to read if you know the basics of NN and C

[tanthorjen]

Are there really 10^10 choices each turn of the game?

My thoughts are: in the first couple of turns, it's just a matter of evaluating which land to drop and which card to cast to get some permanents on the board. Although I agree that in midgame, the number of options can start to spiral.

Some possible heuristics to quickly cut down options:
- evaluate total mana producible to see which cards/abilities can be activated. Cards/abilities that cannot be used/cast can be immediately pruned
- mana producing abilities should be skipped when evaluating options
- when casting a card, only evaluate mana producing abilities until we generate enough mana

Usual heuristics for every deck type:
- favor more life
- favor more permanents
- favor more cards in hand


Possible heuristics for aggro/beatdown creature decks since it's probably the easiest deck archetype to get working:
- favor having more creatures than opponent
- favor having bigger creatures in terms of pow/tough

[MageKing17]

Are there really 10^10 choices each turn of the game?

My thoughts are: in the first couple of turns, it's just a matter of evaluating which land to drop and which card to cast...

Not to make it seem like I didn't read the rest of your post, but that 10^10 number wasn't applying to Magic. This is a generic AI discussion, with the OP asking about a "chess variant, but each player moves all of their pieces each turn."

As for the rest of your post, you should take a look at existing Magic AIs, and see how they handle things.