الگوریتم هایی برای حل بازی Match-3

بازی Match-3 از بازی‌های پازلی هستند که در آن بازیکن می‌خواهد ۳ یا بیشتر از ۳ آیتم را طبق الگوی خاصی در کنار هم قرار دهد. این آیتم‌ها معمولا با اشیایی یا نمادهایی به رنگ‌های مختلف نمایش داده می‌شوند و وقتی در کنار هم قرار بگیرند محو می‌شوند و بازیکن امتیازهایی به دست می‌آورد.

بازی‌های Match-3 جزو پردرآمدترین بازی‌های ویدیویی جهان به حساب می‌آیند و همچنین این بازی‌ها برای تمام سنین و افراد مناسب است.

اولین بازی Match-3 در سال ۱۹۸۴ میلادی توسط یک توسعه‌دهنده‌ی بازی روسی ساخته شده و تا الآن بیش از هزاران بازی در این سبک آمده است. می‌توان گفت این سبک از بازی‌ها جزو اولین بازی ویدیوها بوده و همچنان طرفداران زیاد خودش را دارد.

اما از تاریخچه‌ی این بازی که بگذریم، شاید لازم باشد توضیحات بیشتری از نظر ساختاری درباره‌ی این بازی بدهیم.

• برد بازی: زمین یا صفحه‌ی بازی شامل سلول‌هایی مانند جدول است که هر یک از آیتم ها در یکی از این سلول‌ها قرار می‌گیرد.
• تطبیق: بازیکن می‌تواند یک آیتم را با آیتم‌های مجاور برای ساختن یک ردیف یا یک ستون سه‌تایی یا بیشتر از آیتم‌ها جابه‌جا کند. (بسته به طراحی بازی گاهی الگوهای دیگر نیز قابل قبول است.)
• سقوط مهره‌ها: پس از این که یک الگو مچ شد و مهره‌ها محو شدند، مهره‌ها به صورت آبشاری از بالا دوباره در زمین بازی می‌ریزند و جاهای خالی را پر می‌کنند.
• اهداف: این بازی می‌تواند هدف‌های متفاوتی داشته باشد. اهداف معمولا شامل جمع کردن تعدادی مهره مشخص یا پاک کردن آیتم خاصی به صورت کامل از روی صفحه یا انجام دادن الگوهای خاصی در زمانی محدود یا تعداد حرکات محدود است.
• پاورآپ‌ها و آیتم‌های ویژه: در بعضی از بازی‌های Match-3 با جور کردن الگوهایی پیچیده‌تر از سه آیتم کنار هم می‌توانیم آیتم‌های ویژه‌ای مثل بمب‌ها دریافت کنیم. این آیتم‌ها کمکی به بازیکن هستند تا بتوانند در یک حرکت تعداد بیشتری مهره جمع کند.

این بازی معمولا چندین Level دارد که با رد کردن هر کدام مرحله‌ی جدیدی باز می‌شود.

اکنون شناخت بهتری از این بازی داریم. الگوریتم‌های زیادی برای حل بازی match 3 وجود دارند. در ادامه به معرفی بعضی از الگوریتم‌های معروف برای حل این بازی می‌پردازیم.

Brute force

زوری یا نیروی بی رحم

این الگوریتم ساده‌ترین و ابتدایی‌ترین الگوریتم برای حل این مساله است. این روش بر مبنای توان محاسباتی است و درگیر بهینه‌سازی نمی‌شود.

به عنوان مثال فکر کنید یک رمز چهار رقمی داریم که باید آن را پیدا کنیم. در این الگوریتم تمام ترکیب‌های ممکن تست می‌شود. یعنی از ۰۰۰۰ تا ۹۹۹۹ را پیاده‌سازی کرده تا ببیند کدام رمز مورد نظر بوده است.

این الگوریتم برای حل بازی match-3 شامل تست تمام حرکات ممکن است و بعد از آن انتخاب راهی که بهترین خروجی را به ما داده است.

１- بررسی تمام حرکات موجود (تمام آیتم‌هایی که می‌تواند جابه‌جا کند)

２- پیش‌بینی شکل برد و محل قرار گرفتن مهره‌ها بعد از انجام این حرکت

３- محاسبه‌ی تعداد مچ‌هایی که در آن حالت می توان داشت

４- انتخاب بهترین حرکت

def brute_force_move(game_board):
    best_move = None
    best_score = 0

    for row in range(len(game_board))

        for col in range(len(game_board[0])):
            # Try swapping with the right neighbor
            if col < len(game_board[0]) - 1:
                # Simulate the game state after the swap
                # Evaluate the game state and update best_move and best_score if needed

            # Try swapping with the bottom neighbor
            if row < len(game_board) - 1:
                # Simulate the game state after the swap
                # Evaluate the game state and update best_move and best_score if needed
    return best_move

Backtracking

عقبگرد

این الگوریتم شبیه به نیروی بی‌رحم است اما تفاوت‌هایی دارد که آن را توضیح می‌دهم. این الگوریتم تمام راه‌حل‌ها را آزمایش می‌کند و هر کجا که راه‌حل ما مناسب نبود به عقب برمی‌گردد و راه جدیدی را امتحان می‌کند. (بر خلاف ‌Brute Force که تمام راه‌ها را آزمایش کرده و بعد جواب را بین آن‌ها پیدا می‌کند.)

