{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import games\n", "\n", "infinity = float('inf')\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class TicTacToe(games.Game):\n", " \"\"\"Play TicTacToe on an h x v board, with Max (first player) playing 'X'.\n", " A state has the player to move, a cached utility, a list of moves in\n", " the form of a list of (x, y) positions, and a board, in the form of\n", " a dict of {(x, y): Player} entries, where Player is 'X' or 'O'.\"\"\"\n", "\n", " def __init__(self, h=3, v=3, k=3):\n", " self.h = h\n", " self.v = v\n", " self.k = k\n", " moves = [(x, y) for x in range(1, h + 1)\n", " for y in range(1, v + 1)]\n", " self.initial = games.GameState(to_move='X', utility=0, board={}, moves=moves)\n", " self.show_moves = True\n", "\n", " def actions(self, state):\n", " \"\"\"Legal moves are any square not yet taken.\"\"\"\n", " return state.moves\n", "\n", " def result(self, state, move):\n", " if move not in state.moves:\n", " return state # Illegal move has no effect\n", " board = state.board.copy()\n", " board[move] = state.to_move\n", " moves = list(state.moves)\n", " moves.remove(move)\n", " return GameState(to_move=('O' if state.to_move == 'X' else 'X'),\n", " utility=self.compute_utility(board, move, state.to_move),\n", " board=board, moves=moves)\n", "\n", " def utility(self, state, player):\n", " \"\"\"Return the value to player; 1 for win, -1 for loss, 0 otherwise.\"\"\"\n", " return state.utility if player == 'X' else -state.utility\n", "\n", " def terminal_test(self, state):\n", " \"\"\"A state is terminal if it is won or there are no empty squares.\"\"\"\n", " return state.utility != 0 or len(state.moves) == 0\n", "\n", " def display(self, state):\n", " board = state.board\n", " for x in range(1, self.h + 1):\n", " for y in range(1, self.v + 1):\n", " print(board.get((x, y), '.'), end=' ')\n", " print()\n", "\n", " def compute_utility(self, board, move, player):\n", " \"\"\"If 'X' wins with this move, return 1; if 'O' wins return -1; else return 0.\"\"\"\n", " if (self.k_in_row(board, move, player, (0, 1)) or\n", " self.k_in_row(board, move, player, (1, 0)) or\n", " self.k_in_row(board, move, player, (1, -1)) or\n", " self.k_in_row(board, move, player, (1, 1))):\n", " return +1 if player == 'X' else -1\n", " else:\n", " return 0\n", "\n", " def k_in_row(self, board, move, player, delta_x_y):\n", " \"\"\"Return true if there is a line through move on board for player.\"\"\"\n", " (delta_x, delta_y) = delta_x_y\n", " x, y = move\n", " n = 0 # n is number of moves in row\n", " while board.get((x, y)) == player:\n", " n += 1\n", " x, y = x + delta_x, y + delta_y\n", " x, y = move\n", " while board.get((x, y)) == player:\n", " n += 1\n", " x, y = x - delta_x, y - delta_y\n", " n -= 1 # Because we counted move itself twice\n", " return n >= self.k\n", "\n", " def play_game(self, *players):\n", " \"\"\"Play an n-person, move-alternating game. This a version of\n", " the method from the aima-python games.py program that has been\n", " modified to optionaly print moves made by each player.\"\"\"\n", " state = self.initial\n", " while True:\n", " for player_num, player in enumerate(players):\n", " player_num += 1\n", " move = player(self, state)\n", " state = self.result(state, move)\n", " if self.show_moves:\n", " print(\" Player{} moves {} => {}\".format(player_num, move, state.board))\n", " if self.terminal_test(state):\n", " self.display(state)\n", " return self.utility(state, self.to_move(self.initial))\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a_game = TicTacToe()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(a_game)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A player is represented by a search function that takes a game instance and a state and returns a move. The game's methods (actions, result, utility and terminal_test) do the real work\n", "\n", "The aima code defines several search functions and some players based on them" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "smart = lambda g, s: games.alphabeta_cutoff_search(s, g, d=3)\n", "smarter = lambda g, s: games.alphabeta_cutoff_search(s, g, d=10)\n", "smartest = games.alphabeta_player\n", "dumb = lambda g, s: games.alphabeta_cutoff_search(s, g, d=1)\n", "random = games.random_player\n", "print(smart, smarter, dumb)\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a_game = TicTacToe()\n", "a_game.play_game(smart, dumb)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a_game = TicTacToe()\n", "a_game.play_game(smart, smarter)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a_game = TicTacToe()\n", "a_game.play_game(dumb, random)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.0" } }, "nbformat": 4, "nbformat_minor": 2 }