Artificial Intelligence - 6

by

 AIM: Write a program to create tic-tac-toe game using the alpha-beta algorithm.

Consider following steps to create a program in python:

     1.    Create class StateNode with its proper members (getScoreValue(), isValidMove(), isGameOver(), drawboard(), getEmptyCells(), setMove(), isWin(), etc.)


2.    Create class ticTacToe with its proper members (alphabeta(), computerMove(), playerMove(), execution(), etc.)


3.    Create appropriate heuristic function to solve this problem

4.    Use only math, random, matplotlib libraries in python

Program:

from math import inf as infinity

from random import choice

import platform

import time

from os import system

 

HUMAN = -1

COMP = +1

board = [

    [0, 0, 0],

    [0, 0, 0],

    [0, 0, 0],

]

 

def evaluate(state):

   

    if wins(state, COMP):

        score = +1

    elif wins(state, HUMAN):

        score = -1

    else:

        score = 0

    return score

 

def wins(state, player):

   

    win_state = [

        [state[0][0], state[0][1], state[0][2]],

        [state[1][0], state[1][1], state[1][2]],

        [state[2][0], state[2][1], state[2][2]],

        [state[0][0], state[1][0], state[2][0]],

        [state[0][1], state[1][1], state[2][1]],

        [state[0][2], state[1][2], state[2][2]],

        [state[0][0], state[1][1], state[2][2]],

        [state[2][0], state[1][1], state[0][2]],

    ]

    if [player, player, player] in win_state:

        return True

    else:

        return False

 

def game_over(state):

    

    return wins(state, HUMAN) or wins(state, COMP)

 

def empty_cells(state):

    cells = []

    for x, row in enumerate(state):

        for y, cell in enumerate(row):

            if cell == 0:

                cells.append([x, y])

    return cells

 

def valid_move(x, y):

   

    if [x, y] in empty_cells(board):

        return True

    else:

        return False

def set_move(x, y, player):

   

    if valid_move(x, y):

        board[x][y] = player

        return True

    else:

        return False

 

def minimax(state, depth, player):

   

    if player == COMP:

        best = [-1, -1, -infinity]

    else:

        best = [-1, -1, +infinity]

 

    if depth == 0 or game_over(state):

        score = evaluate(state)

        return [-1, -1, score]

 

    for cell in empty_cells(state):

        x, y = cell[0], cell[1]

        state[x][y] = player

        score = minimax(state, depth - 1, -player)

        state[x][y] = 0

        score[0], score[1] = x, y

 

        if player == COMP:

            if score[2] > best[2]:

                best = score  

        else:

            if score[2] < best[2]:

                best = score  

    return best

 

def clean():

   

    os_name = platform.system().lower()

    if 'windows' in os_name:

        system('cls')

    else:

        system('clear')

 

def render(state, c_choice, h_choice):

    chars = {

        -1: h_choice,

        +1: c_choice,

        0: ' '

    }

    str_line = '---------------'

 

    print('\n' + str_line)

    for row in state:

        for cell in row:

            symbol = chars[cell]

            print(f'| {symbol} |', end='')

        print('\n' + str_line)

 

def ai_turn(c_choice, h_choice):

    

    depth = len(empty_cells(board))

    if depth == 0 or game_over(board):

        return

 

    clean()

    print(f'Computer turn [{c_choice}]')

    render(board, c_choice, h_choice)

 

    if depth == 9:

        x = choice([0, 1, 2])

        y = choice([0, 1, 2])

    else:

        move = minimax(board, depth, COMP)

        x, y = move[0], move[1]

 

    set_move(x, y, COMP)

    time.sleep(1)

 

def human_turn(c_choice, h_choice):

    

    depth = len(empty_cells(board))

    if depth == 0 or game_over(board):

        return

 

    move = -1

    moves = {

        1: [0, 0], 2: [0, 1], 3: [0, 2],

        4: [1, 0], 5: [1, 1], 6: [1, 2],

        7: [2, 0], 8: [2, 1], 9: [2, 2],

    }

 

    clean()

    print(f'Human turn [{h_choice}]')

    render(board, c_choice, h_choice)

 

    while move < 1 or move > 9:

        try:

            move = int(input('Use numpad (1..9): '))

            coord = moves[move]

            can_move = set_move(coord[0], coord[1], HUMAN)

 

            if not can_move:

                print('Bad move')

                move = -1

        except (EOFError, KeyboardInterrupt):

            print('Bye')

            exit()

        except (KeyError, ValueError):

            print('Bad choice')

 

