• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
dimovich

Tetris AI Algorithms

12 posts in this topic

I'm developing a tetris clone that provides the option to play against a computer. The bots are written in a C-like scripting language so that anyone could modify the bot AI. Currently there is only one bot available, and it is rather dumb. I would like to ask if anybody knows of any clever tetris AI algorithms that could do some more advanced stuff. Thanks.
0

Share this post


Link to post
Share on other sites

Hi,

I once developed a tetris playing 'ai'. I'm quoting it on purpose, because it actually was a relatively simple algorithm. On average, it would die after ~50k lines made. Here's how it works:

- your playing field has a number edges. The ground and sides are edges too.
- your current tetris block has edges.
- each edge is one (1) tetris unit wide and long. Normal tetris blocks consist of 4 blocks, but this algo also works with random tetris blocks.
- for any given rotation and position of your block, drop it downwards
- when dropped, count the number of edges on your block that are touching the edges of block already dropped or those which are touching the wall or ground.

If you implement this algo, you will see it will start building in 'V' shaped formations of blocks. To avoid it building too much formations on the sides, penalize height. So for any given rotation and position of blocks, the score is this:

(number of edges touching) - (average block heigth / total height).

This algo is by no means perfect, but believe it or not, that's an advantage. Because it makes 'mistakes', you will also get some gaps in your formation. This will promote dropping blocks that eliminate several lines at once, resulting in more points.

Hope this helps,

Edo

0

Share this post


Link to post
Share on other sites
BTW: if you want something more advanced, you could come up with some scoring criteria for your blocks, like

- height
- number of edges touching
- width
- number of empty gaps made
- number of edges touching a wall

Your overall score for dropping a block at a given rotation and position will then be:

score =
(weight1 * height) +
(weight2 * number of edges touching) +
(weight3 * width) +
(weight4 * number of empty gaps made) +
(weight5 * number edges touching a wall);

All weights are floating points between -1 and 1.

You can encode these weights in a genome (or was it chromosome?), and have a GA evolve these weights by letting a pool of chromosomes play against eachother for 10 games or so. The 'least' strong chromosomes will be killed, while the stronger weights will cross-over and mutate.

just some thoughts,

Edo
0

Share this post


Link to post
Share on other sites
Quote:
Original post by edotorpedo
- number of edges touching
Edo


We were using this one and this one only and it was working very good for us.
0

Share this post


Link to post
Share on other sites
this is one of those problems that you can create the AI strategy to use the same strategy you use. when i play tetris i use the strategy of building up (and fitting) blocks on the left side first. they reach rather dangerously high. but i work my way to the right when i can, fitting the blocks in the blocks as high as necessary to the far left trying to leave no gaps. so after a while the whole area looks similar to a somewhat straight hill sloping steeply to the right, leaving me several areas to fit almost any piece given to me without leaving more than even a couple of gaps. this strategy really works great, until the speed of the falling blocks increases, which is just plain hard anyway.

i would almost suggest representing the playing field as a 2D matrix full of 0's and 1's. in my case, i would start off building up blocks to the left with a general rule to minimize unreachable gaps. and then when the AI was given a new piece it would identify its shape and identify which one of the surfaces below (and preferrably to the left side) would minimize gaps for each of the 4 rotations.

this is just peusado of what i would do. i could come up with some math formulas that i would use that properly weighs height of heightest block, potential for clearing a certain row, best fit position, etc. but i think it would be better for you to approach this using your own strategy. if you just happen to play tetris like i do then i'll be happy to help you. but like i initially suggested, this is one of those simplified problems that you could just make the AI do exactly what you would do in that situation. if it comes to it, write down the steps of how you would play tetris, convert it to how an AI would come to those conclusions of each step, and write the code.

or if all of this is too complex for your liking, i'm sure there are simpler algo's out there.
0

Share this post


Link to post
Share on other sites
This would be an interesting problem for a neural network... it is overkill if you're just creating a single AI, but if you had it learn from 50 different players it would adapt each person's style... :)

