<jupyter_start><jupyter_text>ČETVRTI DOMAĆI ZADATAK iz predmeta "Primenjena teorija igara" (Applied Game Theory) a) Poređenje rezultata kod pristupa Q-learning, SARSA i Monte Karlo metoda za igru Ajnc (BlackJack): https://github.com/NikolaZubic/AppliedGameTheoryHomeworkSolutions/blob/main/Homework%203/domaci3.ipynbb) Razvoj bota za igranje igre Iks-Oks (Tic Tac Toe) koristeći "Q-learning" pristup.  a) Suštinska razlika između navedenih metoda jeste u načinu ažuriranja Q-vrijednosti. Uzeto je da Q-learning i SARSA koriste Temporal-Difference Learning, sa time da kod Q-learninga u narednom stanju uvijek biramo najbolju akciju, dok kod SARSA algoritma biramo akciju na osnovu politike odlučivanja.Dobijeni su sledeći rezultati:Q LEARNING:Player wins: 3681Dealer wins: 5706Player wins percentage = 39.21%SARSA:Player wins: 3647Dealer wins: 5740Player wins percentage = 38.85%MONTE-CARLO METHODS:Player wins: 3314Dealer wins: 6186Player wins percentage = 34.88%  b)  Potrebni import-i<jupyter_code>import gym
import numpy as np
from gym import spaces
import pickle
import os<jupyter_output><empty_output><jupyter_text>Definisanje Iks-Oks okruženja koristeći "Open AI Gym" toolkit<jupyter_code>class TicTacToeEnvironment(gym.Env):
    # Because of human-friendly output
    metadata = {'render.modes': ['human']}

    def __init__(self, player_1, player_2):
        """
        Board is predefined to a 3 x 3 grid.
        We keep track of whether the game is over.
        When initializing the TicTacToeEnvironment, we set game_over flag to 'False'.
        :param player_1: First player
        :param player_2: Second player
        """
        self.observation_space = spaces.Discrete(3 * 3)
        self.action_space = spaces.Discrete(9)
        self.board = np.zeros((3, 3))
        self.player_1 = player_1
        self.player_2 = player_2
        self.game_over = False
        self.reset()

        # Let player_1 play first
        self.current_player = 1

        # Board string representation
        self.board_str = None

    def reset(self):
        # Resets the environment after one game.
        self.board = np.zeros((3, 3))  # set board to zeros
        self.board_str = None  # set board string representation to null
        self.game_over = False
        self.current_player = 1

    def get_board(self):
        # getter for current board
        return self.board

    def get_board_str(self):
        # synchronize board string representation with current board state
        self.board_str = str(self.board.reshape(3 * 3))
        return self.board_str

    def get_free_positions(self):
        # return positions on the board that are free / not occupied
        positions = [(i, j) for i in range(3) for j in range(3) if self.board[i, j] == 0]
        return positions

    def update_state(self, new_position):
        """
        Update the current state of the board. First player puts '1' on the board, second player puts '-1' on the board.

        :param new_position: from set { (0, 0), (0, 1), (0, 2), (1, 0,), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2) }
        :return: None
        """
        self.board[new_position] = self.current_player

        # If current player puts 1 ("X") on the board, next move is player 2 who puts -1 "O" on the board.
        if self.current_player == 1:
            self.current_player = -1
        else:
            self.current_player = 1

    def check_game_status(self):
        """
        Check if game has finished.

        :return: 1 if player 1 has won,
                 -1 if player 2 has won,
                 0 if draw,
                 None if game hasn't finished.
        """
        for i in range(3):
            if sum(self.board[i, :]) == 3:
                self.game_over = True
                return 1
            if sum(self.board[i, :]) == -3:
                self.game_over = True
                return - 1

        for i in range(3):
            if sum(self.board[:, i]) == 3:
                self.game_over = True
                return 1
            if sum(self.board[:, i]) == -3:
                self.game_over = True
                return -1

        main_diagonal_sum = sum([self.board[i, i] for i in range(3)])
        anti_diagonal_sum = sum([self.board[i, 3 - i - 1] for i in range(3)])
        diagonal_sum = max(abs(main_diagonal_sum), abs(anti_diagonal_sum))

        if diagonal_sum == 3:
            self.game_over = True

            if diagonal_sum == 3 or anti_diagonal_sum == 3:
                return 1
            else:
                return - 1

        # DRAW
        if len(self.get_free_positions()) == 0:
            self.game_over = True
            return 0

        self.game_over = False

        return None

    def step(self, action):
        """
        Performs one action.

        :param action: from set { (0, 0), (0, 1), (0, 2), (1, 0,), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2) }
        :return: current board state, reward, boolean indicating whether the game is over,
                 information about won the game if over
        """
        if self.game_over:
            return self.board, 0, True, None

        self.update_state(action)
        current_game_status = self.check_game_status()

        if current_game_status is not None:
            if current_game_status == 1:
                reward = 1
                info = {"Result": "Player 1 won the game."}
            elif current_game_status == -1:
                reward = -1
                info = {"Result": "Player 2 won the game."}
            else:
                # DRAW
                reward = 0
                info = {"Result": "Draw."}
            return self.board, reward, self.game_over, info
        return self.board, None, self.game_over, None

    def render(self):
        for i in range(0, 3):
            print('-------------')
            out = '| '
            for j in range(0, 3):
                token = ''
                if self.board[i, j] == 1:
                    token = 'X'
                if self.board[i, j] == -1:
                    token = 'O'
                if self.board[i, j] == 0:
                    token = ' '
                out += token + ' | '
            print(out)
        print('-------------')<jupyter_output><empty_output><jupyter_text>Definisanje Q-learning agenta<jupyter_code>class QLearningAgent(object):
    def __init__(self, gamma=0.9, LAMBDA=0.1, epsilon=0.1):
        self.gamma = gamma  # Discounting factor
        self.LAMBDA = LAMBDA  # Used for filtering q-values, learning rate
        self.epsilon = epsilon  # Used in epsilon-greedy policy
        self.states = []
        self.states_values = {}  # KEY = CURRENT_BOARD_STATE, VALUE = number

    @staticmethod
    def get_board_str(board):
        return str(board.reshape(3 * 3))

    def reset(self):
        self.states = []

    def add_state(self, state):
        self.states.append(state)

    def get_max_action(self, positions, current_board, symbol):
        """
        Choose best action.

        :param positions: set of free positions
        :param current_board: current environment board
        :param symbol: current player symbol (1 = "X" = PC and -1 = "O" = HUMAN)
        :return: action, for example (1, 1) which is in the center of 3x3 grid
        """
        if np.random.uniform(0, 1) <= self.epsilon:
            idx = np.random.choice(len(positions))  # choose index from the interval [0, 9]
            action = positions[idx]  # choose certain action, for example positions[1] = (0, 2)
        else:
            action = None
            value_max = - np.inf

            for pos in positions:
                next_board = current_board.copy()
                next_board[pos] = symbol
                next_board_str = self.get_board_str(next_board)

                if self.states_values.get(next_board_str) is None:
                    action_value = 0
                else:
                    action_value = self.states_values.get(next_board_str)

                if action_value >= value_max:
                    value_max = action_value
                    action = pos

        return action

    def compute_q(self, reward):
        """
        Compute q values at the end of the game, all states are saved in self.states.

        :param reward: depends on whether the player has won/lost/draw the game
        :return: None
        """
        for current_board_state in reversed(self.states):
            if self.states_values.get(current_board_state) is None:
                self.states_values[current_board_state] = 0

            q_current_s_a = self.states_values[current_board_state]

            # compute new q
            self.states_values[current_board_state] = q_current_s_a + self.LAMBDA * (self.gamma * reward -
                                                                                     q_current_s_a)

            reward = self.states_values[current_board_state]

    def save_policy(self):
        file = open("saved_policy", "wb")
        pickle.dump(self.states_values, file)
        file.close()

    def load_policy(self, file_name):
        file = open(file_name, "rb")
        self.states_values = pickle.load(file)
        file.close()<jupyter_output><empty_output><jupyter_text>Definisanje igrača, unos sa tastature<jupyter_code>class HumanPlayer(object):
    @staticmethod
    def act(positions):
        while True:
            user_input = input("['O' on move] x,y: ")
            x, y = user_input.split(",")
            x_int, y_int = int(x) - 1, int(y) - 1
            pos = (x_int, y_int)
            if pos in positions:
                return pos
            else:
                print("Invalid move. Try again.")<jupyter_output><empty_output><jupyter_text>Treniranje agenta<jupyter_code>def train(number_of_episodes):
    player_1 = QLearningAgent()
    player_2 = QLearningAgent()
    agents = [player_1, player_2]

    environment = TicTacToeEnvironment(player_1, player_2)

    for i in range(number_of_episodes):
        if i % 100000 == 0:
            print("Episode {}".format(i))

        environment.reset()

        is_done = False

        while not is_done:
            for agent in agents:
                if not is_done:
                    free_positions = environment.get_free_positions()
                    current_action = agent.get_max_action(free_positions, environment.get_board(),
                                                          environment.current_player)
                    current_board_state, reward, is_done, information = environment.step(current_action)
                    agent.add_state(agent.get_board_str(current_board_state))

                    if is_done:
                        if reward == 1:
                            # If player one wins, he gets the reward of 1
                            player_1.compute_q(1)
                            player_2.compute_q(0)
                        elif reward == -1:
                            # If player two wins, he gets the reward of 1
                            player_1.compute_q(0)
                            player_2.compute_q(1)
                        else:
                            # DRAW, computer gets smaller reward
                            player_1.compute_q(0.1)
                            player_2.compute_q(0.5)

                        # At the end, reset history of board states for both players
                        player_1.reset()
                        player_2.reset()

        environment.reset()
    player_1.save_policy()<jupyter_output><empty_output><jupyter_text>Pokretanje igre<jupyter_code>def play_game():
    player_1 = QLearningAgent()
    player_1.load_policy("saved_policy")
    player_2 = HumanPlayer()
    agents = [player_1, player_2]

    environment = TicTacToeEnvironment(player_1, player_2)
    environment.reset()

    is_done = False
    environment.render()

    while not is_done:
        for agent in agents:
            if agent == player_1:
                action = agent.get_max_action(environment.get_free_positions(), environment.get_board(),
                                              environment.current_player)
            else:
                action = agent.act(environment.get_free_positions())
            state, reward, is_done, information = environment.step(action)
            environment.render()

            if is_done:
                print(information['Result'])
                break<jupyter_output><empty_output><jupyter_text>Glavni program Preuzimanje istreniranog modela (treniran kroz **1 milion epizoda/partija**):<jupyter_code>!wget "https://github.com/NikolaZubic/AppliedGameTheoryHomeworkSolutions/raw/main/Homework%204/saved_policy"