def main():

   

    clean()

    h_choice = ''  

    c_choice = '' 

    first = '' 

 

    while h_choice != 'O' and h_choice != 'X':

        try:

            print('')

            h_choice = input('Choose X or O\nChosen: ').upper()

        except (EOFError, KeyboardInterrupt):

            print('Bye')

            exit()

        except (KeyError, ValueError):

            print('Bad choice')

 

    if h_choice == 'X':

        c_choice = 'O'

    else:

        c_choice = 'X'

 

    clean()

    while first != 'Y' and first != 'N':

        try:

            first = input('First to start?[y/n]: ').upper()

        except (EOFError, KeyboardInterrupt):

            print('Bye')

            exit()

        except (KeyError, ValueError):

            print('Bad choice')

 

    while len(empty_cells(board)) > 0 and not game_over(board):

        if first == 'N':

            ai_turn(c_choice, h_choice)

            first = ''

 

        human_turn(c_choice, h_choice)

        ai_turn(c_choice, h_choice)

 

    if wins(board, HUMAN):

        clean()

        print(f'Player turn [{h_choice}]')

        render(board, c_choice, h_choice)

        print('YOU WIN!')

    elif wins(board, COMP):

        clean()

        print(f'Computer turn [{c_choice}]')

        render(board, c_choice, h_choice)

        print('YOU LOSE!')

    else:

        clean()

        render(board, c_choice, h_choice)

        print('DRAW!')

    exit()

    

if __name__ == '__main__':

    main()

 

Output:





Comments

Post a Comment

Popular posts from this blog

Computer Architecture and Organization - 4

by
Image
Aim:  To implement various 4-bit arithmetic Micro-operations           using arithmetic unit.   Theory Arithmetic micro operation of the form L:   R A  ( R A + R B ) refers to two data items contained in R A and R B input to a parallel adder with the result being stored back in R A (Fig.). Loading      of the result in R A is subject to the availability   of the control   signal designated as L   (that   is   load control of R A ) . Note that adder being a combinational logic, the adder output is available after a delay of the associated combinational circuit. Input to adder may be also controlled by providing AND word gates on the data paths from R A and R B to the adder under the control signal C (Fig.). the control signals `C' and 2's complement are at logic `0' for add operation.   The subtract micro operation L:   R A  ( R A - R B ) in 2's comp...
Read more

Design and Analysis of Algorithms - 2

by
Image
Implement functions to print n th Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart. Code:   #include<stdio.h>   int count_ite=0; int count_rec=0; void febo_ite(int ); int febo_rec(int );   int main() {     int n,ans;     printf("Enter position of number: ");     scanf("%d",&n);     febo_ite(n);     ans=febo_rec(n);     printf("Using Recursion: %d th number is = %d\n",n,ans);     printf("No of Steps= %d\n\n",count_rec); }   void febo_ite(int n) {     count_ite++;     int next,i, first=0,second=1;     count_ite++;     if(n==0)     {         count_ite++;  ...
Read more

Design and Analysis of Algorithms - 6

by
Image
Implement program for randomized version of quick sort and compare its performance with normal version of quick sort using steps count on various number of inputs.   Code: #include<stdio.h> #include<stdlib.h> #include<time.h>   int count=0; int r_count=0; void quick_sort(int a[],int start,int n) {     int i,j,pivot,temp;     count++;     if(start<n)         {             count++;             pivot=start;             count++;             i=start;             count++;             j=n;     ...
Read more

Design and Analysis of Algorithms - 1

by
Image
Implement a function for each of following problems and count the  number of steps executed/Time taken by each function on various  inputs and write complexity of each function. Also draw a  comparative chart. In each of the following function N will be passed  by user.                     1. To calculate sum of 1 to N number using loop.                     2. To calculate sum of 1 to N number using equation.                     3. To calculate sum of 1 to N numbers using recursion. Code:   #include <stdio.h> int count_loop=0; int count_rec=0; int count_eq=0;   int sum_loop(int n) {     int i,sum=0;     count_loop++;     for(i=1;i<=n;i++)     {         count_loop++; ...
Read more

Artificial Intelligence - 7

by
Image
  AIM: Write a program to build Multi-layer Perceptron to implement any Boolean functions as mentioned below without using any python packages. AND, OR, XOR, XNOR, NOR, NAND, NOT x1, NOT x2, NULL, IDENTITY, INHIBITION ( 𝑥 1 ∧ ¬ 𝑥 2), INHIBITION ( 𝑥 2 ∧ ¬ 𝑥 1), TRANSFER x1, TRANSFER x2, IMPLICATION ( 𝑥 1 ∨ ¬ 𝑥 2), IMPLICATION ( 𝑥 2 ∨ ¬ 𝑥 1)   Program: class  perceptronNeuron:      def   __init__ ( self ,  x ,  w ,  w0 ):         l = [ww  for  ww  in  x]         l.insert( 0 ,  1 )          self .x = l          self .y =  0         l = [ww  for  ww  in  w]         l.insert( 0 ,...
Read more