مراحل حل match-3 توسط این الگوریتم به صورت زیر است:

1- اسکن گیم برد: گیم‌برد را برای پیدا کردن تطبیق‌ها اسکن می‌کنیم.

2- پیدا کردن مچ‌ها: به دنبال مچ‌های عمودی و افقی می‌گردد. بعد از پیدا کردن یکی از آن‌ها آن را انجام می‌دهیم تا تاثیرات این مچ را ببینیم.

3- مشاهده تاثیرات مچ: بعد از انجام مچ برای دیدن تاثیرات آن این اتفاق را شبیه‌سازی می‌کنیم. بدین صورت که اگر حرکت باید جایزه‌ای دریافت کند آن را می‌دهیم و مهره‌های بالایی را پایین بریزیم تا جای خالی آن‌ها پر شود.

4- تکرار: مراحل 2 و 3 را دوباره در گیم‌برد جدید تکرار می‌کنیم تا زمانی که دیگر هیچ تطابقی پیدا نکنیم.

5- در این مرحله گیم برد ما کامل شده و تاثیرات تطابق‌هایی که انجام داده‌ایم را می‌بینیم.

در هر کدام از این مراحل اگر به جایی برسیم که بازی ما حل نشده بود و شکست خورده بودیم، یک مرحله به عقب برمی‌گردیم و مسیر بعدی را انتخاب می‌کنیم و این کار را مجددا انجام می‌دهیم.

# Define a function to check for and remove matching tiles
def remove_matches(board):
    rows = len(board)
    cols = len(board[0])
    matched = False

    # Check for horizontal matches
    for row in range(rows):
        for col in range(cols - 2):
            if board[row][col] == board[row][col + 1] == board[row][col + 2]:
                board[row][col] = 0
                board[row][col + 1] = 0
                board[row][col + 2] = 0
                matched = True

    # Check for vertical matches
    for col in range(cols):
        for row in range(rows - 2):
            if board[row][col] == board[row + 1][col] == board[row + 2][col]:
                board[row][col] = 0
                board[row + 1][col] = 0
                board[row + 2][col] = 0
                matched = True
    return matched

# Define a function to perform gravity and fill empty spaces after matches are removed
def perform_gravity(board):
    rows = len(board)
    cols = len(board[0])
    for col in range(cols):
        non_zeros = [board[row][col] for row in range(rows) if board[row][col] != 0]
        zeros = [0] * (rows - len(non_zeros))
        board_column = zeros + non_zeros
        for row in range(rows):
            board[row][col] = board_column[row]

# Define a function to resolve the Match-3 game using backtracking
def resolve_match3(board):
    while remove_matches(board):
        perform_gravity(board)

Mini Max

کمین‌ بیش (تقلیل یافته)

این الگوریتم اکثرا برای بازی‌های دو نفره است.می‌توان الگوریتم را تقلیل داد تا برای بازی Match-3 مناسب شود و چیدمان رندوم زمین را به عنوان حریف خود بگیریم. این الگوریتم بدین شکل است که درختی به وجود می‌آورد و در هرمرحله اگر نوبت شما باشد بهترین حرکت را انتخاب می‌کند و اگر نوبت حریف باشد بدترین حرکت را انتخاب می‌کند تا در انتها بیشترین امتیاز ممکن را به عنوان بهترین راه انتخاب کند.

مراحل حل match-3 توسط این الگوریتم به صورت زیر است:

1- اسکن گیم برد و انتخاب بهترین حرکت برای اولین حرکت

2- امتیازدهی به حرکت انتخاب‌شده

3- پیش‌بینی زمین بازی بعد از انجام آن حرکت و امتیازدهی به حالت‌های ممکن

4- انتخاب بدترین حالت زمین برای ادامه

این کارها را آن‌قدر تکرار می‌کند تا به دستاوردهای لازم بازی برسد و ببرد.

# Define the evaluation function to assess the desirability of a game state
def evaluate_board(board):
    # Your evaluation function implementation goes here
    # This function should assess the desirability of the current game state

# Define the minimax algorithm to find the best move
def minimax(board, depth, maximizing_player):
    if depth == 0 or game_over(board):
        return evaluate_board(board)
    
     if maximizing_player:
        max_eval = -math.inf
        for move in possible_moves(board):
            eval = minimax(move, depth - 1, False)
            max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = math.inf
        for move in possible_moves(board):
            eval = minimax(move, depth - 1, True)
            min_eval = min(min_eval, eval)
        return min_eval

# Define a function to make the best move using the minimax algorithm
def make_best_move(board, depth):
    best_move = None
    best_eval = -math.inf
    for move in possible_moves(board):
        eval = minimax(move, depth, False)
        if eval > best_eval:
            best_eval = eval
            best_move = move
    return best_move

الگوریتم‌های دیگری نیز برای حل این بازی وجود دارد. همچنین با ترکیب الگوریتم‌ها نیز می‌توان روش‌های بهینه‌ای ساخت. اما بین این سه الگوریتم، الگوریتم آخر بهینه‌تر است و بیشترین نتیجه را دارد.