4 ms·
We had to do something similar for our Intro to CS course at Tufts years ago: implement both a tic-tac-toe game and an algorithm that would play optimally. Seco
by sfRattan 7y ago
We had to do something similar for our Intro to CS course at Tufts years ago: implement both a tic-tac-toe game and an algorithm that would play optimally. Second stage of the project was that, after a player's third move, the oldest "X" or "O" would disappear each turn. I have no idea if they still use that project, but the feeling when your computer player started working and you couldn't beat it was like nothing else, and was one of the reasons I went into CS rather than Economics.
- tcgv 7y agoI also had to implement a Tic Tac Toe "AI" when I was in college about a decade ago. Last year I was revisiting my college files backup and decided to upload it into GitHub: - https://github.com/TCGV/TicTacToe https://github.com/TCGV/TicTacToe. The AI player was implemented using the Minimax algorithm, and can never be beaten ;)
- gnulinux 7y agoSorry very tangential. One time I wrote something like this, and shared on reddit. Like you, I used minimax to solve tic tac toe. My comment was downvoted to oblivion and one highly upvoted person wrote: > You don't need "AI" to solve tic tac toe, it's a solved problem!
- user5994461 7y agoAnd here's a picture of the solution. https://xkcd.com/832/ https://xkcd.com/832/ Could fit on a sheet of paper indeed.
- praptak 7y agoSomeone actually implemented a tic-tac-toe player in Reddit comments using character graphics and cross-comment links.
- tcgv 7y agoDamn... Even though it truly is a solved problem, it's much more intuitive (and fun) to implement a tic-tac-toe solver from scratch using minimax than any lookup tables heuristic. Since it is a generic solution, I believe the minimax solver can also be easily modified to implement an "AI" player for that Roman version of the game as well, where pieces are removed. By the way, using minimax was also one of that college task requirements!
- abhgh 7y agoBrings back memories. I think implementing an AI for tic-tac-toe was one of my first complete implementations of a RL algorithm; circa 2008, I think :)