17. Intro to Game AI and Reinforcement Learning/exercise/03. exercise-n-step-lookahead.ipynb

{"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.7.12","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"**This notebook is an exercise in the [Intro to Game AI and Reinforcement Learning](https://www.kaggle.com/learn/intro-to-game-ai-and-reinforcement-learning) course.  You can reference the tutorial at [this link](https://www.kaggle.com/alexisbcook/n-step-lookahead).**\n\n---\n","metadata":{}},{"cell_type":"markdown","source":"# Introduction\n\nIn the tutorial, you learned how to build a reasonably intelligent agent with the minimax algorithm.  In this exercise, you will check your understanding and submit your own agent to the competition.","metadata":{}},{"cell_type":"code","source":"from learntools.core import binder\nbinder.bind(globals())\nfrom learntools.game_ai.ex3 import *","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:52:15.559552Z","iopub.execute_input":"2022-07-30T05:52:15.560338Z","iopub.status.idle":"2022-07-30T05:52:15.622692Z","shell.execute_reply.started":"2022-07-30T05:52:15.560242Z","shell.execute_reply":"2022-07-30T05:52:15.621697Z"},"trusted":true},"execution_count":1,"outputs":[]},{"cell_type":"markdown","source":"### 1) A closer look\n\nThe heuristic from the tutorial looks at all groups of four adjacent grid locations on the same row, column, or diagonal and assigns points for each occurrence of the following patterns:\n\n<center>\n<img src=\"https://i.imgur.com/3NvBEGL.png\" width=70%><br/>\n</center>\n\nIs it really necessary to use so many numbers to define the heuristic?  Consider simplifying it, as in the image below.\n\n<center>\n<img src=\"https://i.imgur.com/grViegG.png\" width=70%><br/>\n</center>\n\nHow would each heuristic score the potential moves in the example below (where, in this case, the agent looks only one step ahead)?  Which heuristic would lead to the agent selecting the better move?\n\n<center>\n<img src=\"https://i.imgur.com/LWPLy7N.png\" width=100%><br/>\n</center>","metadata":{}},{"cell_type":"code","source":"#q_1.hint()","metadata":{},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Check your answer (Run this code cell to receive credit!)\nq_1.solution()","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:53:37.043183Z","iopub.execute_input":"2022-07-30T05:53:37.043618Z","iopub.status.idle":"2022-07-30T05:53:37.054933Z","shell.execute_reply.started":"2022-07-30T05:53:37.043584Z","shell.execute_reply":"2022-07-30T05:53:37.053800Z"},"trusted":true},"execution_count":2,"outputs":[]},{"cell_type":"markdown","source":"### 2) Count the leaves\n\nIn the tutorial, we worked with a small game tree.\n\n<center>\n<img src=\"https://i.imgur.com/BrRe7Bu.png\" width=90%><br/>\n</center>\n\nThe game tree above has 8 leaf nodes that appear at the bottom of the tree.  By definition, \"leaf nodes\" in a game tree are nodes that don't have nodes below them.\n\nIn the ConnectX competition, the game trees will be much larger!  \n\nTo see this, consider a minimax agent that is trying to plan its first move, where all columns in the game board are  empty.  Say the agent builds a game tree of depth 3.  How many leaf nodes are in the game tree?  \n\nUse your answer to fill in the blank below.","metadata":{}},{"cell_type":"code","source":"# Fill in the blank\nnum_leaves = 7 * 7 * 7\n\n# Check your answer\nq_2.check()","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:53:52.988324Z","iopub.execute_input":"2022-07-30T05:53:52.989327Z","iopub.status.idle":"2022-07-30T05:53:52.996104Z","shell.execute_reply.started":"2022-07-30T05:53:52.989288Z","shell.execute_reply":"2022-07-30T05:53:52.995364Z"},"trusted":true},"execution_count":6,"outputs":[]},{"cell_type":"code","source":"# Lines below will give you a hint or solution code\n#q_2.hint()\n#q_2.solution()","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:53:49.924930Z","iopub.execute_input":"2022-07-30T05:53:49.925286Z","iopub.status.idle":"2022-07-30T05:53:49.929954Z","shell.execute_reply.started":"2022-07-30T05:53:49.925257Z","shell.execute_reply":"2022-07-30T05:53:49.928977Z"},"trusted":true},"execution_count":5,"outputs":[]},{"cell_type":"markdown","source":"### 3) Which move will the agent select?\n\nIn this question, you'll check your understanding of the minimax algorithm.  Remember that with this algorithm, \n> The agent chooses moves to get a score that is as high as possible, and it assumes the opponent will counteract this by choosing moves to force the score to be as low as possible.\n\nConsider the toy example below of a game tree that the agent will use to select its next move.  \n<center>\n<img src=\"https://i.imgur.com/QlfWGM9.png\" width=80%><br/>\n</center>\n\nWhich move will the agent select?  Use your answer to set the value of the `selected_move` variable below.  Your answer should be one of `1`, `2`, or `3`.","metadata":{}},{"cell_type":"code","source":"# Fill in the blank\nselected_move = 3\n\n# Check your answer\nq_3.check()","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:54:00.939167Z","iopub.execute_input":"2022-07-30T05:54:00.939573Z","iopub.status.idle":"2022-07-30T05:54:00.948642Z","shell.execute_reply.started":"2022-07-30T05:54:00.939542Z","shell.execute_reply":"2022-07-30T05:54:00.947354Z"},"trusted":true},"execution_count":8,"outputs":[]},{"cell_type":"code","source":"# Lines below will give you a hint or solution code\n#q_3.hint()\n#q_3.solution()","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:54:03.936753Z","iopub.execute_input":"2022-07-30T05:54:03.937102Z","iopub.status.idle":"2022-07-30T05:54:03.941615Z","shell.execute_reply.started":"2022-07-30T05:54:03.937073Z","shell.execute_reply":"2022-07-30T05:54:03.940792Z"},"trusted":true},"execution_count":9,"outputs":[]},{"cell_type":"markdown","source":"### 4) Examine the assumptions\n\nThe minimax agent assumes that its opponent plays optimally (with respect to the heuristic, and using a game tree of limited depth).  But this is almost never the case, in practice: it's far more likely for the agent to encounter a suboptimal (that is: worse than optimal) opponent.  \n\nSay the minimax agent encounters a suboptimal opponent. Should we expect the minimax agent to still play the game well, despite the contradiction with its assumptions?  If so, why?","metadata":{}},{"cell_type":"code","source":"#q_4.hint()","metadata":{},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Check your answer (Run this code cell to receive credit!)\nq_4.solution()","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:54:06.818335Z","iopub.execute_input":"2022-07-30T05:54:06.818761Z","iopub.status.idle":"2022-07-30T05:54:06.828303Z","shell.execute_reply.started":"2022-07-30T05:54:06.818720Z","shell.execute_reply":"2022-07-30T05:54:06.827197Z"},"trusted":true},"execution_count":10,"outputs":[]},{"cell_type":"markdown","source":"### 5) Submit to the competition\n\nNow, it's time to submit an agent to the competition!  Use the next code cell to define an agent.  (You can see an example of how to write a valid agent in **[this notebook](https://www.kaggle.com/alexisbcook/create-a-connectx-agent)**.)\n\nIf you decide to use the minimax code from the tutorial, you might like to add [**alpha-beta pruning**](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) to decrease the computation time (i.e., get the minimax algorithm to run much faster!).  In this case, \"alpha\" and \"beta\" to refer to two values that are maintained while the algorithm is running, that help to identify early stopping conditions.  \n\nWithout alpha-beta pruning, minimax evaluates each leaf node.  With alpha-beta pruning, minimax only evaluates nodes that could provide information that affects the agent's choice of action.  Put another way, it identifies nodes that could not possibly affect the final result and avoids evaluating them.","metadata":{}},{"cell_type":"code","source":"def my_agent(obs, config):\n    # Your code here: Amend the agent!\n    import random\n    valid_moves = [col for col in range(config.columns) if obs.board[col] == 0]\n    return random.choice(valid_moves)","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:54:12.002535Z","iopub.execute_input":"2022-07-30T05:54:12.002905Z","iopub.status.idle":"2022-07-30T05:54:12.008225Z","shell.execute_reply.started":"2022-07-30T05:54:12.002875Z","shell.execute_reply":"2022-07-30T05:54:12.007408Z"},"trusted":true},"execution_count":11,"outputs":[]},{"cell_type":"code","source":"# Run this code cell to get credit for creating an agent\nq_5.check()","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:54:14.457569Z","iopub.execute_input":"2022-07-30T05:54:14.458166Z","iopub.status.idle":"2022-07-30T05:54:14.466288Z","shell.execute_reply.started":"2022-07-30T05:54:14.458120Z","shell.execute_reply":"2022-07-30T05:54:14.465306Z"},"trusted":true},"execution_count":12,"outputs":[]},{"cell_type":"code","source":"import inspect\nimport os\n\ndef write_agent_to_file(function, file):\n    with open(file, \"a\" if os.path.exists(file) else \"w\") as f:\n        f.write(inspect.getsource(function))\n        print(function, \"written to\", file)\n\nwrite_agent_to_file(my_agent, \"submission.py\")","metadata":{"execution":{"iopub.status.busy":"2022-07-30T05:54:16.291677Z","iopub.execute_input":"2022-07-30T05:54:16.292145Z","iopub.status.idle":"2022-07-30T05:54:16.300155Z","shell.execute_reply.started":"2022-07-30T05:54:16.292087Z","shell.execute_reply":"2022-07-30T05:54:16.299252Z"},"trusted":true},"execution_count":13,"outputs":[]},{"cell_type":"markdown","source":"Then, follow these steps to submit your agent to the competition:\n1. Begin by clicking on the **Save Version** button in the top right corner of the window.  This will generate a pop-up window.  \n2. Ensure that the **Save and Run All** option is selected, and then click on the **Save** button.\n3. This generates a window in the bottom left corner of the notebook.  After it has finished running, click on the number to the right of the **Save Version** button.  This pulls up a list of versions on the right of the screen.  Click on the ellipsis **(...)** to the right of the most recent version, and select **Open in Viewer**.  This brings you into view mode of the same page. You will need to scroll down to get back to these instructions.\n4. Click on the **Output** tab on the right of the screen.  Then, click on the file you would like to submit, and click on the **Submit** button to submit your results to the leaderboard.\n\nYou have now successfully submitted to the competition!\n\nIf you want to keep working to improve your performance, select the **Edit** button in the top right of the screen. Then you can change your code and repeat the process. There's a lot of room to improve, and you will climb up the leaderboard as you work.\n\n\nGo to **\"My Submissions\"** to view your score and episodes being played.\n\n# Keep going\n\nMove on to learn how to **[use deep reinforcement learning](https://www.kaggle.com/alexisbcook/deep-reinforcement-learning)** to develop an agent without a heuristic!","metadata":{}},{"cell_type":"markdown","source":"---\n\n\n\n\n*Have questions or comments? Visit the [course discussion forum](https://www.kaggle.com/learn/intro-to-game-ai-and-reinforcement-learning/discussion) to chat with other learners.*","metadata":{}}]}