Hello I''m making a Tetris clone, and I want to implement a versus cpu mode. Does anyone know how can I create the AI for the CPU?

A reasonable idea would be to take the current state of the game, take the new block and create a series of potential new game states with the block in every position under every rotation. Then analyse each of these new world states with a heuristic and pick the best one (for difficulty levels, you can pick the best one for the hardest difficulty, pick randomly between the best two to make it easier, between the best three for an even easier level etc.).
For heuristics you could use several criteria which would become obvious when you play the game yourself.
Examples would be...
...the new game state that has the lowest height of blocks in each column (this could be average height, lowest single colum height or highest single column height).
...the new game state that completes a line
...the new game state that leaves the least number of empty gaps blocked by higher level blocks

To make the AI better you could look at all the potential new game states for the next two blocks with the same heuristic or even the next three or more blocks. To be honest there''s nothing wrong with the AI cheating if it makes for a good game.

Mike

You should add the possibility of AI moving blocks too slowly. Most human players can usually say what place is best (or at least good) for new block, but when the game gets too fast you just don''t have time to move it there.

You could make the decision like MikeD suggested and even evaluate states for few following blocks (using all the possible block combinations, not the ones actually coming). When the speed is slow you could evaluate for example three levels of blocks and when it gets faster you would reduce the number of levels
evaluated.

It is also very likely that the AI will be too good compare to player if you don''t let it make mistakes.

-Ratsia

If you have ever read the Xanth novels by Piers Anthony, you know of the character "Com Puter" If not, here is something. Com Puter is totally logical. A girl tried to teach him Solitare and Freecell. However, she couldn''t do so. It turned out that he had to know how to win in order to play. So, you have to program the victory conditions, so the computer can work with it. However, attempt a skill slightly under yours, or you would tie. (Unless theorhetically, you act in desparation, an emotional feeling. In which the computer would be unable to match your level.)

Generally you generate a search tree with expanding branches of game states - and in the end you backtrack to find what way to go. An interesting idea would then be to make the response time of the ai proportional to the depth (ply expanded to reach the actual move made) of the search. Thereby you emulate the fact that sometimes the ai "sees" the solution directly, and sometimes it doesn''t.

keywords : A*, puzzle solving, depth first search, breadth first search ...

there are some good tutorials about all this on the internet, and I guess a tetris is really just a puzzle. The problem is that with an algorithm like A*, the PU would just wipe your a$$ without a problem ... you''d have to implement some sort of "mistakes" ...

youpla :-P

The best page I have found about AI in games is Amit''s Game Programming Information... I recommend you check it out.


-Chris Bennett ("Insanity" of Dwarfsoft)

Check our site:
http://www.crosswinds.net/~dwarfsoft/
Check out our NPC AI Mailing List :
http://www.egroups.com/group/NPCAI/
made due to popular demand here at GDNet :)

same here. Amit''s is the place to be if you are interested in pathfinding.
But for the case here, I would also read more "classical" material, as taking an A* algorithm and applying the underlying logic to a puzzle is NOT the easiest task.
You might want to check out the "PAwn captures Wyvern" article on Gamasutra, but it''s quite high level. The best thing would be to find an online course in some university (stanford, carnegie ? never remember which one).

youpla :-P

dwarfsoft : if it''s 23:15 here in France, it''s around 12:00 on the west coast ... but what time is it in Australia ?

what i ever miss in computers AI is ambition. Never ever a computer tries to make it better next time. I can imagine it must be horrible to implement that, but I'm too new in programming (or designing) AI to get an idea of the amount of problems...

just an impulse

Scott me up, Beamy!!!

Edited by - CarLos on August 4, 2000 5:48:18 PM