The topic winning the vote in class on March 27th was a distributed tetris game, likely in teams with one team’s wins causing setbacks for the other team.
Flatris is a variant of Tetris where two players play against one another. Each has their own Tetris board, with all the regular Tetris rules, with one exception: if your opponent clears a row it doesn’t just vanish: it has one random cell cleared and then is added to the bottom of your board. Instead of points for speed, number of cleared rows, etc, this is a Boolean-score game: you win if your opponent loses.
Course staff will provide a working Flatris server. You will provide a bot, a game AI that plays on this server. Your goals is to make your bot indistinguishable from a human player. That will definitely need to include pauses between actions: humans can’t press keys anywhere near as fast as bots can.
You have two programming tasks:
Initial files are available in project.zip, including one file you’ll edit: bot.py
. You will also need a copy of your MP10 solution, and will further edit tetris.py
.
You may change any of the provided files freely and may include other .py files in your solution if you wish. The comments in the provided bot.py
file indicate where we expect most students will want to work.
The provided Makefile has five targets:
make bot
runs bot.py
in dev mode, showing errors and informational messages to the terminal.make tetris
runs tetris.py
in dev mode, showing errors and informational messages to the terminal.make both
runs both bot.py
and tetris.py
in dev mode, showing errors and informational messages from both to the same terminal. This can be handy for quick tests, but debugging might go better having make bot
and make tetris
in separate terminals so you can tell which messages are from which.make background
runs bot.py
in the background; it will keep running even after you close the terminal. This is intended for the May 12 checkoff, not for development and debugging.make stop
will stop the background run (and any other ongoing python instances).If you wish to use the provided submitcode.py
and have files other than tetris.py
and bot.py
that your code uses, edit the space-separated list of files on the third line of that file to submit them all.
MP10 creates a new game for each connecting WebSocket. To build a game-playing program you’re going to want to be able to watch the bot play. To achieve this watching ability, you’ll need to add a bit of code to your MP10.
The basic idea is to have two kinds of WebSockets:
/ws
, created by browsers with index.html
and by your bots./snoop
, created by the watch.html
distributed with this project.You’ll store a mapping between game-playing WebSockets and the game-watching WebSockets that are watching them. Any message you send to a game-playing WebSocket you also send to each game-watching WebSocket that is watching that game.
Instead of responding to left/right/etc, game-watching WebSockets accept two messages:
"?"
Prompts the game server to send a message to the watcher formatted like {"alive":[
…]}
, where the …
is replaced by a list of all active game IDs.
The provided starter code for MP10 used id(ws)
, where ws
is the game-playing WebSocket, to identify WebSockets in allws
; our chat1.py
in-class example used a global counter to assign IDs. It does not matter what format you pick: whatever you send here will be echoed back to pick what to view.
"?"
We won’t grade this change on correctness; if it has small errors that don’t prevent it being used to watch your bot at work that’s fine.
There are multiple ways to get watching to work. One possible avenue is outlined below.
Refactor1 To refactor
is to change the code without changing resulting behavior. Refactors can be easily tested by running the program before and after the change and verifying that it runs the same. your code to rename allws
as playws
.
Add a GET endpoint that returns the provided watch.html
. This may be modeled after the existing /
endpoint code. Verify that when you visit your new endpoint you see the watching page (which will not yet work).
Add a GET endpoint /snoop
that upgrades its request to a WebSocket. This may be modeled after the existing /ws
endpoint code.
Add the WebSocket to a new watchws
global that mirrors playws
, and remove it before retuning.
In shutdown_ws
, shut down all WebSockets in watchws
as well as those in playws
.
In /snoop
, when a TEXT message’s data is ?
, send a JSON object with key alive
and value being a list of all the keys in playws
.
Create a global mapping indicating which playing WebSockets are being watched by which watching WebSockets. This is initially empty.
In /snoop
, when a TEXT message’s data is (a textual representation of) the identifier of something in playws
both (a) remove any previous mapping between a playing WebSocket and the watching WebSocket and (b) add a mapping to the playing WebSocket with that ID. When removing the WebSocket from watchws
, also remove it from the mapping of watchers.
Refactor your code so that instead of calling send_json
directly, you instead call a new function you write that calls send_json
.
In the new function that calls send_json
, loop through any watchers of the recipient WebSocket and send the same message to each of them.
The starter code in bot.py
implements a particularly poor tetris bot. You can try it as follows:
tetris.py
bot.py
/ws
path of your tetris URLYou should then see this bot, which just waits a bit and then drops each Tetronimo. When the game ends you won’t see anything more happen until either (a) you refresh the watcher page or (b) your tetris code allocates a new game with an old ID.
You should modify this code as follows:
Add a reasonably-competent Tetris playing algorithm.
Your bot must be at least as good at Tetris as the following bot:
Starter Bot
When you get a message with next
in it (i.e. a new tetromino is on the board), pick a full sequence of moves as follows:
best; as a starter the
bestoption maximizes the sum of the y coordinates of the cells in the tetromino.
left
, right
, cw
, and/or ccw
commands to get the tetromino into that horizontal location and orientation, followed by drop
.We hope your bot is much better than the starter bot (likely by using a better heuristic), but doing at least this good is expected.
The most common measure of the goodness of a Tetris bot algorithm is the number of rows it can clear before it loses. The algorithm outlined above tends to clear between 1 and 5 rows. Clearing 20 is needed to send more rows to your opponent in Flatris than you keep yourself.
Add delays (and possibly mistakes) to make your bot seem human.
We’ll be running a Turing test as part of the final project check-off. Bots that play so fast you know they have to be a bot will not get points. Bots that play in a way that convinces other students it is a human instead will get prizes.
Prepare for Flatris
Flatris will mostly seem like Tetris to your bot, with the following exceptions:
There will be several types of "event"
s: you might win, or lose, or have your opponent disconnect. You can treat these all the same: the game is over.
Sometimes 1–4 new rows will be added at the bottom of the board, with everything above them moved up. This will arrive like any other "board"
, but is created by the other player clearing rows instead of anything you did.
Some messages will be JSON objects with none of the keys defined in MP102 We haven’t finalized the format of these messages, but they might be things like {"wait":0.3}
or {"other":{"board":[...]}}
. You can safely ignore these. They are indicating what the oponents board looks like, informing the web UI of wait times, and other bot-irrelevant information.
Flatris will have a gap between the WebSocket connecting and the game beginning. Messages sent by a bot (or human) before the game server sends its first message with live
in it will be ignored by the game server.
There have been many publications about Tetris AIs. The following are a few that I think you might find contain implementable ideas.
holesin detail, with suggestions on how to score and pick moves.
make background
Some students have found that make background
is not sufficient to keep their code running after they log out. This may be caused by a system setting, which can be modified to allow programs to run after you log out by running
loginctl enable-linger $(id -u $USER)
This should only be needed once: it permanently changes part of the VM setup.
All grading occurs based on detailed logs of what each bot and human does during the in-class checkoff on May 12th at 1:30pm. The following are required for full credit:
Your bot connects to our servers and plays Tetris.
Your bot does not play faster than a human can.3 Because we will have both human and bot logs, if your bot sends keys faster than the fastest human, we will judge it to be too fast
.
Your bot plays at least as well as the starter bot listed above (i.e. can beat our reference implementation of that algorithm at least half the time).
The code you have submitted by the end of class matches what your bot does.
You connect to our servers and play Tetris.
You attempt to identify which players are human and which are bots.
You don’t cheat during the graded part.
Cheating includes things like bots taking human input, humans taking bot input, creating custom WebSocket or HTTP messages in an effort to bypass the game logic or interrupt others games, etc.
After the main game play for grading we will dismiss students who are satisfied with how things went and run another set of games where cheating is permitted. These cheating-allowed games are just for fun and won’t be included in grading.