#47558 - musicman3320 - Sun Jul 10, 2005 10:14 pm
Hi all. I was wondering if someone knows of a good AI tutorial for games. I am writing a tetris spin off, but I don't know how to write an AI. Does anyone know a good place to learn how to write AIs? I assume that this is the right category, since I don't think it fits anywhere else. If it should be asked elsewhere, please let me know. Thank you in advance for any help.
-Chris
#47562 - sajiimori - Sun Jul 10, 2005 10:45 pm
Beyond the usual advice regarding finite state machines (used them yet?), AI is very game-specific.
If the AI is controlling something that could also be controlled by a player (as I would expect in a player-versus-AI game of Tetris), one of the key ideas is to write your game logic so that you can "plug in" either a human controller or an AI controller, leaving everything else the same.
To do that, make a list of all the things that the player can do. Then make an easy way to send those commands to the game and have it respond correctly. For instance:
| Code: |
enum Command
{
CMD_DO_NOTHING,
CMD_MOVE_LEFT,
CMD_MOVE_RIGHT,
CMD_ROTATE_LEFT,
CMD_ROTATE_RIGHT,
CMD_SNAP_TO_BOTTOM,
};
void executeCommand(int playerNum, Command);
|
After you have a simple interface that responds to all the commands, you start writing a program that produces interesting commands (the AI). It's traditionally in the form of a state machine, but coroutines are an attractive alternative (enough so that I hardly ever write state machines anymore). The interface to the AI might look like this:
| Code: |
Command makeDecision(AIState*);
|
The AIState object contains everything the AI needs to know in order to make a decision. For Tetris, it presumably needs to know the state of the board, the active shape and its location, and possibly the next shape in the queue. (If it wants to be a real bugger, it might want to know the state of the opponent's board so it can set up well-timed attacks.)
If you'd like to talk AI sometime, message sajiimori on AIM. I've never written an AI for Tetris so it would be fun to discuss.
#47567 - Miked0801 - Sun Jul 10, 2005 10:56 pm
Tetris would be a fun AI to write wouldn't it? Maybe we can make a 2p tetris clone as a minigame sometime :)
#48891 - quickcup - Sat Jul 23, 2005 8:17 pm
I have been working on a tetris clone that incorporates ai in one of its modes for almost four years now. It is nearing completion.
Here is a screenshot.
[Images not permitted - Click here to view it]
#48900 - ScottLininger - Sat Jul 23, 2005 10:25 pm
| Code: |
| Command makeDecision(AIState*); |
What would be really cool sometime would be a compo where contestants submit "makeDecision" routines that play against one another. Whoever writes the best AI wins the prize.
Of course, one would have to come up with some sort of fair way to determine how much processing power each AI has access to...
AI for Tetris would be a fascinating challenge.
-Scott
#48902 - tepples - Sat Jul 23, 2005 10:36 pm
| ScottLininger wrote: |
| Of course, one would have to come up with some sort of fair way to determine how much processing power each AI has access to... |
If the vcount interrupt fires before think() finishes, DQ. If think() writes to the interrupt control registers, DQ.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#48964 - Miked0801 - Sun Jul 24, 2005 9:41 pm
Or just use No$GBA's timing to see how long the think takes. Over X tics, DQ.
#48970 - tepples - Sun Jul 24, 2005 10:51 pm
| Miked0801 wrote: |
| Or just use No$GBA's timing to see how long the think takes. Over X tics, DQ. |
Which would require all judges to own a copy of NO$GBA (profiler edition). This could run more than the prize budget. It'd be easier to hack VBA to trap unauthorized writes to the interrupt registers.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#49023 - Kyoufu Kawa - Mon Jul 25, 2005 5:21 pm
I'll pass. I suck at AI :P
#49059 - APL - Tue Jul 26, 2005 2:28 am
| ScottLininger wrote: |
| Code: | | Command makeDecision(AIState*); |
What would be really cool sometime would be a compo where contestants submit "makeDecision" routines that play against one another. Whoever writes the best AI wins the prize. |
That would be a really fun contest! Count me in!
It might also be good for programmers new to the GBA (Such as myself) as all the graphics would be taken care of by the supplied code.
The interesting question would be should the contest revolve around a real-time game like "Tetris" or something turn based? Real-time would probably be more exciting, but "chess on GBA hardware" might be an interesting problem.
_________________
-Andy L
http://www.depthchasers.com
#49062 - sajiimori - Tue Jul 26, 2005 3:01 am
For the purposes of AI, realtime and turn-based are identical. "What should I do this tick?" is the same question as "What should I do this turn?" The AI doesn't care how fast the turns are playing out in reality.
Of course, the shorter the turns are, the less CPU you have to work with, but it's not a fundamental difference.
#49064 - DekuTree64 - Tue Jul 26, 2005 3:31 am
Yeah, I'd be in for a compo like that. Preferrably in about a month, when I'd actually have time to work on it...
Maybe give each MakeDecision around 100K cycles (out of 280896 per frame) to work with, so about 1/3 of the frame. Should leave plenty for the game to run with music and cool SFX when your AI opens up a can of whup-ass on the other :)
Then maybe half of EWRAM, 14KB of IWRAM, and 256KB of ROM. That way we could put all the entries in a single ROM and make a nice menu to select 2 people and watch them go at it.
Heck, just designing the game to run the AI players would be loads of fun
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#49079 - quickcup - Tue Jul 26, 2005 6:57 am
I can supply the engine and maybe the interface.
Here is a demo of my engine with two players instantiated using the same AI.
Press a key to start it.
http://fast.filespace.org/quickcup/game.zip
#49149 - ScottLininger - Tue Jul 26, 2005 9:07 pm
Your linky, she is broken. :(
Uh, at least for me. :)
-Scott
#49159 - tepples - Tue Jul 26, 2005 11:58 pm
| DekuTree64 wrote: |
Maybe give each MakeDecision around 100K cycles (out of 280896 per frame) to work with, so about 1/3 of the frame. Should leave plenty for the game to run with music and cool SFX when your AI opens up a can of whup-ass on the other :)
Then maybe half of EWRAM, 14KB of IWRAM, and 256KB of ROM. |
28 KiB of IWRAM used by the AIs? How much would that leave for the game engine and especially the audio mixer?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#49166 - DekuTree64 - Wed Jul 27, 2005 1:20 am
| tepples wrote: |
| DekuTree64 wrote: | | Then maybe half of EWRAM, 14KB of IWRAM, and 256KB of ROM. |
28 KiB of IWRAM used by the AIs? How much would that leave for the game engine and especially the audio mixer? |
Eh, 4KB should be plenty for a mixer and a couple of other misc routines. I don't think it would be too difficult to get the engine running with a 4 channel mixer in about 28% CPU, so more IWRAM should go to the AIs, since they'll probably be hard-pressed to keep up.
Maybe that should be more like 12KB per AI though, to leave more room for the stack.
EDIT: On second thought, the mixer would need a bit of EWRAM for the output buffer, so I guess each AI would get 127KB there :)
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#49276 - APL - Thu Jul 28, 2005 1:28 am
| tepples wrote: |
| Miked0801 wrote: | | Or just use No$GBA's timing to see how long the think takes. Over X tics, DQ. |
Which would require all judges to own a copy of NO$GBA (profiler edition). This could run more than the prize budget. It'd be easier to hack VBA to trap unauthorized writes to the interrupt registers. |
It actualy might require the contestants to have it too. It'd be tough to push your AI right to the edge if you couldn't accurately measure to see if you were within the rules.
_________________
-Andy L
http://www.depthchasers.com
![[Images not permitted - Click here to view it]](http://img320.imageshack.us/img320/9931/poly7zc.jpg){kind=link}