Lövetris - another impossible tetris

[Lövely]

Hello everyone. Just like Numandina, I came to Löve by way of a job interview. I was chocked at first by the lack of types and brackets, but I soon learned to love it! I call my solution (to what has to be the same challenge) Lövetris:

https://www.dropbox.com/s/40cfq3yf3ryl4 ... 0Life.love

My algorithm uses three different factor to score each potential piece, and ranks them accordingly. It will then give you a piece whose rank corresponds to your level (1-7), so in level 4 you will always get the 4th best piece.

You can get a good idea about how my algorithm works by toggling debug mode within the game, by pressing d. You can then press m to move the piece around manually, or f to see how the search algorithm that checks (almost) all possible placements works. In debug mode you can also press S, Z, O, L, T, I or J to get the piece with that shape. These letters are also used in the scoring list at the to of the screen in debug mode.

In the game over screen there is a kind of game-in-the-game. You can draw with the mouse and change colors with the szoltij keys, and erase with x. Get rid of the menu text with m. Stop time with d and speed up with the down key.

CHALLENGE: Can you figure out what is actually going on in the in-game game, without checking the code?

The code is not overly commented, but I use long, descriptive objective c-style names of functions and variables, so it should be pretty easy to follow along and to modify. Please don't post it online without attribution, though.

/Güstäf

[numandina]

Wow, amazing implementation by the looks of it. Going to check the code on what exactly is going on but I noticed you can beat the computer even in the most difficult setting, using a scenario like this:



This is probably due to the algorithm only looking one step in advance.

Also regarding difficulty level, instead of having 1-7 giving the best through worst pieces, why not make it so these these are weights that influence the piece being chosen. For example diff 1 gives 100% chance of getting best piece, 7 gives 100% chance of getting worst piece, diff 3 gives weights 10%, 35%, 40%, 5%, 5%, 5%, 0% or something similar, and so on? I think this is better for randomization.

Great work and hope you got the job haha.

[Lövely]

Thanks for taking the time to look at it, and the nice comments.

It is true that the AI is possible to beat, I think you would probably have to several steps ahead to prevent that, as you said. My ambition was more modest! It would be cool to look several steps ahead but of course more complex to program and take exponentially longer to compute.

Löve seems pretty fast though, I was able to run my complete search for next piece 2000 times in one second, so it should be possible to look at least one or two steps ahead with a clever algorithm.

Regarding difficulty levels, I had actually implemented that system at first, with 100 difficulties and weighting the chances for the next piece, but then I thought that since the player will remain within the same difficulty for the duration of a game (the only thing that changes over time is the speed) there was not that much reason to over complicate it. Also, I actually wanted to avoid randomization, to make comparisons between players easier!

It will be interesting to examine your code and see what we did similar and what was different!