Thursday, March 21, 2013

Artificial intelligence for Tetris

Let's look on artificial intelligence applied to Tetris game. First, we need a base code to run the game. Here is a minimalistic version you can test, it can be controled by keyboard:

Basic indeed, but some clarification could be useful. Tetris has a lot a different implementations, but by his evolution, some relevant rules of gameplay are now well settled. These rules are listed as a Tetris Guideline. The main rules I implemented are the following:
  • official rotations are respected
  • infinite rotation (tetrominos are not falling while rotating)
  • wall kick (automatic left/right shifting allowing rotation of a tetromino against a wall)
  • 7 system random generator (fill a bag with the 7 tetrominos ; then draw each by random, and fill it again when empty)
  • ghost piece is visible
  • 3 next tetrominos are in preview
  • quick fall (you can accelerate the falling speed of your current tetromino)
  • hard drop (you can throw your current tetromino directly at the bottom of playfield)
  • you have a delay to shift your tetromino between the last fall movement and the lock
  • the game speed can be modified
  • you loose when a tetromino lock while overlaping one the 2 top lines

I think I forgot some little rules, but here is the essential. On the artificial intelligence side, I early took some crucial decisions:

  • "fair-play". It means that everything the AI can do, the player can do. No cheat, no special moves for the AI. Briefly, the AI acts on the game with exactly the same controls as a human player and has no more informations that what can be seen on the screen
  • on the other side, the AI has a direct access to the game datas during the game. The AI doesn't "see" the game states by analyse of the pixels on the screen, but by introspection of the datas building the game model (but always in a fair-play manner, no more datas that can be seen on screen)
  • the AI has to run in real time, in such way a human can play against

Here is my first working version:

It is very efficient, even if not tweaked very precisely. But it can be much more impressive. For example if I put the game speed at maximum and allow the AI to proceed the hard drop movement:

If you are very patient, you could see the AI failing and triggering the game over. But it is actually a very good basis to build some interesting AI behaviors to challenge a human player in Versus game.

1 comment: