Hi every body! Check out my program Tetris Analyzer (windows/x86). It starts in "step mode", press <F1> for instructions, 'S' to quit (toggle) step mode: http://www.sendspace.com/file/fvwnsr. Unzip it and run TetrisApp.exe. It makes 1,800,000 lines in average in level 1 (only knowing the falling piece) in a 10x20 grid, and it hasn't died any time in level 2 (knowing the falling piece and the next piece), made over 90,000,000 lines and it took almost eight days on my 2.8 Ghz Pentium, screen shot: http://www.sendspace.com/file/8yfwlw. When I have time, I will release it as open source on SourceForge. /Joakim Tengstrand
Here comes a short description of the algorithm: The most important part of the "AI" is the evaluation method. It measures different characteristics of the 10x20 grid (hope you understand, my english isn't perfect). In level1, when only taking the falling piece in concideration, it tries every possibly move, and lets the evaulation method measure the "equity" (the term equity is stolen from Back gammon and means "value") of the possition. The best move is then picked. Two properties are measured in the possition: 1) Gaps: Code: 5 *----------* 4 *----------* 3 *xx---x----* 2 *x-xxxx---x* 1 *x-xxxxx-xx* ************ 1234567890 The (2,3) block (x=2, y=3) is in the way for the first and the second row. The "penalty" is based on how completed the rows 1-3 are. A row can consist of 1-9 blocks = 10-90% completed. 2) Outline: The other thing that is measured is the outline structure. Example: Code: 5 *x---------* 4 *x----x----* 3 *x----x----* 2 *x---xx----* 1 *xxxxxx--xx* ************ 1234567890 It mesures "areas with same with". In this example it finds these areas: (2,5)-(0,5) (2,4)-(5,3) (2,2)-(4,2) (7,4)-(0,2) (7,1)-(8,1) Wider area = less penalty More narrow area = more penalty That is the algorithm in short.
Good, but not great. Its algorithm is too slow & too defensive. http://dtet.web.infoseek.co.jp/dtet/ga/dtcptr/ It is fast, but defensive.
Try these settings... Next: off Level: 1 Sliding: off Animate: off Delay: 0 Frame Delay: 20 ...and the speed will increase to over 10,000 pieces per second on my machine (Pentium 2.8 Ghz) and I don't call that slow! The DOS version made 19,500 pieces/sec. If you make the algorithm more offencive, the program will "die" sooner and get less points (if you are counting points instead of pieces). When the pieces is falling fast, in for example the original Game Boy Tetris, you don't have time to think of making Tetris'. Colin Fahey http://www.colinfahey.com/tetris/tetris.html is comparing different Tetris Algorithm's by look at how many lines they make in average in level 1. I think this is a good way of ranking Tetris programs. But, maybe you are right that it is more fun to see the computer making four lines rather than only one or two!
I'd love to see an AI playing under lots of restrictions. Stuff like 20G and T.A. Death speeds add constraints which should simplify greatly reduce valid placement options. You'd have to avoid superhuman things... For example, at high speed Death you can't often use the piece preview to influence the active piece. The overall placement plan must be made before the preview can be seen. Really, you can only tweak the final placement decision. You also can't triple tap a piece right or left without a lock reset. An AI with that sort of human touch, and that went for Tetrises, would be interesting indeed.
I use a Linear congruential generator http://en.wikipedia.org/wiki/Linear_congruential_generator. Here is the code: Random.h: Code: #ifndef __random__ #define __random__ class Random { private: unsigned int seed; public: Random(); Random(unsigned int seed); ~Random(); void setSeed(int seed) { this->seed = seed; } unsigned int getRandom(); int getRandomP(); }; #endif Random.cpp: Code: #include "Random.h" Random::Random() { this->seed = 0; } Random::Random(unsigned int seed) { this->seed = seed; } Random::~Random() { } unsigned int Random::getRandom() { seed *= (unsigned int)(1664525); seed += (unsigned int)(1013904223); return seed; } int Random::getRandomP() { unsigned int seed = getRandom(); return seed % 7 + 1; }
@tengstrand: 1. question: uhm - might be just a strange coincidence - but: are you jean luc pons who programmed blockoutII? because he uses exactly the same random generatror for blockoutII... 2. your AI is much better than that piss-stupid quickly coded from www.gravytris.de. Great work! i will learn from you. that said - please post here again if you release your source code sometimes. i can only watch learn from you. @colourtthief: if you ask for such things - 20g etc - then we might as well ask tengstrand to code a complete clone i am sure it will be great! there are never enough tetris clones. every one has its own highlights. and tengstrand's would be especially great regarding intelligent computer opponents.. imagine: a computer, forced down in speed by limiting his abilities in placement speed (limited sideways speed or whatever), but still able to beat you because he much more cleverly places pieces. that would be humiliating ...
No, Im not jean luc pons. Joakim Tengstrand is my real name. I have had some contact with Colin Fahey in the past (before he closed down his site), and I decided to use the same random generator as in his "Standard Tetris", i took the algorithm from him, just placed in into my code. I haven't worked with the code since 2003 because I have worked with a object oriented scannerless parser generator instead (own design). If any one out there can find a better Tetris algorithm, please add a reply here! /Joakim Tengstrand
Linear congruential generators? It is not good. once upon a time, there was stupid programmer. He made Random number generators. (maybe he used linear congruential generators) but............... http://www.youtube.com/watch?v=TGMV8s8TtJY http://en.wikipedia.org/wiki/Linear_con ... es_of_LCGs If you want to use Linear congruential generators, I think it need replace return seed % 7 + 1; to int rndn; rndn=(seed % 7000 / 1000) + 1; return rndn; If you don't want to use Linear congruential generators, Shall we use Mersenne twister? http://www.math.sci.hiroshima-u.ac.jp/~ ... index.html
There are some people here who feel that MT is slow an innefficient. I've not yet looked into it hard enough to determine such findings for myself.
Mersenne Twister is fast, but it generates numbers in batches of 600-odd. Batches are bad if you're trying to develop real-time software, where you time everything for the worst case rather than the average case. Granted, this would affect a handheld more than a PC.
In practical Tetris gameplay, doesn't the higher-level duplicate avoidance algorithm ("TGM Randomizer", "Guideline Random Generator") matter more than the lower-level random number generator itself? I mean, we're not doing government-grade cryptography or anything, they all look random enough to the human eye.
