5 ms·
Solving Tetris in C
- a3_nm 15y agoIt would be nice to provide the game tree for the 10x20 case. If it's not too big, then it would be an easy way to check the result of your experiment. Even if it's big, it would probably be fun to navigate.
- zbanks 15y agoHis current implementation runs out of memory on a board less than half that size. Good luck ;-P
- a3_nm 15y agoAh, right, so the real problem is still open. :-) I didn't examine the code very carefully, but here are some sensible things that you could do and that I'm not sure you're currently doing: - Are you doing alpha-beta pruning? http://en.wikipedia.org/wiki/Alpha-beta_pruning http://en.wikipedia.org/wiki/Alpha-beta_pruning - Instead of either caching everything or nothing, choose a cache size, cache things and flush the least used ones when the cache is full. (More intelligent things are possible there.) - Explore the player moves in a clever order to avoid getting bogged down in useless branches. You could use an existing tetris AI to pick sensible moves for you and examine them first, or use simple heuristics. - In the same spirit, since you seem to be using an exact but complicated (and costly) way to compute possible player moves, it might make sense to first explore a subset of moves which is easier to compute. For instance, examine first the moves which are just an horizontal movement, a rotation, and a straight drop. Maybe there is a winning strategy for the player which mostly uses such moves. - I am not sure of what you cache. There is no point in caching the whole well, just caching the lines with a reachable empty space. Also, hitting any configuration from the cache is deadly (since it means we went higher and went back to an equivalent configuration). Hopefully this is sensible and isn't stuff you already do. I'd be quite interested to know the definitive answer to this problem. :-)
- qntm 15y agoAlpha-beta pruning sounds like a reasonable route forward. In this case, each "well" is a state in the game and placing a new piece in the well constitutes a move to a new state. Since the "heuristic value" of a move is absolute (player wins or AI wins), I already have stuff in place to exit early from an exhaustive evaluation of all possible landing points if a definitive answer is found. But I don't have anything in place to put those landing points into an optimal order for evaluation purposes. A Tetris-playing AI which can quantify the "goodness" of a move would be useful here, and that's entirely possible. Intelligent caching is possible but I think it would be difficult for me to implement and I'm not certain that it would yield much benefit. Actually, the procedure for identifying all the possible player moves is very fast already and I think making it prioritise "easier" moves would slow it down. In particular, ruling out or de-prioritising simple things like "tucking" a piece under another is very counterproductive.
- qntm 15y agoI'm afraid the game tree for W10xH5 is over 2 gigabytes and I'm pretty sure the number of possibilities increases faster than exponentially in H!
- Xk 15y agoFor those that care, a few years ago some researchers proved Tetris is NP-complete for many problems. http://arxiv.org/abs/cs.CC/0210020 http://arxiv.org/abs/cs.CC/0210020
- algolicious 15y agoThe paper tells us that Brzustowski and Burgeil already showed that a loss is forced for alternating S and Z pieces. But it is easy to see that you can get 1 line with S and Z simply by putting the thick part in the middle, and this is all the author wants.
- Xk 15y agoYeah, I realize that -- I'm just saying, for people who want to read more on the subject of Tetris there is a lot out there.
- deleted 15y ago[deleted]
- CGamesPlay 15y agoIn the method pseudocode for player_can_always_force_win, the player has full control over which piece will appear next (i.e. the pseudocode in its current form should be called player_can_possibly_win). I think it should read: BOOLEAN player_can_always_force_win(well w) { for each piece p { BOOLEAN player_will_win = FALSE for each landing state of piece p in well w { well w2 = result if( that_makes_a_line(w2) or player_can_always_force_win(w2) ) { player_will_win = TRUE } } if (!player_will_win) { // If the AI selects this piece, the AI wins return FALSE } } // There is no piece the AI can select that will cause the player to lose return TRUE }
- qntm 15y agoYou are correct. I updated it to this: who_wins(well W) { for each piece P { for each landing state of piece P in well W { well W2 = result if(that_makes_a_line(W2)) { next piece } if(who_wins(W2) == PLAYERWINS) { next piece } } // AI wins every landing state return AIWINS } // Player wins every piece return PLAYERWINS } print who_wins(empty_well)
- T-R 15y agoIt might be a good idea to look at it as an induction problem - one state leads to another, and since a lot of states are effectively the same, it means the tree can be pruned. Let's say the player has a row that's almost full - say, one spot left to fill all the way on the right. That means the AI needs to not give the player any block that would let him fill it (I,J,L,S,T) - so the player can force the AI to just give him O and Z blocks. If the hole isn't against the wall, the AI can only give O blocks. There are only a few, if any board states where the player cannot create a line using only O and Z blocks - the player just needs to make sure he doesn't loosen the restriction on the AI (such as by covering the hole). If the hole is 2-wide, depending on the hole's depth, the AI may only be able to give T blocks, if even that, and for most board states, you'll probably find that T blocks can be used to make a line without loosening the restrictions on the AI.
- Iv 15y agoYou have 10 columns and you need to consider at least 4 rows, to account for the possibility to make a line. That means 2^40 different possible states, and I think that most of them are reachable with the rules of Tetris. It could still be implemented with a hash_table and yield interesting results, but it is still possible to fill up the memory with such an algorithm. Before using such an approach, I think it would make sense to find a compressed way of representing a state. I think it would be workable to have ten "heights" describing the enveloppe of the structure and to add 3 bits to describe the presence of "holes" in the 3 bottom lines (the presence of holes in the top line can be inferred in the enveloppe information). That would give us 2 bits of height per column, plus 3 bits for hole presences. 2^23 : a more manageable state space of 8 millions. Such a representation is not enough to have a good AI or to even make a completely evil AI but it fills the bill when it comes to solve the problem at hand : "prevent the player from making even a single line"
- qntm 15y agoYou're suggesting using 2 bits to store the height of the column, plus 3 bits to store the presence of holes, for a total of 5 bits per column. Exactly how you got from that to a figure of "2^23" I don't know. That's actually (2^5)^10 = 2^50 possible column combinations. Why not just use 4 bits to represent the whole column? That's (2^4)^10 = 2^40, exactly where we started. In fact, look at rows instead. With 10 columns and 4 rows there are, to be more precise, (2^10 - 1)^4 possible states. And the majority of which have "floating" (disconnected) sections which, while reachable with the rules of Tetris, cannot be reached without making at least one line. In case you didn't read the article, Tetris has been solved for width 10 height 4: the AI wins. The same is true for width 10 height 5. We need to go further.
- emillon 15y agoBastet is an open source Tetris clone that is based on a similar concept : http://fph.altervista.org/prog/bastet.shtml http://fph.altervista.org/prog/bastet.shtml
- hammock 15y agoInteresting that the player starts winning earlier in the smaller width wells as opposed to the larger ones. I wonder why that is.