Min_Max Algorithm

[dhruvishavaghani]

I want to contribute Min-Max algorithm used in Artificial Intelligence.

[Aditya7024]

@dhruvishavaghani can you give a bit more discription about the problem

[Swap-Nova]

@Aditya7024 I can contribute to that.

• The algorithm comes under game-playing. For eg: In a tic-tac-toe game we perform a search algorithm by building a search tree.
• We can use the BFS approach in order to get more choices and therefore try to maximize our probability of winning.
• But the problem with using BFS is that it works as a level-order search which in turn can lead to exploring the complete level that is not allowed by game-playing as the first move will be by us and the next by the opponent.
• Therefore, we use the min-max algorithm which is a backtracking approach and use the best move strategy in order to maximize our probability to win.

• Time complexity= O(b^d), where b is the branching factor and d is depth.

[Aditya7024]

hey @Swap-Nova thanks for refreshing me on this topic but I was asking @dhruvishavaghani what exactly she is asking here, weather the code or only the description about the problem

[Swap-Nova]

Oh Okay, if it's alright I would like to write the code for this problem in order to understand the problem in depth.

[dhruvishavaghani]

I would like to add code and description both .

[Aditya7024]

@dhruvishavaghani Its just a game of tic-tac-toe which uses min-max algorithm but without any html frame work .

import random

Function to print the Tic-Tac-Toe board

def print_board(board): print("---------") for i in range(3): print("|", end=" ") for j in range(3): print(board[i][j], end=" ") print("|", end=" ") print("\n---------")

Function to check if a player has won

def check_win(board, player): for i in range(3): if board[i][0] == board[i][1] == board[i][2] == player: return True if board[0][i] == board[1][i] == board[2][i] == player: return True if board[0][0] == board[1][1] == board[2][2] == player: return True if board[0][2] == board[1][1] == board[2][0] == player: return True return False

Function to evaluate the score of the board

def evaluate(board): if check_win(board, "X"): return 1 elif check_win(board, "O"): return -1 else: return 0

Minimax algorithm

def minimax(board, depth, is_maximizing): score = evaluate(board)

if score == 1 or score == -1:
    return score

if depth == 0 or not any(" " in row for row in board):
    return 0

if is_maximizing:
    best_score = float("-inf")
    for i in range(3):
        for j in range(3):
            if board[i][j] == " ":
                board[i][j] = "X"
                score = minimax(board, depth - 1, False)
                board[i][j] = " "
                best_score = max(score, best_score)
    return best_score
else:
    best_score = float("inf")
    for i in range(3):
        for j in range(3):
            if board[i][j] == " ":
                board[i][j] = "O"
                score = minimax(board, depth - 1, True)
                board[i][j] = " "
                best_score = min(score, best_score)
    return best_score

Function to make a move

def make_move(board, player): best_score = float("-inf") best_move = None

for i in range(3):
    for j in range(3):
        if board[i][j] == " ":
            board[i][j] = player
            score = minimax(board, 9, False)
            board[i][j] = " "
            if score > best_score:
                best_score = score
                best_move = (i, j)

board[best_move[0]][best_move[1]] = player

Function to play the game

def play_game(): board = [[" " for _ in range(3)] for _ in range(3)] print("Welcome to Tic-Tac-Toe!") print_board(board)

while True:
    # Player's move
    row = int(input("Enter the row (0-2): "))
    col = int(input("Enter the column (0-2): "))

    if board[row][col] == " ":
        board[row][col] = "O"
        print_board

[dhruvishavaghani]

yes so can I contribute this ?

[Aditya7024]

@dhruvishavaghani yes the logic for min-max algorithm is correct but its not the full code , you have to call the functions and then run them ! It will only run on compilers . for graphical representation you must write a html/JavaScript code

[dhruvishavaghani]

Okay, I will do that! Please assign this issue to me!!

[github-actions[bot]]

Stale issue message