It is currently 12 Dec 2018, 16:37
   
Text Size

General AI Suggestions

Non-Application Specific Programming Stuff

Moderator: CCGHQ Admins

General AI Suggestions

Postby jatill » 19 Oct 2010, 12:28

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.
jatill
DEVELOPER
 
Posts: 2118
Joined: 24 Feb 2009, 16:35
Has thanked: 5 times
Been thanked: 17 times

Re: General AI Suggestions

Postby Snacko » 19 Oct 2010, 13:26

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
Snacko
DEVELOPER
 
Posts: 826
Joined: 29 May 2008, 19:35
Has thanked: 4 times
Been thanked: 73 times

Re: General AI Suggestions

Postby jatill » 19 Oct 2010, 13:52

-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.
jatill
DEVELOPER
 
Posts: 2118
Joined: 24 Feb 2009, 16:35
Has thanked: 5 times
Been thanked: 17 times

Re: General AI Suggestions

Postby Snacko » 19 Oct 2010, 15:59

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
Snacko
DEVELOPER
 
Posts: 826
Joined: 29 May 2008, 19:35
Has thanked: 4 times
Been thanked: 73 times

Re: General AI Suggestions

Postby tanthorjen » 02 Dec 2010, 02:27

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
tanthorjen
DEVELOPER
 
Posts: 23
Joined: 25 Nov 2010, 08:45
Has thanked: 1 time
Been thanked: 2 times

Re: General AI Suggestions

Postby MageKing17 » 02 Dec 2010, 03:10

tanthorjen wrote: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.
User avatar
MageKing17
Programmer
 
Posts: 473
Joined: 12 Jun 2008, 20:40
Has thanked: 5 times
Been thanked: 9 times


Return to General Programming

Who is online

Users browsing this forum: No registered users and 1 guest


Who is online

In total there is 1 user online :: 0 registered, 0 hidden and 1 guest (based on users active over the past 10 minutes)
Most users ever online was 279 on 11 Jul 2013, 22:03

Users browsing this forum: No registered users and 1 guest

Login Form