Help, I want to implement an AI in my Tetris game but there aren't many good resources about it and I can't figure out what this guy is talking about: http://www.vidarholen.net/contents/junk/tetris/
When a piece drops, it simple goes through all rotations and horizontal movements of these to find the place where it's best to drop, for some definition of best. In this case is the total mass of the board where the weight of each square is the cubed distance from the top, minus a big penalty for each covered hole. That didn't say much, I suppose. Let me try again: for each non-empty square (x,y), sum up y^3. Subtract the number of empty squares with a filled square over it (ie, they are unreachable by dropping blocks).
Besides the first paragraph being slightly nonsensical, I get lost at "Subtract the number of empty squares with a filled square over it". Does that mean to take the total number of empty squares that are unreachable, and subtract that number from each y^3 that I calculate? And then after I've done this for each non-empty square, am I meant to choose the highest value or lowest value to drop onto?
Name:
Anonymous2010-06-08 3:41
Need more informations
What sort of data structure are you using for the shapes?
Are you using a Tile based layout?
maybe show us some code/pseudo code,
Name:
Anonymous2010-06-08 3:43
same anon that posted about more info-
Just a tip, 4chan isn't really the best place to go for this sort of thing, there are great online communities elsewhere on the webs that could help out much better
Name:
Anonymous2010-06-08 4:13
>>2,3
His question is fairly simple, I don't think that information is necessary. >>1
From my reading of the article: Does that mean to take the total number of empty squares that are unreachable, and subtract that number from each y^3 that I calculate?
Yes And then after I've done this for each non-empty square, am I meant to choose the highest value or lowest value to drop onto?
Since you are subtracting for all the unreachable blocks, it's safe to assume that you would choose the highest.
Name:
Anonymous2010-06-08 4:15
>>4
Let me clarify that "yes". You do not calculate y^3 for the empty squares, only the filled squares and then you subtract the empty ones.
Name:
Anonymous2010-06-08 7:14
Subtract the number of empty squares with a filled square over it #
###
>>1
I've coded some tetris ai as well. Its fairly simple to make a very strong Tetris AI. Just simulate all possible placements and 'score' the resulting board, then choose the placement with the best score. Pretty much any scoring function that minimize holes and chasms will work.
Here's what I came up with:
int n=0;
for(int r=0;r<numRows;r++){ //starts from the top row, -1 means empty
for(int c=0;c<numCols;c++){
if(board[r][c]!=-1){
for(int z=1;z<numRows;z++){
//scans under each block for holes and penalize
if(z+r>=numRows||board[z+r][c]!=-1)
break;
n+=5;
}
}else{
//penalizes chasms by checking for blocks bordering holes
if(c>0&&board[r][c-1]!=-1)
n++;
if(c<numCols-1&&board[r][c+1]!=-1)
n++;
}
}
}
return n;
This is very simple scoring function plays nearly perfectly.
>>8 nearly perfectly.
Perfect tetris play can be achieved relatively easily. If you cannot find a probabilistic evaluation function to play optimally perhaps you should reconsider your career choice.
The ai was a small part of a long forgotten networked tetris game.
It would probably fail very quickly against a hateful piece generator. I just ran it a few times again and its ok against a regular generator. Average games seem to be a few thousand pieces.
Name:
oh2010-06-08 19:13
I came up with this:
static int score_grid(uint8_t * grid) {
int score = 0, penalty = 0;
int row, column;
// Find the penalty of this grid
for (row=0; row < GridH; row++) {
for (column=0; column < GridW; column++) {
if (grid[TILE(column,row)]) { // cell is not empty:
int z;
for (z=1; z+row < GridH; z++) {
if (z+row >= GridH || grid[TILE(column,row+z)] != 0) {
break;
}
++penalty;
}
} // Penalize chasms too?
}
}
for (row=0; row < GridH; row++) {
for (column=0; column < GridW; column++) {
if (grid[TILE(column,row)]) { // cell is not empty:
score += (row * row * row) - penalty;
}
}
}
return score;
}
But my shit is broked. I haven't figured out whether it is this function or the calling function (where I score all grids against each other) that is broken.
>>14
man, I can't believe I didn't wrap the y in parentheses. Thanks for pointing that out.
In any case, that didn't seem to fix the problem. The AI just keeps forcing the pieces over to the right side (although it has started to drop the T piece over to the left, and he slowly works his way to the middle of the screen). Example: http://i47.tinypic.com/2q3dxyc.png
I'm pretty sure the problem is not in the calling function.
>>15
Your scoring doesn't seem valid... try one or the other(minimize holes or height) before combining them.
Name:
Anonymous2010-06-09 0:44
Ok,it turned out I was doing something stupid in my calling function after all. I fixed that, and it stopped hoarding pieces to the right like a piece of crap.
But it still doesn't play properly, like the Java applet does in the OP link. It usually manages to clear a row before getting pwnt.
try one or the other(minimize holes or height) before combining them
Not sure what you mean. Try it without penalties for blocked cells? Actually, I'm not even sure that ++penalty is enough weight per blocked cell.
Thanks for help so far. I'll try to think about what could be wrong with the scoring, and try to figure out if it's just not giving the right inputs for some reason.
Anyways, I sorted that out, and now the only problem left is that it develops an inability to place tetris pieces at the farthest left cell (ie. column 0). If it would do that, it would play just fine. I'll continue debugging... maybe it's a problem with its ability to send input.
>>19
Ah, it was due to something stupid involving the way I store tetris pieces in memory. All is well now. AI managed to get to level 11 just now... It's far from perfect but it plays well enough to be an "easy mode" AI. I just need to improve the scoring system in order to improve the AI I guess.
Name:
Anonymous2010-06-09 12:41
>>9 Perfect tetris play can be achieved relatively easily. If you cannot find a probabilistic evaluation function to play optimally perhaps you should reconsider your career choice.
Hey pal, didn't you know that Tetris is NP-Complete?
>>21
Actually, no. Only full-information games of tetris (where the player can see the identity and order of allf future pieces) is proven to be NP-Complete.
Name:
Anonymous2010-06-09 15:20
>>11
If this game was called Tetris NET 2 and had sound effects in the preference dialog box, we have not forgotten you sir
The AI plays really awesome when penalty += (row * row * row) (y^3, just like scoring), but at level 5 last time it decided to start piling shit onto the left for some reason :|
>>24
Basically it creates a large gap (often at one side but sometimes closer to the middle) and then it will create a huge tower beside the gap instead of putting anything in it.
Name:
Anonymous2010-06-10 15:27
http://www.gamedev.net/community/forums/topic.asp?topic_id=391139 - 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).
Can anybody figure out what total height is supposed to be there? The sum of the height of each filled block? It would seem to mean that, but when I calculate the average block height I am already dividing the total height by the number of blocks, and dividing the average by the total height again just gives me a really small number that wouldn't influence anything. I wish people wrote coherently on forums.
>>8
Why +5 penalty for blocking a hole and +1 per neighboring chasm? Or did you just choose those as examples? Because I think those numbers are much too small, when the scoring is row3 per filled block.
>>28
They are completely arbitrary, I just tried a couple numbers until I got a balance I liked. As this thread shows, there are many approaches to make a passable AI. I didn't do any explicit penalization for height(except for boards that overflowed).
Name:
Anonymous2010-07-07 1:10
>>9 find a probabilistic evaluation function to play optimally