if __name__ == '__main__':
    NUMBER_OF_EPISODES = 1000000

    if not os.path.exists("saved_policy"):
        train(number_of_episodes=NUMBER_OF_EPISODES)
    play_game()<jupyter_output>-------------
|   |   |   | 
-------------
|   |   |   | 
-------------
|   |   |   | 
-------------
-------------
|   |   |   | 
-------------
|   | X |   | 
-------------
|   |   |   | 
-------------
['O' on move] x,y: 1,1
-------------
| O |   |   | 
-------------
|   | X |   | 
-------------
|   |   |   | 
-------------
-------------
| O | X |   | 
-------------
|   | X |   | 
-------------
|   |   |   | 
-------------
['O' on move] x,y: 3,2
-------------
| O | X |   | 
-------------
|   | X |   | 
-------------
|   | O |   | 
-------------
-------------
| O | X |   | 
-------------
|   | X |   | 
-------------
| X | O |   | 
-------------
['O' on move] x,y: 1,3
-------------
| O | X | O | 
-------------
|   | X |   | 
-------------
| X | O |   | 
-------------
-------------
| O | X | O | 
-------------
| X | X |   | 
-------------
| X | O |   | 
-------------
['O' on move] x,y: 2,3
-------------
| O | X | O | 
-------------
| X | X | O | 
-------------
| X | O |   | 
-------------[...]
{'fraction_non_alphanumeric': 0.13088404133180254, 'fraction_numerical': 0.0169345579793341, 'mean_word_length': 1.6360885190088896, 'pattern_counts': {'":': 3, '<': 29, '<?xml version=': 0, '>': 29, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '45463', 'license': 'MIT', 'n_tokens_mistral': 4413, 'n_tokens_neox': 4143, 'n_words': 1091, 'path': 'Homework 4/domaci4.ipynb', 'repo_name': 'NikolaZubic/AppliedGameTheoryHomeworkSolutions', 'size': '13936'}