Tic tac toe

July Challenge: Noughts and Crosses and Cheating

You are an up and coming Youtuber. Your hard work of reading many books of the Youtube algorithm is finally paying off. You now have thousands of young impressionable fans who revere you and will never question your judgement.

You started your career by clickbaiting other youtubers, finding the "seed" of other, more popular, youtuber's video games. You have also gained popularity for your "TicTacToe Manhunt" videos, in which you try to beat Tic-Tac-Toe before your friend stops you.

Sadly, according to Youtube statistics, only a small percentage of your viewers are actually subscribed.

To help with that, you decide to make a new series: "Tic-Tac-Toe speedruns". You've gotten pretty good at the game, but it's tough, y'know. Speedrunning takes hours, and it's so..... luck-based. The RNG gods have not been kind, and you really need that "Speedrun World Record Sub-20" title for those sweet sweet views, so you have decided to use a modded client and make a bot that will play the tic-tac-toe game for you, one that would never lose and be faster than any human player! Besides, no one will know you cheated. If anyone finds out, you could always hire someone with a PhD to say you didn't cheat, or claim months afterwards that you "accidentally" used a modded client. Those fans of yours will believe anything.

Your job is to make a bot to win at least 500 games in the tic tac toe page within 20 minutes. The game can be found here. If that link doesn't work, try this link instead. If you are reading this in August, the links will no longer work, but I will release the backend code if you wish to host it yourself to try it out.

Out Of Universe

First off, please be careful to not spam my server so much that it drives my VPS costs high. Basically, just please check if I return an error, and if it is an error, don't send the same request again. Also, don't leave a bot running overnight or something. In my tests, it should take slightly over 10 minutes if your bot plays optimally. I would also appreciate it if your bot plays optimally all the time instead of just playing randomly until it, by some sort of dream-like luck, gets the 500 wins after spamming my server many times. Any algorithm can do (See Tic-Tac-Toe's Wikipedia page or elsewhere on the web for strategies), but I recommend the Minimax algorithm, which is a recursive algorithm that takes into account every single possible move and chooses the optimal move. Since Tic-Tac-Toe is a small game, with only a 3 by 3 board, this is completely feasible, as opposed to a game of chess or Go. The base case occurs when the board is completely occupied or one of the player wins. The heuristic value of the node is 1 for the player winning, -1 for the computer winning, and 0 for a tie. Each "children of node" is the possible next moves, taking into account whose turn it currently is. The pseudocode on wikipedia uses depth, but for tic-tac-toe this isn't strictly needed. If you're stuck, you can just search up online a tutorial on how to create an unbeatable Tic Tac Toe AI using Minimax.

When you visit the page, you have 20 minutes to get 500 winning games, after which you will get the flag. Once the 20 minutes are up, your scores reset to 0. I suggest writing a script to play for you, but if you manage to win 500 games in 20 minutes, I think you deserve it.

Hints

There are a few ways you can go about this. One way would be to check the network calls being done, and simulate that in your own program (e.g: a python script), and play the game until it wins 500 times. Another possible way would be to use the Developer tools of your web browser, and in Console section, code up some javascript to simulate the button presses and play the tic tac toe game. This could also be done in a userscript using an browser addon like Greasemonkey or Violentmonkey. I'm sure there are other ways too (using Selenium to play for you, or having a auto-clicker that simulates a mouse press and gets the screen framebuffer to keep track of taken spots, etc.)

Keep in mind, in both cases, I have spent a tiny bit of time making it a tiny bit harder for you. If making your own bot which makes network calls, make sure you simulate a web browser as accurately as possible (check your HTTP Headers), and also remember you need to ensure your calls are in the same session, otherwise your score won't be seen as done by the same user. Usually there is a built-in way to do this in most networking libraries, or you can manually make sure the cookies used are the same in subsequent network calls (the session id in this challenge implementation is in document.cookie and can be accessed via javascript, although in other cases it could be in the Http Header if HttpOnly is set).

Rate-limiting

I have enabled some basic rate-limiting to ensure my bill doesn't skyrocket. If you send more than 5 HTTP Requests per second to a particular page, it will return a 403 Error (Check the HTTP Status Code to see if it's 200, if it is, then it's okay. Otherwise it returns a page describing the error. If the error is in a JSON-format and the HTTP Status is still "200", this is a different type of error and there is no rate limiting done, and you're good to go.). If you get the 403 Error, wait for 10 seconds, and you should be able to send requests once more (may be longer, every subsequent request during the 10 second cooldown will add another 10 seconds, so be sure to wait.)

As a simple workaround, I suggest sleeping at least 200 milliseconds in between requests.

Additionally, depending on the traffic, I may add some more aggressive intrusion-detection systems this month (Not necessarily because of participants in this challenge, I've had this instance running for a few hours, and I have had 5 weird logs coming from around the world searching for exploits already; despite the fact that I haven't shared the URL to anyone.). So please do not do port scanning or running automated tools to find exploits in the webserver, brute-forcing SSH passwords, etc. This may be flagged as malicious behaviour and put you in the blocklist for 1 day.

If my server goes down or you find something you think is a bug, or if you believe your IP has been added to the blocklist and you wish to get unblocked immediately instead of waiting, feel free to email me at nrav0005 (at) student (dot) monash (dot) edu

Disclaimer: Note that the story is fictional and only just inspired by real events, satirising it. Don't look too deeply into it, I just thought it was funny to parody the situation. I don't know whether the real person this story is based on intentionally cheated or not; you can decide for yourself. The character in the story was just shown to be cheating knowingly to make it silly and funny.

Challenge Submission (Monash Students only)

Submit the flag you got here, and if you were the first person to get the flag, you will win a prize! You will be notified around the start of August if you had won.