بازی Match-3 از بازیهای پازلی هستند که در آن بازیکن میخواهد ۳ یا بیشتر از ۳ آیتم را طبق الگوی خاصی در کنار هم قرار دهد. این آیتمها معمولا با اشیایی یا نمادهایی به رنگهای مختلف نمایش داده میشوند و وقتی در کنار هم قرار بگیرند محو میشوند و بازیکن امتیازهایی به دست میآورد.
بازیهای Match-3 جزو پردرآمدترین بازیهای ویدیویی جهان به حساب میآیند و همچنین این بازیها برای تمام سنین و افراد مناسب است.
اولین بازی Match-3 در سال ۱۹۸۴ میلادی توسط یک توسعهدهندهی بازی روسی ساخته شده و تا الآن بیش از هزاران بازی در این سبک آمده است. میتوان گفت این سبک از بازیها جزو اولین بازی ویدیوها بوده و همچنان طرفداران زیاد خودش را دارد.
اما از تاریخچهی این بازی که بگذریم، شاید لازم باشد توضیحات بیشتری از نظر ساختاری دربارهی این بازی بدهیم.
این بازی معمولا چندین Level دارد که با رد کردن هر کدام مرحلهی جدیدی باز میشود.
اکنون شناخت بهتری از این بازی داریم. الگوریتمهای زیادی برای حل بازی match 3 وجود دارند. در ادامه به معرفی بعضی از الگوریتمهای معروف برای حل این بازی میپردازیم.
این الگوریتم سادهترین و ابتداییترین الگوریتم برای حل این مساله است. این روش بر مبنای توان محاسباتی است و درگیر بهینهسازی نمیشود.
به عنوان مثال فکر کنید یک رمز چهار رقمی داریم که باید آن را پیدا کنیم. در این الگوریتم تمام ترکیبهای ممکن تست میشود. یعنی از ۰۰۰۰ تا ۹۹۹۹ را پیادهسازی کرده تا ببیند کدام رمز مورد نظر بوده است.
این الگوریتم برای حل بازی 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
این الگوریتم شبیه به نیروی بیرحم است اما تفاوتهایی دارد که آن را توضیح میدهم. این الگوریتم تمام راهحلها را آزمایش میکند و هر کجا که راهحل ما مناسب نبود به عقب برمیگردد و راه جدیدی را امتحان میکند. (بر خلاف 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)
این الگوریتم اکثرا برای بازیهای دو نفره است.میتوان الگوریتم را تقلیل داد تا برای بازی 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
الگوریتمهای دیگری نیز برای حل این بازی وجود دارد. همچنین با ترکیب الگوریتمها نیز میتوان روشهای بهینهای ساخت. اما بین این سه الگوریتم، الگوریتم آخر بهینهتر است و بیشترین نتیجه را دارد.