You know you've written a good AI when it can win at Bastard Tetris!

http://www.happypenguin.org/show?bastet (Somewhere out there theres a Windows port too)
0

Share this post


Link to post
Share on other sites
Thanks for your advices. You really gave me some clever ideas.
My current bot uses this formula:

merit = rowsEliminated;
merit += -1*cellsOccupied;
merit += -5*holesShadowed;
merit += -4*pileHeight;

There are some minor issues with it but overal it does
fine. The NN ideas seems interesting. Bastard Tetris
looks promising :).

My project is open source. After I release it
I hope there will be enough people willing to write
their own Tetris AI.

[Edited by - dimovich on May 5, 2006 3:10:12 AM]
0

Share this post


Link to post
Share on other sites
Couldn't you develop a recursive possibilities-exploring algorithm similar to the algorithm used to look ahead n number of chess moves?
0

Share this post


Link to post
Share on other sites

Well, not similar to a chess algo, as that is a turn based game. And you only know the next tetris block that is going to fall, not the one after that.

So you can only recurse 2-deep (one for the current block, one for the next block). But by using my algo and recursing, I think you can achieve reasonably decent results, say ~100k lines.

Let me know if you finish your clone.

Edo
0

Share this post


Link to post
Share on other sites
Quote:
Original post by edotorpedo
You can encode these weights in a genome (or was it chromosome?), and have a GA evolve these weights by letting a pool of chromosomes play against eachother for 10 games or so. The 'least' strong chromosomes will be killed, while the stronger weights will cross-over and mutate.


A friend and I did this for a project in one of our AI classes. We built a simple Tetris repesentation (I say representation because it wasn't a game, you couldn't play, or even watch, but we could spit out the board when we wanted to in ASCII form :) ), and the used a GA to weight an evaluation, much like you described.

Our work was motivated by Colin Fahey... who's site seems to be down right now, but if you google for him you'll find all kinds of stuff. Using 3 or 4 features we got an agent that could play up to 100K lines, but on average much less than that.

We didn't spend a lot of time hand modifying the weights, but my point is that an evaluation function like that works pretty well for Tetris, and you can have some fun with learning algorithms with it too :).
0

Share this post


Link to post
Share on other sites
Quote:
Original post by edotorpedo

Well, not similar to a chess algo, as that is a turn based game. And you only know the next tetris block that is going to fall, not the one after that.

So you can only recurse 2-deep (one for the current block, one for the next block). [...]


Actually, you can do better than that. You define whatever your utility function is (a combination of height and holes, for instance). Let's call the current block block0, the next block (known) block1, the one after that (not known) block2, etc. The algorithm goes:
Loop over each position where you can place the block0 {
Loop over the 7 possible shapes for block2 {
Find the best utility you can get by placing block1 and block2.
}
Take the average of those 7 utilities, and that's the utility of placing block0 in that position.
Keep the position that has the maximum utility so far
}


This way, you are thinking 3 moves ahead. This can be extended using a recursive formulation to think even further ahead, although the branching factor of 7 is going to kill you quickly.

An interesting place to use neural networks would be in the utility function. You can try to define a bunch of things that might be relevant for the utility function, like maximum height, minimum height of a column, number of gaps, number of blocks on top of gaps... Then you build a neural network that tries to predict, using those numbers, how long you are likely to survive, or how many more points you are likely to score, or whatever else is what you really want to maximize. Now that you have a smart playing bot, you can generate plenty of data points to train your network. So start with a simple hand-made utility function and gather training data for the network with it. After a while, you can train the network, replace your utility function with the new network and start all over again. After a few iterations of this process you should have a really good player.

Too bad I don't have time these days to try this type of thing myself!

[Edited by - alvaro on May 8, 2006 11:26:27 PM]
0

Share this post


Link to post
Share on other sites
Damn, what a great feeling :)...

My bot managed to score 80k completed lines. And it is a simple, 1-piece algorithm, whith no advanced stuff in it.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0