Using PageRank to play Tetris
Tetris is one of the classic video games created in the 1980s that revolutionized the video game industry. The goal is to fit randomly chosen blocks onto a given surface and eliminate as many complete rows as possible before the blocks overflow the screen. This simple rule generates great complexity and challenges the sharpest minds in accuracy and responsiveness. This begs the questions: Can a computer do a better job than a human? Which algorithm is the most efficient? Is there a limit to the algorithm? These questions led one avid gamer to create a code for fun to play Tetris based on Google’s PageRank.
The PageRank algorithm was originally designed by Google to rank websites in search engine results. According to Google, “PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.” Basically, the algorithm works by treating each backlink to a webpage as an up-vote. Extra weight is given to the vote if it came from a webpage with a high rank. The algorithm then runs iteratively so the rank of all related webpages can be updated. In the Tetris code, a similar method is used. The stack surface at any given moment is ranked from “least accommodating” to “most accommodating”. Given surface B is created after a block is placed on surface A, surface B is an -up-vote for surface A. Weight is given to A if B is a high rank. The highest rank corresponds to the flat surface. The algorithm is allowed to iterate so all ranks are updated before each move. Also, the same surface with different heights are still considered as having the same rank. This reduces the combinations of different surfaces and improves the efficiency of the algorithm. Is this a good algorithm for a self-playing Tetris? This seems like an efficient algorithm for Tetris due to its simplicity and efficient data representation. The completion of the algorithm is preceded by cataloging and ranking all possible surfaces in Tetris (it turns out there are effectively 43046721 different stack surfaces). However, after the surfaces are properly catalogued, each step simply corresponds to checking the rank in a catalog and playing accordingly. PageRank algorithm turns out to be a fun and interesting way of playing Tetris.
Source:
http://www.ryanheise.com/tetris/tetris_artificial_intelligence.html
http://en.wikipedia.org/wiki/Tetris
https://en.wikipedia.org/wiki/PageRank