title
Minimax Algorithm for Tic Tac Toe (Coding Challenge 154)
description
In this challenge I take the Tic Tac Toe game from coding challenge #149 and add an AI opponent for a human player by implenenting the Minimax algorithm. Code: https://thecodingtrain.com/challenges/154-tic-tac-toe-minimax
đšī¸ p5.js Web Editor Sketch: https://editor.p5js.org/codingtrain/sketches/0zyUhZdJD
đĨ Previous video: https://youtu.be/ZCXkvwLxBrA?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
đĨ Next video: https://youtu.be/R3C2giDfmO8?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
đĨ All videos: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
References:
đ Geeks for Geeks - Minimax Algorithm in Game Theory: https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/
đ Minimax on Wikipedia: https://en.wikipedia.org/wiki/Minimax
Videos:
đ Algorithms Explained - minimax and alpha-beta pruning: https://youtu.be/l-hh51ncgDI
đ´ Livestream Archive: https://youtu.be/rv98KUFtF9U
Related Coding Challenges:
đ #94 2048 Sliding Puzzle Game: https://youtu.be/JSn-DJU8qf0
đ #149 Tic Tac Toe: https://youtu.be/GTWrWM1UsnA
Timestamps:
0:00 Introduction to the challenge
2:17 Explanation of the Minimax algorithm
8:20 Start Coding
12:54 Check to see if anybody won
14:16 Recursively check the max score for all the spots (AI)
16:51 Recursively check the min score for all the spots (Human)
18:15 Refactor using min() and max()
19:05 Fix bugs
21:13 Final output
22:46 Ideas and Suggestions
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
đ Website: http://thecodingtrain.com/
đž Share Your Creation! https://thecodingtrain.com/guides/passenger-showcase-guide
đŠ Suggest Topics: https://github.com/CodingTrain/Suggestion-Box
đĄ GitHub: https://github.com/CodingTrain
đŦ Discord: https://discord.gg/hPuGy2g
đ Membership: http://youtube.com/thecodingtrain/join
đ Store: https://standard.tv/codingtrain
đī¸ Twitter: https://twitter.com/thecodingtrain
đ¸ Instagram: https://www.instagram.com/the.coding.train/
đĨ Coding Challenges: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
đĨ Intro to Programming: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6Zy51Q-x9tMWIv9cueOFTFA
đ p5.js: https://p5js.org
đ p5.js Web Editor: https://editor.p5js.org/
đ Processing: https://processing.org
đ Code of Conduct: https://github.com/CodingTrain/Code-of-Conduct
This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecodingtrain.com/issues/new
#beginners #tictactoe #minimaxalgorithm #games #p5js #javascript
detail
{'title': 'Minimax Algorithm for Tic Tac Toe (Coding Challenge 154)', 'heatmap': [{'end': 546.159, 'start': 521.236, 'weight': 0.789}, {'end': 797.799, 'start': 781.107, 'weight': 0.723}, {'end': 893.102, 'start': 809.408, 'weight': 0.882}, {'end': 1290.536, 'start': 1281.992, 'weight': 0.727}], 'summary': 'Presents a coding challenge for a tic-tac-toe game with a minimax algorithm, including human interaction and a random computer picker, demonstrating the implementation of the algorithm, visualization of outcomes, scoring mechanism, decision-making process, and potential game optimization.', 'chapters': [{'end': 60.026, 'segs': [{'end': 26.466, 'src': 'embed', 'start': 0.169, 'weight': 0, 'content': [{'end': 4.072, 'text': 'Hello, and welcome to a coding challenge, Tic-Tac-Toe.', 'start': 0.169, 'duration': 3.903}, {'end': 6.593, 'text': 'Oh, with the minimax algorithm.', 'start': 4.091, 'duration': 2.502}, {'end': 7.394, 'text': "That's why I'm here.", 'start': 6.613, 'duration': 0.781}, {'end': 13.838, 'text': "Because I made this other coding challenge, Tic-Tac-Toe, where I created a kind of a big, it was kind of a mess, if I'm being perfectly honest.", 'start': 7.674, 'duration': 6.164}, {'end': 19.302, 'text': 'But I made a working version of the Tic-Tac-Toe game that just played with two players picking random spots.', 'start': 13.878, 'duration': 5.424}, {'end': 26.466, 'text': 'So since then and you can check one of my live streams if you want to find where I did this I made some adjustments to it so that I could,', 'start': 19.602, 'duration': 6.864}], 'summary': 'Coding challenge: tic-tac-toe with minimax algorithm, improving from previous version.', 'duration': 26.297, 'max_score': 0.169, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ169.jpg'}, {'end': 60.026, 'src': 'embed', 'start': 36.831, 'weight': 2, 'content': [{'end': 44.856, 'text': 'Owens So what I have, the adjustment that I made, is that I added a mouse pressed function where I find where did I click.', 'start': 36.831, 'duration': 8.025}, {'end': 46.717, 'text': 'And I put my human.', 'start': 45.296, 'duration': 1.421}, {'end': 51.5, 'text': 'variable, which is the letter O, onto the board.', 'start': 49.118, 'duration': 2.382}, {'end': 60.026, 'text': "And then I call next turn, where next turn picks a random spot in the board and makes that the AI spot or X's spot.", 'start': 51.82, 'duration': 8.206}], 'summary': "Added mouse pressed function to place 'o' on the board and implemented next turn to pick a random spot for the ai or x", 'duration': 23.195, 'max_score': 36.831, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ36831.jpg'}], 'start': 0.169, 'title': 'Tic-tac-toe coding challenge', 'summary': 'Presents a coding challenge for a tic-tac-toe game with a minimax algorithm, including the addition of human interaction and a random computer picker, demonstrated through a live stream.', 'chapters': [{'end': 60.026, 'start': 0.169, 'title': 'Tic-tac-toe coding challenge with minimax algorithm', 'summary': "Presents a coding challenge where the speaker discusses the development and adjustments made to a tic-tac-toe game, including the addition of a mouse-pressed function, allowing human interaction, and the implementation of a random computer picker. the game is demonstrated through a live stream, showcasing the speaker's ability to play against the ai.", 'duration': 59.857, 'highlights': ['The speaker made adjustments to a Tic-Tac-Toe game, including the addition of a mouse-pressed function for human interaction and the implementation of a random computer picker.', 'The speaker demonstrated playing the game against the AI through a live stream, showcasing the functionality and interaction of the developed game.', 'Initially, the speaker had created a version of the Tic-Tac-Toe game that was played with two players picking random spots.']}], 'duration': 59.857, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ169.jpg', 'highlights': ['The speaker demonstrated playing the game against the AI through a live stream, showcasing the functionality and interaction of the developed game.', 'The speaker made adjustments to a Tic-Tac-Toe game, including the addition of a mouse-pressed function for human interaction and the implementation of a random computer picker.', 'Initially, the speaker had created a version of the Tic-Tac-Toe game that was played with two players picking random spots.']}, {'end': 449.014, 'segs': [{'end': 109.208, 'src': 'embed', 'start': 81.521, 'weight': 2, 'content': [{'end': 85.964, 'text': 'And if you want to learn more about the Minimax algorithm, I would suggest two resources that you can look at.', 'start': 81.521, 'duration': 4.443}, {'end': 88.546, 'text': 'that I actually looked at before beginning this coding challenge.', 'start': 85.964, 'duration': 2.582}, {'end': 92.169, 'text': "I haven't programmed this before, but I watched this video by Sebastian Laig.", 'start': 88.566, 'duration': 3.603}, {'end': 97.234, 'text': "that explains the minimax algorithm, also something called alpha-beta pruning, which I'm not going to implement,", 'start': 92.629, 'duration': 4.605}, {'end': 99.217, 'text': 'but could be a good exercise next step for you.', 'start': 97.234, 'duration': 1.983}, {'end': 104.102, 'text': 'And I also found this article on the geeksforgeeks.org website,', 'start': 99.597, 'duration': 4.505}, {'end': 109.208, 'text': 'which has a three-part series about the minimax algorithm and how to apply it to tic-tac-toe.', 'start': 104.102, 'duration': 5.106}], 'summary': 'Resources for minimax algorithm: video by sebastian laig and article on geeksforgeeks.org', 'duration': 27.687, 'max_score': 81.521, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ81521.jpg'}, {'end': 254.463, 'src': 'embed', 'start': 224.366, 'weight': 4, 'content': [{'end': 227.188, 'text': 'O could go here, or O could go here.', 'start': 224.366, 'duration': 2.822}, {'end': 228.609, 'text': 'And look at these.', 'start': 227.909, 'duration': 0.7}, {'end': 231.671, 'text': 'In this case and this case, O has won.', 'start': 228.889, 'duration': 2.782}, {'end': 235.814, 'text': "Remember, we're trying to solve for the optimal move for x.", 'start': 231.731, 'duration': 4.083}, {'end': 237.095, 'text': 'x is making the first turn.', 'start': 235.814, 'duration': 1.281}, {'end': 241.439, 'text': 'So this means I can mark these where O wins as red.', 'start': 237.576, 'duration': 3.863}, {'end': 244.494, 'text': 'I was like, those are bad outcomes.', 'start': 242.773, 'duration': 1.721}, {'end': 248.498, 'text': "So while these are not terminal states, there's only one move possible for x.", 'start': 245.155, 'duration': 3.343}, {'end': 250.56, 'text': 'So I could draw an arrow and put that down here.', 'start': 248.498, 'duration': 2.062}, {'end': 254.463, 'text': 'But ultimately, I can just consider this as x has to go here.', 'start': 250.88, 'duration': 3.583}], 'summary': "Analyzing tic-tac-toe game, x to make optimal move based on o's wins.", 'duration': 30.097, 'max_score': 224.366, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ224366.jpg'}, {'end': 291.087, 'src': 'embed', 'start': 267.694, 'weight': 0, 'content': [{'end': 276.359, 'text': 'So how does x pick which path to go down? where we can see here that the goal is for x to win the game, to get to here, here, or there.', 'start': 267.694, 'duration': 8.665}, {'end': 282.523, 'text': 'How does it do that? And the way that it does that, and by the way, spoiler alert, this is the move it should pick.', 'start': 276.68, 'duration': 5.843}, {'end': 283.923, 'text': 'It should just win instantly.', 'start': 282.543, 'duration': 1.38}, {'end': 291.087, 'text': 'But the idea of the minimax algorithm is, if we can score every possible outcome,', 'start': 284.704, 'duration': 6.383}], 'summary': 'Using minimax algorithm, x aims to win the game by scoring every possible outcome.', 'duration': 23.393, 'max_score': 267.694, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ267694.jpg'}], 'start': 60.366, 'title': 'Implementing minimax algorithm in games', 'summary': 'Discusses the implementation of the minimax algorithm to find the optimal next move for the ai in games, with a focus on its application in tic-tac-toe, demonstrating visualization of outcomes, scoring mechanism, and decision-making process for players, with references to learning resources.', 'chapters': [{'end': 117.372, 'start': 60.366, 'title': 'Implementing minimax algorithm for ai', 'summary': 'Discusses the implementation of the minimax algorithm to find the optimal next move for the ai in a game, with references to learning resources on the algorithm and its applications.', 'duration': 57.006, 'highlights': ['The Minimax algorithm is implemented to find the optimal next move for the AI, aiming for the computer player to beat or tie the human player in the game.', 'Recommended learning resources for understanding the Minimax algorithm and its application include a video by Sebastian Laig and a three-part series on geeksforgeeks.org.', 'The video by Sebastian Laig explains the Minimax algorithm and alpha-beta pruning, while the geeksforgeeks.org series focuses on applying the Minimax algorithm to tic-tac-toe.']}, {'end': 449.014, 'start': 117.552, 'title': 'Minimax algorithm in tic-tac-toe', 'summary': 'Explains the application of the minimax algorithm in a tic-tac-toe game, demonstrating the visualization of possible outcomes, scoring mechanism, and decision-making process for the maximizing and minimizing players.', 'duration': 331.462, 'highlights': ['The minimax algorithm is applied to visualize all possible outcomes of the tic-tac-toe game based on the starting configuration, demonstrating the decision-making process for the maximizing and minimizing players. Visualization of possible outcomes, decision-making process for maximizing and minimizing players', 'Scoring mechanism for the tic-tac-toe game is explained, where winning is assigned a score of plus 1, losing a score of negative 1, and tying a score of 0, showcasing the quantifiable scoring system in the algorithm. Scoring mechanism, quantifiable scoring system', 'Explanation of the maximizing and minimizing players in the minimax algorithm, where the maximizing player aims to achieve the highest possible score, while the minimizing player aims to minimize the score, highlighting the strategic decision-making process in the algorithm. Maximizing and minimizing players, strategic decision-making process']}], 'duration': 388.648, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ60366.jpg', 'highlights': ['Recommended learning resources for understanding the Minimax algorithm and its application include a video by Sebastian Laig and a three-part series on geeksforgeeks.org.', 'The video by Sebastian Laig explains the Minimax algorithm and alpha-beta pruning, while the geeksforgeeks.org series focuses on applying the Minimax algorithm to tic-tac-toe.', 'The minimax algorithm is applied to visualize all possible outcomes of the tic-tac-toe game based on the starting configuration, demonstrating the decision-making process for the maximizing and minimizing players.', 'Explanation of the maximizing and minimizing players in the minimax algorithm, where the maximizing player aims to achieve the highest possible score, while the minimizing player aims to minimize the score, highlighting the strategic decision-making process in the algorithm.', 'Scoring mechanism for the tic-tac-toe game is explained, where winning is assigned a score of plus 1, losing a score of negative 1, and tying a score of 0, showcasing the quantifiable scoring system in the algorithm.', 'The Minimax algorithm is implemented to find the optimal next move for the AI, aiming for the computer player to beat or tie the human player in the game.']}, {'end': 618.512, 'segs': [{'end': 546.159, 'src': 'heatmap', 'start': 490.222, 'weight': 0, 'content': [{'end': 497.348, 'text': 'If I ever get to an endpoint, return the score and have that score backtrack up or ripple back up the chain.', 'start': 490.222, 'duration': 7.126}, {'end': 499.43, 'text': "So let's see if we can write the code to do this.", 'start': 497.629, 'duration': 1.801}, {'end': 503.252, 'text': 'So this here is the place where I want to write the new code.', 'start': 500.271, 'duration': 2.981}, {'end': 510.173, 'text': 'Currently, a move is chosen by picking a random available spot, and I no longer want to do that.', 'start': 503.632, 'duration': 6.541}, {'end': 513.594, 'text': "So I'm actually going to change the name of this function to best move.", 'start': 510.453, 'duration': 3.141}, {'end': 516.434, 'text': "And I don't need to worry about what's available.", 'start': 514.313, 'duration': 2.121}, {'end': 520.436, 'text': 'I just want to actually look at all the possible spots.', 'start': 516.715, 'duration': 3.721}, {'end': 530.024, 'text': 'So basically, I just want to know, is the spot available? If the spot is available, I want to try going there.', 'start': 521.236, 'duration': 8.788}, {'end': 533.907, 'text': "So I'm going to say board, i, j is the AI player.", 'start': 530.044, 'duration': 3.863}, {'end': 536.75, 'text': 'And then I want to call minimax on the board.', 'start': 534.288, 'duration': 2.462}, {'end': 540.413, 'text': 'Why do I want to call minimax? Because I want to get what is the score.', 'start': 537.03, 'duration': 3.383}, {'end': 546.159, 'text': 'I want minimax to return to me the score for this particular move.', 'start': 541.074, 'duration': 5.085}], 'summary': 'Changing the code to evaluate all possible moves and get the score using minimax algorithm.', 'duration': 50.191, 'max_score': 490.222, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ490222.jpg'}], 'start': 449.254, 'title': 'Implementing minimax algorithm for game ai', 'summary': 'Discusses implementing the minimax algorithm for game ai, emphasizing the use of a tree diagram and recursive algorithms to determine the best move, while addressing the need to track scores and handle game board alterations.', 'chapters': [{'end': 618.512, 'start': 449.254, 'title': 'Implementing minimax algorithm for game ai', 'summary': 'Discusses implementing the minimax algorithm for game ai, emphasizing the use of a tree diagram and recursive algorithms to determine the best move, while addressing the need to track scores and handle game board alterations.', 'duration': 169.258, 'highlights': ['The chapter discusses implementing the minimax algorithm for game AI, emphasizing the use of a tree diagram and recursive algorithms to determine the best move. The author explains the concept of implementing the minimax algorithm for game AI, highlighting the use of a tree diagram and recursive algorithms to determine the best move.', 'Addressing the need to track scores and handle game board alterations. The author emphasizes the importance of tracking scores and dealing with game board alterations while implementing the minimax algorithm for game AI.']}], 'duration': 169.258, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ449254.jpg', 'highlights': ['The chapter discusses implementing the minimax algorithm for game AI, emphasizing the use of a tree diagram and recursive algorithms to determine the best move.', 'Addressing the need to track scores and handle game board alterations.']}, {'end': 1285.354, 'segs': [{'end': 664.064, 'src': 'embed', 'start': 633.627, 'weight': 0, 'content': [{'end': 638.989, 'text': "So minimax is always going to return the score of 1, meaning it's not going to be able to pick.", 'start': 633.627, 'duration': 5.362}, {'end': 641.53, 'text': "They're all going to be a tie, so it's always going to pick the first one.", 'start': 639.249, 'duration': 2.281}, {'end': 643.371, 'text': "But let's see how that goes.", 'start': 641.791, 'duration': 1.58}, {'end': 648.554, 'text': 'Next turn is not defined, because I called it best move.', 'start': 644.992, 'duration': 3.562}, {'end': 652.819, 'text': "And it's in one more place here in Setup.", 'start': 650.638, 'duration': 2.181}, {'end': 656.841, 'text': 'OK, it went there.', 'start': 656.1, 'duration': 0.741}, {'end': 664.064, 'text': "Watch, it's going to go to the next available spot, to the next available spot, to the next available spot.", 'start': 657.161, 'duration': 6.903}], 'summary': 'Minimax always returns a score of 1, resulting in tie outcomes. the algorithm consistently picks the first available spot.', 'duration': 30.437, 'max_score': 633.627, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ633627.jpg'}, {'end': 809.408, 'src': 'heatmap', 'start': 781.107, 'weight': 0.723, 'content': [{'end': 783.449, 'text': "I'm pretty sure I already have a check winner function.", 'start': 781.107, 'duration': 2.342}, {'end': 785.69, 'text': "That's something that I wrote in the previous coding challenge.", 'start': 783.469, 'duration': 2.221}, {'end': 786.751, 'text': 'Let me double check that.', 'start': 785.871, 'duration': 0.88}, {'end': 789.794, 'text': 'Check winner.', 'start': 789.173, 'duration': 0.621}, {'end': 791.595, 'text': 'The winner is null.', 'start': 789.814, 'duration': 1.781}, {'end': 794.717, 'text': 'And then by the end, it returns a tie.', 'start': 792.576, 'duration': 2.141}, {'end': 797.799, 'text': 'It returns null, a tie, or the winner.', 'start': 794.957, 'duration': 2.842}, {'end': 806.146, 'text': "So the score is, and let's make a little lookup table that's basically exactly what I wrote here.", 'start': 798.34, 'duration': 7.806}, {'end': 808.207, 'text': "If x wins, it's a 0.", 'start': 806.766, 'duration': 1.441}, {'end': 809.408, 'text': "If o wins, it's a negative 1.", 'start': 808.207, 'duration': 1.201}], 'summary': 'The check winner function returns null, a tie, or the winner, with a score of 0 for x wins and -1 for o wins.', 'duration': 28.301, 'max_score': 781.107, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ781107.jpg'}, {'end': 896.265, 'src': 'heatmap', 'start': 808.207, 'weight': 1, 'content': [{'end': 809.408, 'text': "If o wins, it's a negative 1.", 'start': 808.207, 'duration': 1.201}, {'end': 814.497, 'text': "If it's a tie, it's a 0.", 'start': 809.408, 'duration': 5.089}, {'end': 817.598, 'text': 'All right, so this is my lookup table for what the score then.', 'start': 814.497, 'duration': 3.101}, {'end': 819.218, 'text': "And again, it's a very simple scenario.", 'start': 817.858, 'duration': 1.36}, {'end': 820.678, 'text': "There's only three possible scores.", 'start': 819.238, 'duration': 1.44}, {'end': 829.4, 'text': 'If the result is not equal to null, the score is the number associated with this particular.', 'start': 821.258, 'duration': 8.142}, {'end': 830.46, 'text': 'Oh, it got rid of those.', 'start': 829.42, 'duration': 1.04}, {'end': 832.021, 'text': "I didn't need those quotes.", 'start': 830.68, 'duration': 1.341}, {'end': 834.181, 'text': 'Visual Studio Code just cleaned that up for me.', 'start': 832.501, 'duration': 1.68}, {'end': 834.901, 'text': 'Thank you very much.', 'start': 834.241, 'duration': 0.66}, {'end': 837.562, 'text': 'The score is based on whoever won.', 'start': 835.341, 'duration': 2.221}, {'end': 838.722, 'text': 'And then I can return that.', 'start': 837.722, 'duration': 1}, {'end': 842.137, 'text': 'So this would be the terminal condition.', 'start': 840.014, 'duration': 2.123}, {'end': 850.247, 'text': "If I am calling minimax on this particular board configuration at this particular depth and it's an end state.", 'start': 842.798, 'duration': 7.449}, {'end': 852.17, 'text': "if it's a terminal state, just return the score.", 'start': 850.247, 'duration': 1.923}, {'end': 853.391, 'text': "That's what I'm supposed to do.", 'start': 852.43, 'duration': 0.961}, {'end': 864.594, 'text': "If it's not a terminal state, If it's not this state and I can't just return the score, I need to check all the possible next moves.", 'start': 856.535, 'duration': 8.059}, {'end': 866.594, 'text': 'So I got this wrong, actually.', 'start': 865.254, 'duration': 1.34}, {'end': 873.175, 'text': 'The next move, this is the AI player trying a spot, their move.', 'start': 866.794, 'duration': 6.381}, {'end': 876.136, 'text': 'So the next move is actually not the maximizing player.', 'start': 873.415, 'duration': 2.721}, {'end': 877.536, 'text': 'This should be false.', 'start': 876.636, 'duration': 0.9}, {'end': 879.577, 'text': "But I'm going to write this as if it is.", 'start': 877.956, 'duration': 1.621}, {'end': 887.698, 'text': "So if it's the maximizing player, I can copy paste that from above, check all the possible spots again.", 'start': 880.197, 'duration': 7.501}, {'end': 893.102, 'text': "If it's available, try.", 'start': 890.18, 'duration': 2.922}, {'end': 896.265, 'text': "Now that's the human, right? Oh, no, this is the AI.", 'start': 893.983, 'duration': 2.282}], 'summary': 'Developing a simple ai algorithm with three possible scores and terminal conditions for a game.', 'duration': 88.058, 'max_score': 808.207, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ808207.jpg'}, {'end': 904.691, 'src': 'embed', 'start': 880.197, 'weight': 3, 'content': [{'end': 887.698, 'text': "So if it's the maximizing player, I can copy paste that from above, check all the possible spots again.", 'start': 880.197, 'duration': 7.501}, {'end': 893.102, 'text': "If it's available, try.", 'start': 890.18, 'duration': 2.922}, {'end': 896.265, 'text': "Now that's the human, right? Oh, no, this is the AI.", 'start': 893.983, 'duration': 2.282}, {'end': 901.989, 'text': "I'm confused because currently the way I'm stepping through this, in my mind, it's O's turn.", 'start': 896.585, 'duration': 5.404}, {'end': 904.691, 'text': "But I'm writing the code for both, whether it's X's turn or O's turn.", 'start': 902.009, 'duration': 2.682}], 'summary': 'Discussed confusion between ai and human player, code being written for both x and o turns.', 'duration': 24.494, 'max_score': 880.197, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ880197.jpg'}, {'end': 1030.022, 'src': 'embed', 'start': 1001.366, 'weight': 2, 'content': [{'end': 1003.888, 'text': "But if it's the maximizing player, check all the spots.", 'start': 1001.366, 'duration': 2.522}, {'end': 1007.207, 'text': 'find the best possible outcome, and return it.', 'start': 1004.965, 'duration': 2.242}, {'end': 1011.39, 'text': 'But call minimax recursively at the next future move.', 'start': 1007.767, 'duration': 3.623}, {'end': 1018.315, 'text': "And then here, I'm going to start, right? The minimizing player wants to find the best score for it, which is the lowest score.", 'start': 1011.45, 'duration': 6.865}, {'end': 1020.876, 'text': "So and that's the human player.", 'start': 1019.055, 'duration': 1.821}, {'end': 1030.022, 'text': 'And if the score is less than the best score, and then return that best score.', 'start': 1021.837, 'duration': 8.185}], 'summary': 'Minimax algorithm for maximizing and minimizing player in a game.', 'duration': 28.656, 'max_score': 1001.366, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ1001366.jpg'}, {'end': 1110.9, 'src': 'embed', 'start': 1085.207, 'weight': 5, 'content': [{'end': 1090.17, 'text': 'Minimax Minimax, Minimax.', 'start': 1085.207, 'duration': 4.963}, {'end': 1093.492, 'text': "I don't know what this extra code is in here.", 'start': 1090.19, 'duration': 3.302}, {'end': 1095.513, 'text': 'And Minimax, OK.', 'start': 1094.532, 'duration': 0.981}, {'end': 1098.154, 'text': 'Oh, yes.', 'start': 1097.433, 'duration': 0.721}, {'end': 1104.657, 'text': "Simon is pointing out something to me which is great, which I don't need this if statement to find the best score.", 'start': 1098.654, 'duration': 6.003}, {'end': 1105.777, 'text': 'The whole point of this Minimax.', 'start': 1104.897, 'duration': 0.88}, {'end': 1110.9, 'text': "And also, this is a great chance for me to use the min function and the max function because it's the Minimax algorithm.", 'start': 1105.797, 'duration': 5.103}], 'summary': 'Implementing minimax algorithm using min and max functions.', 'duration': 25.693, 'max_score': 1085.207, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ1085207.jpg'}], 'start': 619.98, 'title': 'Implementing minimax algorithm for game ai', 'summary': 'Involves writing the minimax function to always return a score of 1, resulting in the first available spot being picked. it covers implementation for a turn-based game ai, including depth tracking and player optimization. minor issues are addressed during debugging to ensure optimal moves.', 'chapters': [{'end': 680.261, 'start': 619.98, 'title': 'Writing minimax algorithm', 'summary': 'Involves writing the minimax function to create an algorithm that always returns a score of 1, causing it to pick the first available spot, with a minor issue arising but not causing major problems.', 'duration': 60.281, 'highlights': ['The algorithm always returns a score of 1, causing it to pick the first available spot, resulting in a tie for all choices.', 'The algorithm is making choices but always goes in order of the board, limiting its decision-making capability.', 'A minor issue arose during the process, but no major problems occurred.']}, {'end': 1285.354, 'start': 680.421, 'title': 'Implementing minimax algorithm for game ai', 'summary': 'Covers the implementation of the minimax algorithm for a turn-based game ai, including keeping track of depth and the maximizing/minimizing player, and debugging the algorithm to ensure optimal moves.', 'duration': 604.933, 'highlights': ['Implemented the minimax algorithm for a turn-based game AI, including keeping track of depth and the maximizing/minimizing player, to make optimal moves.', "Debugged the algorithm to ensure that the maximizing and minimizing player's turns are correctly handled, resulting in optimal moves for the AI.", 'Utilized the min and max functions to simplify the code and make it easier to read and understand.']}], 'duration': 665.374, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ619980.jpg', 'highlights': ['Implemented the minimax algorithm for a turn-based game AI, including keeping track of depth and the maximizing/minimizing player, to make optimal moves.', "Debugged the algorithm to ensure that the maximizing and minimizing player's turns are correctly handled, resulting in optimal moves for the AI.", 'Utilized the min and max functions to simplify the code and make it easier to read and understand.', 'The algorithm always returns a score of 1, causing it to pick the first available spot, resulting in a tie for all choices.', 'The algorithm is making choices but always goes in order of the board, limiting its decision-making capability.', 'A minor issue arose during the process, but no major problems occurred.']}, {'end': 1582.661, 'segs': [{'end': 1315.259, 'src': 'embed', 'start': 1285.894, 'weight': 0, 'content': [{'end': 1287.275, 'text': "We're going to go into competition now.", 'start': 1285.894, 'duration': 1.381}, {'end': 1290.536, 'text': "I'm going to let you win by going here.", 'start': 1288.715, 'duration': 1.821}, {'end': 1299.821, 'text': "Ah! So if I go in a corner, if I don't go to the middle, it's always going to win.", 'start': 1293.638, 'duration': 6.183}, {'end': 1306.964, 'text': 'So x is always going to win unless I go to the middle, which is always going to be a tie, unless I make a mistake.', 'start': 1300.501, 'duration': 6.463}, {'end': 1307.945, 'text': "And then it's going to win.", 'start': 1306.984, 'duration': 0.961}, {'end': 1310.006, 'text': 'But if I go to any other spot.', 'start': 1308.625, 'duration': 1.381}, {'end': 1315.259, 'text': "x is going to be able to win because it's always going to, OK, this worked.", 'start': 1311.138, 'duration': 4.121}], 'summary': 'In a game, x will win unless opponent reaches the middle, which results in a tie, but x will win if opponent makes a mistake.', 'duration': 29.365, 'max_score': 1285.894, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ1285894.jpg'}, {'end': 1385.368, 'src': 'embed', 'start': 1357.217, 'weight': 1, 'content': [{'end': 1360.04, 'text': "It's a solved game, because it's always going to go to the center.", 'start': 1357.217, 'duration': 2.823}, {'end': 1363.777, 'text': 'So I could try going here, could go here, go here.', 'start': 1360.896, 'duration': 2.881}, {'end': 1365.858, 'text': 'And the best I could do is a tie.', 'start': 1364.017, 'duration': 1.841}, {'end': 1367.959, 'text': "So you've watched this coding challenge.", 'start': 1366.538, 'duration': 1.421}, {'end': 1371.24, 'text': 'Maybe you have a creative idea about how to make your own version of this.', 'start': 1368.139, 'duration': 3.101}, {'end': 1377.322, 'text': 'But I just quickly whipped up, thanks to the chat in the live stream, also some suggestions of things you could try.', 'start': 1371.52, 'duration': 5.802}, {'end': 1382.505, 'text': 'So first of all, what happens if you just make two AI that just play against each other over and over again.', 'start': 1377.362, 'duration': 5.143}, {'end': 1385.368, 'text': "Well, in that case, it's just going to be a tie every single time.", 'start': 1382.725, 'duration': 2.643}], 'summary': 'Playing the game results in a tie every time, making it a solved game.', 'duration': 28.151, 'max_score': 1357.217, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ1357217.jpg'}, {'end': 1431.436, 'src': 'embed', 'start': 1392.554, 'weight': 2, 'content': [{'end': 1400.601, 'text': 'So, for example, if I go back to the code and I change these to say 10 and negative 10, I could account for the depth,', 'start': 1392.554, 'duration': 8.047}, {'end': 1405.586, 'text': 'meaning I could have a higher score if I win more quickly than if it takes longer to win.', 'start': 1400.601, 'duration': 4.985}, {'end': 1407.047, 'text': "Right now, I'm not accounting for that.", 'start': 1405.866, 'duration': 1.181}, {'end': 1410.911, 'text': "So where in the code would you subtract out depth? That's something you could try.", 'start': 1407.327, 'duration': 3.584}, {'end': 1414.512, 'text': 'Certainly, it would be interesting to make a larger board.', 'start': 1411.551, 'duration': 2.961}, {'end': 1420.813, 'text': 'So can you play Tic-Tac-Toe in a 5 by 5 or a 7 by 7? The winning conditions would change.', 'start': 1414.552, 'duration': 6.261}, {'end': 1422.454, 'text': 'The optimal play would change.', 'start': 1421.353, 'duration': 1.101}, {'end': 1423.814, 'text': 'That would be exciting to try.', 'start': 1422.534, 'duration': 1.28}, {'end': 1424.994, 'text': 'I hope somebody does that.', 'start': 1423.914, 'duration': 1.08}, {'end': 1426.694, 'text': 'You could try more players.', 'start': 1425.714, 'duration': 0.98}, {'end': 1431.436, 'text': "Like, how would you have a Tic-Tac-Toe game with three players? That's something you try with a larger board.", 'start': 1426.734, 'duration': 4.702}], 'summary': 'Modifying the code to account for depth and trying larger boards and more players in tic-tac-toe.', 'duration': 38.882, 'max_score': 1392.554, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ1392554.jpg'}, {'end': 1507.28, 'src': 'embed', 'start': 1480.823, 'weight': 4, 'content': [{'end': 1488.868, 'text': "Then there's a possibility of a game where the number of moves is so vast you couldn't possibly compute the entire tree.", 'start': 1480.823, 'duration': 8.045}, {'end': 1491.61, 'text': 'Chess is the classic example of that.', 'start': 1489.509, 'duration': 2.101}, {'end': 1498.074, 'text': 'So you need some heuristic or a way of an estimated guess of what the score could be with any given state.', 'start': 1491.65, 'duration': 6.424}, {'end': 1501.936, 'text': "So one way of doing this which I'm not saying is a good strategy, but a simple thing.", 'start': 1498.334, 'duration': 3.602}, {'end': 1507.28, 'text': 'you could do with chess add up the total number of white pieces versus black pieces.', 'start': 1501.936, 'duration': 5.344}], 'summary': 'In chess, a heuristic is needed for vast move possibilities, e.g., counting pieces.', 'duration': 26.457, 'max_score': 1480.823, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ1480823.jpg'}], 'start': 1285.894, 'title': 'Minimax algorithm for tic-tac-toe and game optimization', 'summary': 'Explores the implementation of the minimax algorithm for tic-tac-toe, demonstrating its unbeatable nature and suggesting enhancements such as incorporating depth in the score, experimenting with larger boards, and applying alpha-beta pruning and heuristic estimation for game optimization, with the potential of implementing a three-dimensional game board.', 'chapters': [{'end': 1431.436, 'start': 1285.894, 'title': 'Minimax algorithm for tic-tac-toe', 'summary': 'Explores the implementation of the minimax algorithm for tic-tac-toe, demonstrating its unbeatable nature and suggesting potential enhancements such as incorporating depth in the score and experimenting with larger boards and multiple players.', 'duration': 145.542, 'highlights': ['The chapter demonstrates the unbeatable nature of the Minimax algorithm for Tic-Tac-Toe, showcasing that X will always win unless the player makes a mistake, leading to a tie if the player goes to the middle spot. X always wins unless the player makes a mistake, and a tie occurs if the player goes to the middle spot.', 'The chapter suggests potential enhancements for the implementation, such as incorporating depth in the score and experimenting with larger Tic-Tac-Toe boards and multiple players. Suggestions include incorporating depth in the score, experimenting with larger boards like 5x5 or 7x7, and exploring the possibility of a Tic-Tac-Toe game with three players.', 'The chapter mentions the possibility of creating two AI players to compete against each other, resulting in a tied game each time due to the solved nature of Tic-Tac-Toe. Creating two AI players to compete results in a tied game each time due to the solved nature of Tic-Tac-Toe.']}, {'end': 1582.661, 'start': 1431.876, 'title': 'Enhancing minimax algorithm for game optimization', 'summary': 'Explores the application of alpha-beta pruning and heuristic estimation to optimize the minimax algorithm for game strategy, while also suggesting the possibility of implementing a three-dimensional game board.', 'duration': 150.785, 'highlights': ['Alpha-beta pruning is an aspect of the minimax algorithm that optimizes pathfinding by disregarding worse possibilities, reducing computation time. Reduces computation time by disregarding worse possibilities.', 'Heuristic estimation involves making an estimated guess of the score in a game state, such as counting total pieces, to provide an alternative to computing the entire tree, potentially improving efficiency in complex games. Provides an alternative to computing the entire tree, potentially improving efficiency in complex games.', 'The suggestion of creating a three-dimensional game board presents a novel and complex challenge for implementing the minimax algorithm, potentially expanding the possibilities for game strategy optimization. Presents a novel and complex challenge for implementing the minimax algorithm.']}], 'duration': 296.767, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/trKjYdBASyQ/pics/trKjYdBASyQ1285894.jpg', 'highlights': ['X always wins unless the player makes a mistake, and a tie occurs if the player goes to the middle spot.', 'Suggestions include incorporating depth in the score, experimenting with larger boards like 5x5 or 7x7, and exploring the possibility of a Tic-Tac-Toe game with three players.', 'Alpha-beta pruning reduces computation time by disregarding worse possibilities.', 'Heuristic estimation provides an alternative to computing the entire tree, potentially improving efficiency in complex games.', 'The suggestion of creating a three-dimensional game board presents a novel and complex challenge for implementing the minimax algorithm.']}], 'highlights': ['The Minimax algorithm is implemented to find the optimal next move for the AI, aiming for the computer player to beat or tie the human player in the game.', 'The minimax algorithm is applied to visualize all possible outcomes of the tic-tac-toe game based on the starting configuration, demonstrating the decision-making process for the maximizing and minimizing players.', 'Scoring mechanism for the tic-tac-toe game is explained, where winning is assigned a score of plus 1, losing a score of negative 1, and tying a score of 0, showcasing the quantifiable scoring system in the algorithm.', 'Addressing the need to track scores and handle game board alterations.', 'Alpha-beta pruning reduces computation time by disregarding worse possibilities.', 'Heuristic estimation provides an alternative to computing the entire tree, potentially improving efficiency in complex games.', 'The suggestion of creating a three-dimensional game board presents a novel and complex challenge for implementing the minimax algorithm.', 'The speaker demonstrated playing the game against the AI through a live stream, showcasing the functionality and interaction of the developed game.', 'The chapter discusses implementing the minimax algorithm for game AI, emphasizing the use of a tree diagram and recursive algorithms to determine the best move.', 'Implemented the minimax algorithm for a turn-based game AI, including keeping track of depth and the maximizing/minimizing player, to make optimal moves.', 'Recommended learning resources for understanding the Minimax algorithm and its application include a video by Sebastian Laig and a three-part series on geeksforgeeks.org.', 'The video by Sebastian Laig explains the Minimax algorithm and alpha-beta pruning, while the geeksforgeeks.org series focuses on applying the Minimax algorithm to tic-tac-toe.']}