Mengimplementasikan Algoritme Minimax untuk AI di Python

Algoritme Mini-Max memiliki sejarah panjang dalam AI, sejak tahun 1920-an. Meski istilah AI belum digunakan untuk algoritme komputer saat itu, algoritme dasar ini memberikan beberapa wawasan paling awal tentang bagaimana mesin dapat mengambil keputusan optimal dalam skenario adversarial. Algoritme ini pertama kali diformalkan oleh John von Neumann dalam makalahnya tahun 1928 “Zur Theorie der Gesellschaftsspiele” (Tentang Teori Permainan Strategi), yang menjadi landasan teori permainan modern dan algoritme pengambilan keputusan.

Pada 1997, Deep Blue milik IBM mengalahkan juara catur dunia Garry Kasparov menggunakan varian Mini-max yang canggih. Sejak itu, algoritme ini menjadi tulang punggung pendekatan yang lebih mutakhir seperti Monte Carlo Tree Search (MCTS) dan sistem pembelajaran penguatan (reinforcement learning).

Dalam artikel ini, kita tidak akan membangun ulang Deep Blue untuk catur, melainkan versi yang jauh lebih sederhana untuk tic-tac-toe di Python. Sepanjang jalan, Anda akan memperoleh intuisi yang kuat tentang cara kerja algoritme dan bagaimana menerapkannya pada gim dunia nyata yang lebih kompleks.

Apa itu Algoritme Minimax?

Minimax biasanya adalah algoritme pengambilan keputusan untuk gim dua pemain (seperti catur, tic-tac-toe, atau dam). Ini memungkinkan komputer merencanakan beberapa langkah ke depan dengan asumsi lawan Anda selalu membuat langkah terbaiknya. Pada bagian ini, kita akan melihat gambaran umum algoritme melalui contoh tic-tac-toe.

Gambaran umum algoritme Minimax

Dalam tic-tac-toe dunia nyata, setiap kali giliran Anda, Anda mencoba membuat langkah terbaik dengan asumsi lawan juga bermain sebaik mungkin. Inilah yang persis dilakukan algoritme Minimax — membantu komputer membuat langkah terbaik dengan berpikir ke depan tentang semua kemungkinan gerakan.

Algoritme Minimax mendapat namanya dari cara kerjanya:

• “Mini” mewakili lawan yang mencoba meminimalkan skor Anda
• “Max” mewakili Anda yang mencoba memaksimalkan skor Anda

Saat giliran Anda, Anda ingin membuat langkah yang memberi peluang menang terbaik (memaksimalkan). Saat giliran lawan, Anda berasumsi mereka akan membuat langkah yang memberi hasil terburuk bagi Anda (meminimalkan).

Pentingnya Minimax dalam AI

Minimax sangat penting dalam kecerdasan buatan karena beberapa alasan:

1. Membantu komputer membuat keputusan cerdas dalam gim dua pemain
2. Menjadi fondasi bagi banyak sistem AI bermain gim modern
3. Mengajarkan komputer untuk berpikir ke depan dan merencanakan langkah

Bagian paling keren? Gagasan yang sama digunakan dalam banyak aplikasi dunia nyata:

• Lawan AI di gim video
• Gim strategi seperti catur dan dam
• Bahkan beberapa alat pengambilan keputusan bisnis

Walau Minimax terdengar rumit, sebenarnya ini hanya mengajarkan komputer untuk berpikir seperti pemain yang cermat yang mempertimbangkan langkahnya dan langkah lawan sebelum mengambil keputusan.

Memahami Algoritme Minimax

Mari kita uraikan cara kerja Minimax menggunakan contoh tic-tac-toe sederhana. Bayangkan Anda bermain sebagai X, dan komputer adalah O.

Bagaimana komputer berpikir

Saat giliran komputer, ia mengikuti langkah-langkah ini:

1. Melihat semua kemungkinan langkah yang dapat dibuat
2. Untuk setiap langkah, membayangkan apa yang mungkin Anda lakukan selanjutnya
3. Terus berpikir maju hingga mencapai titik akhir (seperti seseorang menang atau seri)
4. Memilih langkah yang memberinya peluang menang terbaik

Memberi skor pada gim

Komputer dapat menggunakan sistem penilaian sederhana:

• +10 poin jika komputer menang
• -10 poin jika Anda menang
• 0 poin jika seri

Bayangkan ini seperti pohon kemungkinan:

• Di puncak adalah papan gim saat ini
• Setiap cabang adalah satu kemungkinan langkah
• Di dasar adalah semua kemungkinan hasil

Bergantian giliran

Komputer beralih antara dua mode berpikir:

1. Mode memaksimalkan (giliran komputer):

• Mencari langkah dengan skor tertinggi
• Berusaha menang atau memaksakan seri

2. Mode meminimalkan (giliran pemain):

• Mengasumsikan Anda akan membuat langkah yang menghasilkan skor terendah
• Bersiap menghadapi langkah terbaik Anda

Contoh sederhana

Misalnya giliran komputer (X) dalam gim ini:

Komputer akan:

1. Melihat ada 3 petak kosong untuk dipilih
2. Untuk setiap petak kosong, membayangkan semua langkah masa depan yang mungkin
3. Memilih langkah yang mengarah ke hasil terbaik baginya
4. Dalam kasus ini, ia seharusnya memilih kotak tengah bawah untuk memblokir kemenangan Anda

Cara berpikir ke depan seperti ini membantu komputer bermain tic-tac-toe dengan sempurna setiap saat!

Pseudocode Algoritme Minimax

Mari uraikan cara menulis algoritme Minimax selangkah demi selangkah. Jangan khawatir jika Anda baru mengenal pseudocode — anggap saja ini menuliskan langkah-langkah dalam bahasa Inggris biasa sebelum kita ubah menjadi kode sebenarnya!

Penjelasan langkah demi langkah

Fungsi Minimax membutuhkan tiga hal utama agar berfungsi:

1. Papan gim saat ini
2. Kedalaman (berapa banyak langkah ke depan yang kita lihat)
3. Apakah ini giliran pemain pemaksimal (komputer) atau pemain peminimal (manusia)

Berikut tampilan pseudocode dasarnya:

function minimax(board, depth, isMaximizingPlayer):
   # First, check if the game is over
   if game is won:
       return +10 if computer wins, -10 if human wins
   if game is tied:
       return 0

   # If it's the computer's turn (maximizing)
   if isMaximizingPlayer:
       bestScore = -infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, false)
           undo the move
           bestScore = max(score, bestScore)
       return bestScore

   # If it's the human's turn (minimizing)
   else:
       bestScore = +infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, true)
           undo the move
           bestScore = min(score, bestScore)
       return bestScore

Walau sebagian besar contoh pseudocode dibaca dalam bahasa Inggris dan mudah dipahami, yang di atas berbeda karena menggunakan rekursi. Rekursi adalah ketika sebuah fungsi memanggil dirinya sendiri berulang kali untuk menyelesaikan masalah yang lebih besar. Bayangkan seperti melihat ke cermin yang memantulkan cermin lain — Anda melihat gambar yang sama berulang kali, makin kecil setiap kali.

Dalam algoritme Minimax kita, kita membutuhkan rekursi karena kita mencoba melihat semua kemungkinan langkah masa depan dalam gim. Setiap kali fungsi memanggil dirinya sendiri, ia melihat langkah berikutnya yang bisa terjadi. 

Ini membantu kita menentukan langkah terbaik dengan memeriksa setiap kemungkinan jalannya gim, seperti pemain yang sangat pintar yang berpikir “Jika saya lakukan ini, maka mereka mungkin lakukan itu, lalu saya bisa lakukan ini…” dan seterusnya sampai gim berakhir. Untuk mempelajari lebih lanjut tentang rekursi, Anda dapat membaca tutorial rekursi terpisah kami.

Contoh ilustratif

Mari lihat bagaimana ini bekerja dalam situasi gim sederhana:

1. Posisi awal:

2. Komputer berpikir:

• “Jika saya menempatkan X di petak kosong mana pun…”
• “Apa yang akan dilakukan manusia selanjutnya?”
• “Dan apa yang bisa saya lakukan setelah itu?”
• “Langkah mana yang memberi saya skor akhir terbaik?”

3. Untuk setiap petak kosong, komputer:

• Melakukan langkah
• Memeriksa apakah gim sudah berakhir
• Jika belum, membayangkan langkah terbaik manusia
• Teruskan hingga menemukan akhir
• Memilih langkah dengan skor tertinggi

Bayangkan seperti catur — Anda selalu berpikir “Jika saya pindah ke sini, mereka akan pindah ke sana, lalu saya bisa pindah ke sini…” tetapi komputer dapat memikirkan SEMUA kemungkinan langkah sekaligus!

Hal keren dari algoritme ini adalah selalu menemukan langkah terbaik, dengan asumsi kedua pemain bermain sempurna. Ini seperti memiliki bola kristal yang menunjukkan semua kemungkinan masa depan gim!

Mengimplementasikan Minimax untuk Tic-tac-toe Selangkah demi Selangkah

Pada bagian ini, kita akan membangun AI tic-tac-toe yang tak terkalahkan dengan algoritme Mini-max murni di Python. Kita akan menguraikan implementasi dalam langkah-langkah sederhana dan menjelaskan intuisi di balik masing-masing serta bagaimana semuanya menyatu dalam gambaran besar gim.

Langkah 1: Mendefinisikan kelas TicTacToe

Pertama, kita mendefinisikan kelas yang memuat seluruh logika dan metode yang diperlukan untuk memainkan gim tic-tac-toe dengan komputer kita:

class TicTacToe:
   def __init__(self):
       # Initialize empty board (using ' ' for empty squares)
       self.board = [" " for _ in range(9)]
       self.human_player = "O"
       self.ai_player = "X"

   def print_board(self):
       """Print the current state of the board"""
       for i in range(0, 9, 3):
           print(f"{self.board[i]} | {self.board[i+1]} | {self.board[i+2]}")
           if i < 6:
               print("---------")

   def available_moves(self):
       """Returns list of available moves (indices of empty squares)"""
       return [i for i, spot in enumerate(self.board) if spot == " "]

Di atas, metode __init__ menginisialisasi papan gim baru sebagai daftar berisi 9 spasi kosong (diwakili oleh spasi " "), dengan indeks 0-8 mewakili posisi papan dari kiri ke kanan, atas ke bawah. Ini juga menyiapkan dua simbol pemain - "O" untuk pemain manusia dan "X" untuk AI.

Metode print_board menyediakan cara untuk memvisualisasikan keadaan papan saat ini. Ini mencetak kisi 3x3 dengan garis pemisah antarbaris, menampilkan langkah masing-masing pemain di posisinya.

Metode available_moves mengembalikan daftar semua langkah valid yang masih bisa dibuat. Ini dilakukan dengan memeriksa posisi mana di papan yang masih kosong (berisi spasi " ") dan mengembalikan indeksnya. Ini akan krusial bagi algoritme minimax untuk mengetahui langkah mana yang dapat dipertimbangkan.

Metode-metode ini membentuk fondasi yang akan kita bangun untuk membuat pemain AI menggunakan algoritme minimax.

Mari uji cepat:

>>> game = TicTacToe()
>>> game.print_board()
  |   | 
---------
  |   | 
---------
  |   |

>>> game.available_moves()
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Sesuai harapan, saat ini kita memiliki papan kosong dan semua langkah tersedia.

Langkah 2: Mengimplementasikan metode untuk melakukan langkah dan memeriksa status papan

Sekarang, mari tambahkan metode untuk melakukan langkah:

class TicTacToe:
   ...
  
   def make_move(self, position, player):
       """Make a move on the board"""
       if self.board[position] == " ":
           self.board[position] = player
           return True
       return False

Kita telah menambahkan metode make_move yang:

• Menerima posisi (0–8) dan simbol pemain (“X” atau “O”) sebagai masukan
• Memeriksa apakah posisi yang dipilih kosong (“ ”)
• Jika kosong, menempatkan simbol pemain dan mengembalikan True
• Jika posisi sudah terisi, mengembalikan False tanpa mengubah apa pun

Mari lakukan beberapa langkah dan periksa sisa langkah:

>>> game = TicTacToe()

>>> game.make_move(0, "X")
>>> game.make_move(1, "O")

>>> game.print_board()
 X | O | 
-----------
   |   | 
-----------
   |   |

>>> game.available_moves()
[2, 3, 4, 5, 6, 7, 8]

Berjalan baik. Langkah berikutnya adalah menambahkan metode untuk memeriksa apakah papan penuh:

class TicTacToe:
   ...

   def is_board_full(self):
       """Check if the board is full"""
       return " " not in self.board

is_board_full adalah metode boolean yang memeriksa apakah masih ada spasi kosong di papan.

Selanjutnya, kita tambahkan metode untuk memeriksa apakah kondisi menang tercapai:

class TicTacToe:
   ...

   def check_winner(self):
       """Check if there's a winner. Returns winner symbol or None"""
       # Check rows
       for i in range(0, 9, 3):
           if self.board[i] == self.board[i + 1] == self.board[i + 2] != " ":
               return self.board[i]

       # Check columns
       for i in range(3):
           if self.board[i] == self.board[i + 3] == self.board[i + 6] != " ":
               return self.board[i]

       # Check diagonals
       if self.board[0] == self.board[4] == self.board[8] != " ":
           return self.board[0]
       if self.board[2] == self.board[4] == self.board[6] != " ":
           return self.board[2]

       return None

Metode check_winner mengevaluasi keadaan papan Tic-tac-toe saat ini untuk menentukan apakah ada pemenang. Ia memeriksa semua kombinasi kemenangan yang mungkin:

1. Baris (3 kemungkinan):

• Baris atas (indeks 0,1,2)
• Baris tengah (indeks 3,4,5)
• Baris bawah (indeks 6,7,8)

2. Kolom (3 kemungkinan):

• Kolom kiri (indeks 0,3,6)
• Kolom tengah (indeks 1,4,7)
• Kolom kanan (indeks 2,5,8)

3. Diagonal (2 kemungkinan):

• Kiri-atas ke kanan-bawah (indeks 0,4,8)
• Kanan-atas ke kiri-bawah (indeks 2,4,6)

Untuk setiap kombinasi, ia memeriksa apakah ketiga posisi berisi simbol pemain yang sama (X atau O) dan bukan spasi kosong. Jika ditemukan kombinasi menang, ia mengembalikan simbol pemenang. Jika tidak ada pemenang setelah memeriksa semua kemungkinan, ia mengembalikan None.

Mari uji fungsi pada kondisi menang dan tidak menang:

game = TicTacToe()

# Winning state
game.make_move(0, "X")
game.make_move(1, "X")
game.make_move(2, "X")

>>> game.print_board()
 X | X | X
-----------
   |   | 
-----------
   |   |

>>> game.check_winner()
'X'

game = TicTacToe()

# Non-winning state
game.make_move(0, "X")
game.make_move(1, "O")
game.make_move(2, "O")
game.make_move(3, "X")

>>> game.print_board()
 X | O | O
-----------
 X |   | 
-----------
   |   |

>>> game.check_winner() is None
True

Terakhir, kita tambahkan metode boolean lain untuk menyatakan apakah gim sudah berakhir atau belum:

class TicTacToe:
   ...

   def game_over(self):
       """Check if the game is over"""
       return self.check_winner() is not None or self.is_board_full()

Metode ini mengembalikan True jika pemenang ditemukan atau papan sudah penuh.

Pada titik ini, kita telah membangun semua mekanisme inti gim:

• Papan direpresentasikan sebagai daftar 9 petak yang diinisialisasi kosong
• print_board() menampilkan keadaan gim saat ini secara visual
• available_moves() mengembalikan indeks petak kosong
• make_move() menempatkan simbol pemain di papan
• check_winner() memeriksa baris, kolom, dan diagonal untuk kemenangan di setiap langkah
• is_board_full() menentukan apakah tidak ada langkah tersisa
• game_over() menggabungkan pemeriksaan pemenang dan papan penuh

Metode-metode ini menyediakan fondasi yang dibutuhkan untuk membuat gim yang dapat dimainkan, menangani semua operasi dasar seperti membuat langkah dan menentukan status gim.

Sekarang bagian krusial — memberi komputer “otak” untuk bermain menggunakan Minimax.

Langkah 3: Mengimplementasikan Minimax untuk tic-tac-toe

Sekarang, mari implementasikan algoritmenya untuk gim dalam metode baru:

class TicTacToe:
   ...

   def minimax(self, depth, is_maximizing):
       """
       Minimax algorithm implementation
       Returns the best score possible for the current board state
       """
       # Base cases
       winner = self.check_winner()
       if winner == self.ai_player:
           return 1
       if winner == self.human_player:
           return -1
       if self.is_board_full():
           return 0

Fungsi ini menerima dua parameter:

• depth - Melacak berapa tingkat kedalaman kita dalam rekursi. Ini dapat digunakan untuk membatasi kedalaman pencarian untuk gim yang sangat kompleks, meskipun untuk tic-tac-toe kita tidak perlu membatasinya.
• is_maximizing - Flag boolean yang menunjukkan apakah kita saat ini mencari skor maksimum (giliran AI) atau skor minimum (giliran manusia). Ini berganti pada setiap pemanggilan rekursif seiring pemain bergantian.

Di dalam fungsi, kita mulai dengan mendefinisikan kasus dasar: Jika gim dimenangkan AI (winner == ai_player), kita mengembalikan 1 karena ini hasil terbaik bagi AI. Jika manusia menang (winner == human_player), kita mengembalikan -1 karena ini hasil terburuk bagi AI. Jika papan penuh tanpa pemenang, kita mengembalikan 0 untuk hasil seri.

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       best_score = float("-inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(depth + 1, False)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = max(score, best_score)
       return best_score

Ketika is_maximizing bernilai True, kita mensimulasikan giliran AI dan ingin menemukan langkah yang menghasilkan skor setinggi mungkin. Kita mulai dengan mengatur best_score ke negatif tak hingga agar skor nyata apa pun akan lebih baik. Lalu untuk setiap langkah yang tersedia, kita:

1. Menempatkan simbol AI di papan secara sementara
2. Mengevaluasi secara rekursif apa yang terjadi jika kita membuat langkah ini dengan memanggil minimax dengan is_maximizing=False (karena selanjutnya giliran manusia)
3. Membatalkan langkah sementara untuk mengembalikan keadaan papan
4. Melacak skor tertinggi sejauh ini menggunakan max()

Ini memungkinkan kita memeriksa setiap kemungkinan langkah yang bisa dilakukan AI. Untuk setiap langkah, kita melihat apa yang bisa terjadi selanjutnya, hingga seseorang menang atau seri. Lalu kita menelusuri balik untuk menemukan langkah pertama mana yang memberi AI peluang menang terbaik.

Sekarang, mari lakukan bagian meminimalkan untuk manusia:

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       ...

   else:
       # if it is the minimizing player's turn (human), we want to minimize the score
       best_score = float("inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.human_player
           # Recursively call minimax with the next depth and the maximizing player
           score = self.minimax(depth + 1, True)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = min(score, best_score)
       return best_score

Ketika is_maximizing bernilai False, kita mensimulasikan giliran pemain manusia dan ingin menemukan langkah yang menghasilkan skor serendah mungkin (karena skor tinggi berarti AI menang). Kita mulai dengan best_score sebagai positif tak hingga agar skor nyata apa pun akan lebih rendah. Untuk setiap langkah yang tersedia, kita:

1. Menempatkan simbol manusia di papan secara sementara
2. Mengevaluasi secara rekursif apa yang akan terjadi dengan memanggil minimax dengan is_maximizing=True (karena selanjutnya giliran AI)
3. Membatalkan langkah sementara untuk mengembalikan keadaan papan
4. Melacak skor terendah yang kita lihat menggunakan min()

Ini mensimulasikan pemain manusia yang mencoba membuat langkah terbaik untuk mencegah AI menang. Manusia ingin meminimalkan skor karena skor positif merepresentasikan kemenangan AI. Dengan bergantian antara giliran memaksimalkan dan meminimalkan, algoritme dapat menentukan urutan langkah optimal bagi kedua pemain.

Langkah 4: Menemukan langkah terbaik untuk AI menggunakan Minimax

Sekarang algoritmenya sudah siap, kita memerlukan metode lain yang menggunakan metode minimax untuk menentukan langkah terbaik bagi AI setelah setiap langkah manusia:

class TicTacToe:
   ...

   def get_best_move(self):
       """Find the best move for AI using minimax"""
       best_score = float("-inf")
       best_move = None

       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(0, False)
           # Reset the move
           self.board[move] = " "

           # Update the best score
           if score > best_score:
               best_score = score
               best_move = move

       return best_move

Metode get_best_move bertanggung jawab menentukan langkah optimal bagi pemain AI menggunakan algoritme minimax. Cara kerjanya:

1. Memulai dengan skor terbaik negatif tak hingga dan belum ada langkah yang dipilih

2. Untuk setiap langkah yang tersedia di papan:

• Menempatkan simbol AI sementara di posisi tersebut
• Menggunakan minimax untuk mengevaluasi seberapa baik langkah itu dengan mensimulasikan sisa gim
• Membatalkan langkah sementara
• Jika langkah ini menghasilkan skor lebih baik dari sebelumnya, memperbarui skor terbaik dan langkah terbaik

3. Terakhir mengembalikan langkah yang menghasilkan skor tertinggi

Pendekatan ini memastikan AI memilih langkah yang memberinya peluang terbaik untuk menang, dengan asumsi pemain manusia juga bermain optimal. Metode ini mempertimbangkan semua kemungkinan keadaan gim di masa depan dan memilih jalur yang memaksimalkan peluang AI sambil meminimalkan peluang manusia untuk menang.

Mari uji pada keadaan gim contoh:

game = TicTacToe()

# Make a couple of moves
game.make_move(0, "X")
game.make_move(1, "O")

# Print the board

>>> game.print_board()
X | O | 
---------
  |   | 
---------
  |   |

>>> game.get_best_move()
3

# AI moves
>>> game.make_move(3, "X")

# I move
>>> game.make_move(4, "O")
>>> game.print_board()
X | O | 
---------
X | O | 
---------
  |   |

# Get the best move for AI
>>> game.get_best_move()
6

Seperti yang Anda lihat, AI menemukan kombinasi kemenangan berdasarkan langkah saya (ini keadaan dummy tetapi membuktikan algoritme kita bekerja).

Langkah 5: Mengimplementasikan loop gim

Sekarang kita telah mengimplementasikan dan menguji algoritme minimax, mari buat loop gim yang memungkinkan kita bermain melawan AI.

class TicTacToe:

   ...

   def play_game(self):
       """Main game loop"""
       print("Welcome to Tic Tac Toe!")
       print("You are 'O' and the AI is 'X'")
       print("Enter positions (0-8) as shown below:")
       print("0 | 1 | 2")
       print("---------")
       print("3 | 4 | 5")
       print("---------")
       print("6 | 7 | 8")
       print("\n")

Metode play_game dimulai dengan menampilkan pesan sambutan dan instruksi kepada pemain. Ditunjukkan bahwa pemain manusia menggunakan ‘O’ dan AI menggunakan ‘X’. Kemudian mencetak kisi bernomor (0–8) untuk menunjukkan nomor mana yang sesuai dengan posisi di papan. Ini memudahkan pemain mengetahui nomor mana yang harus dimasukkan untuk langkah yang diinginkan.

# ... the rest of the class
def play_game(self):
   ...

   # Randomly decide who goes first
   import random

   ai_turn = random.choice([True, False])

   while not self.game_over():
       self.print_board()

       if ai_turn:
           print("\nAI's turn...")
           move = self.get_best_move()
           self.make_move(move, self.ai_player)
       else:
           while True:
               try:
                   move = int(input("\nYour turn (0-8): "))
                   if 0 <= move <= 8 and self.make_move(move, self.human_player):
                       break
                   else:
                       print("Invalid move! Try again.")
               except ValueError:
                   print("Please enter a number between 0 and 8!")

       ai_turn = not ai_turn

Setelah menampilkan instruksi awal, gim masuk ke loop utamanya. Gim secara acak memutuskan siapa yang lebih dulu — AI atau pemain manusia — menggunakan random.choice([True, False]). Ini menciptakan unsur keadilan dan ketidakpastian di awal setiap gim.

Loop gim utama berlanjut hingga game_over() mengembalikan True (seseorang menang atau papan penuh). Selama setiap giliran, keadaan papan saat ini ditampilkan menggunakan print_board().

Jika giliran AI (ai_turn bernilai True), program:

1. Mencetak pesan bahwa AI sedang berpikir
2. Memanggil get_best_move() untuk menentukan langkah optimal menggunakan algoritme minimax
3. Melakukan langkah dengan menempatkan simbol AI (‘X’) pada posisi yang dipilih

Jika giliran manusia (ai_turn bernilai False), program:

1. Masuk ke loop untuk mendapatkan masukan yang valid dari pemain2. Meminta nomor langkah antara 0–83. Memvalidasi masukan agar:

• Bilangan bulat yang valid (menggunakan try/except)
• Dalam rentang valid 0–8
• Menunjuk ke posisi kosong di papan

4. Terus meminta hingga masukan valid diterima. Melakukan langkah dengan menempatkan simbol pemain (‘O’) pada posisi yang dipilih

Setelah setiap giliran, ai_turn dibalik menggunakan not untuk bergantian antar pemain. Ini menciptakan alur saling bergantian, dengan masing-masing pemain mengambil giliran hingga seseorang menang atau gim berakhir seri.

Validasi masukan memastikan gim tidak mogok karena masukan pengguna yang tidak valid dan memberikan pesan galat yang membantu untuk membimbing pemain memasukkan langkah yang benar. Ini menciptakan pengalaman gim yang tangguh dan ramah pengguna.

def play_game(self):
   ...
   # Game over
   self.print_board()
   winner = self.check_winner()
   if winner == self.ai_player:
       print("\nAI wins!")
   elif winner == self.human_player:
       print("\nCongratulations! You win!")
   else:
       print("\nIt's a tie!")

Saat gim berakhir, keadaan akhir papan ditampilkan menggunakan print_board() dan pemenang ditentukan oleh check_winner(). Gim dapat berakhir dengan tiga cara:

1. AI menang — Jika check_winner() mengembalikan simbol AI ('X'), yang menandakan AI membentuk garis kemenangan
2. Manusia menang — Jika check_winner() mengembalikan simbol manusia ('O'), yang menandakan pemain membentuk garis kemenangan
3. Seri — Jika tidak ada yang menang tetapi papan penuh, artinya tidak ada langkah lagi yang mungkin

Pesan yang sesuai ditampilkan untuk mengumumkan hasil gim. Ini memberikan umpan balik yang jelas kepada pemain tentang bagaimana gim berakhir.

Langkah 6: Menyatukan semuanya

Sekarang, saatnya menempatkan semua kode yang sudah kita tulis ke dalam skrip Python dengan klausa if/main berikut di bagian paling akhir:

# Start the game
if __name__ == "__main__":
   game = TicTacToe()
   game.play_game()

Ini memungkinkan gim dimulai segera setelah Anda menjalankan skrip dengan python script.py. Jika Anda tersesat di antara semua penjelasan dan blok kode, Anda dapat menemukan kode lengkap gim dalam GitHub gist ini.

Berikut contoh gim yang saya mainkan:

❯ python tic-tac-toe.py
Welcome to Tic Tac Toe!
You are 'O' and the AI is 'X'
Enter positions (0-8) as shown below:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8


  |   | 
---------
  |   | 
---------
  |   | 

Your turn (0-8): 4
  |   | 
---------
  | O | 
---------
  |   | 

AI's turn...
X |   | 
---------
  | O | 
---------
  |   | 

Your turn (0-8): 5
X |   | 
----------
  | O | O
----------
  |   | 

AI's turn...
X |   | 
---------
X | O | O
---------
  |   | 

Your turn (0-8): 6
X |   | 
---------
X | O | O
---------
O |   | 

AI's turn...
X |   | X
---------
X | O | O
---------
O |   | 

Your turn (0-8): 1
X | O | X
---------
X | O | O
---------
O |   | 

AI's turn...
X | O | X
---------
X | O | O
---------
O | X | 

Your turn (0-8): 8
X | O | X
---------
X | O | O
---------
O | X | O

It's a tie!

Ingat, karena tic-tac-toe adalah gim sederhana, tidak ada peluang untuk mengalahkan AI. Gim akan berakhir seri atau Anda kalah!

Memformalkan Algoritme Mini-max

Sekarang, mari tinjau definisi umum algoritme melampaui contoh tic-tac-toe sederhana.

Algoritme Minimax secara formal dapat didefinisikan sebagai fungsi rekursif yang mengevaluasi posisi dalam gim jumlah-nol. Mari uraikan komponen dan sifat formalnya.

Definisi matematis

Untuk keadaan gim s, nilai minimax V(s) didefinisikan sebagai:

V(s) =
   utility(s)                    if s is terminal
   max(V(s')) for all s' in S    if player = MAX
   min(V(s')) for all s' in S    if player = MIN

Di mana:

• s’ merepresentasikan keadaan penerus dari s
• S adalah himpunan semua langkah legal dari keadaan s
• utility(s) adalah fungsi evaluasi untuk keadaan terminal

Sifat kunci

1. Informasi sempurna

• Semua pemain memiliki pengetahuan lengkap tentang keadaan gim
• Tidak ada informasi tersembunyi atau unsur kebetulan
• Hasil deterministik

2. Sifat jumlah-nol

• Keuntungan satu pemain sama persis dengan kerugian pemain lain
• Jumlah utilitas untuk semua pemain selalu nol
• Untuk gim dua pemain, utilitas umumnya {-1, 0, 1}

3. Permainan optimal

• Mengasumsikan kedua pemain membuat keputusan optimal
• Menjamin hasil terbaik yang mungkin melawan permainan sempurna
• Mengarah pada ekuilibrium Nash dalam istilah teori permainan

Analisis kompleksitas

Kompleksitas waktu: O(b^m)

• b = faktor percabangan (jumlah langkah legal pada setiap keadaan)
• m = kedalaman maksimum pohon gim

Kompleksitas ruang: O(bm)

• Memerlukan penyimpanan keadaan gim pada setiap tingkat
• Dapat dioptimalkan dengan iterative deepening

Fungsi evaluasi

Untuk keadaan non-terminal, fungsi evaluasi f(s) harus:

1. Berkorelasi dengan probabilitas menang
2. Efisien secara komputasional
3. Menjaga skala yang konsisten sepanjang gim

Definisi formal:

f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ

Di mana:

• wᵢ adalah bobot untuk fitur yang berbeda
• xᵢ adalah nilai fitur dari keadaan gim
• n adalah jumlah fitur yang dievaluasi

Jaminan optimalitas

Algoritme Minimax menjamin permainan optimal di bawah kondisi berikut:

1. Informasi sempurna
2. Hasil deterministik
3. Pencarian lengkap hingga keadaan terminal
4. Evaluasi keadaan terminal yang akurat

Ini membuatnya sangat cocok untuk gim seperti catur, tic-tac-toe, dan dam, di mana kondisi-kondisi ini terpenuhi.

Variasi Lanjutan dan Keterbatasan

Walau Minimax bagus untuk gim sederhana seperti tic-tac-toe, ia memiliki masalah pada gim yang lebih besar. Mari lihat bagaimana kita dapat membuatnya lebih baik dan di mana ia kesulitan.

Membuat Minimax lebih cepat: Pemangkasan alpha-beta

Bayangkan Anda bermain catur dan memikirkan langkah-langkah Anda. Jika Anda menemukan langkah kemenangan, Anda tidak perlu memeriksa semua kemungkinan langkah lainnya, bukan? Pemangkasan Alpha-Beta bekerja dengan cara yang sama — membantu komputer melewati pemeriksaan langkah yang sudah kita tahu tidak akan lebih baik dari yang sudah ditemukan.

Pikirkan seperti ini:

• Anda berbelanja untuk batang cokelat termurah
• Anda punya $1 untuk dibelanjakan
• Jika Anda menemukan batang cokelat seharga 50¢, Anda bisa melewati cokelat apa pun yang harganya lebih dari $1
• Ini menghemat waktu Anda!

Batas kedalaman: Tidak melihat terlalu jauh ke depan

Dalam gim besar seperti catur, terlalu banyak kemungkinan langkah untuk diperiksa semuanya. Jadi kita tambahkan batas kedalaman:

1. Hanya melihat 4–5 langkah ke depan alih-alih sampai akhir
2. Memberi perkiraan yang baik tentang seberapa baik posisi saat itu
3. Memilih langkah terbaik berdasarkan perkiraan ini

Anda tidak bisa merencanakan setiap langkah hingga akhir gim, tapi Anda bisa merencanakan beberapa langkah ke depan!

Di mana Minimax kesulitan

Minimax tidak sempurna. Berikut masalah utamanya:

1. Terlalu banyak pilihan

• Gim seperti Go memiliki terlalu banyak kemungkinan langkah
• Bahkan komputer cepat pun tidak bisa memeriksa semuanya
• Itulah mengapa kita membutuhkan metode lain untuk gim yang sangat kompleks

2. Masalah waktu

• Semakin jauh Anda melihat ke depan, semakin lama waktunya
• Dalam catur, komputer tidak bisa melihat setiap kemungkinan langkah
• Mereka perlu cerdas dalam memilih langkah mana yang diperiksa

3. Kurang bagus untuk gim yang tidak pasti

• Minimax bekerja paling baik saat Anda bisa melihat semuanya
• Tidak bagus untuk gim kartu di mana Anda tidak tahu kartu apa yang dimiliki orang lain
• Tidak bisa menangani kejadian acak dengan baik (seperti lempar dadu)

Solusi modern

AI gim saat ini sering menggabungkan Minimax dengan teknik keren lainnya:

1. Pembelajaran mesin

• Komputer dapat belajar dari menonton banyak gim
• Ini membantu mereka membuat tebakan yang lebih baik tentang langkah yang bagus
• Gim seperti AlphaGo menggunakannya untuk mengalahkan juara manusia

2. Pengenalan pola

• Alih-alih memeriksa setiap langkah, cari pola
• Seperti halnya pemain manusia mengenali langkah yang bagus
• Ini membuat komputer jauh lebih cepat

3. Bank memori

• Mengingat posisi yang pernah dilihat sebelumnya
• Tidak membuang waktu menghitung hal yang sama dua kali
• Seperti punya contekan langkah-langkah bagus!

Bagian paling keren? Peningkatan ini membantu komputer bermain gim hampir sebaik manusia, dan kadang-kadang bahkan lebih baik! Namun ingat — bahkan dengan semua tambahan hebat ini, Minimax tetap fondasi yang membuat semuanya bekerja.

Kesimpulan

Dalam tutorial ini, kita telah mengeksplorasi algoritme Minimax dari konsep dasar hingga implementasi praktis. Berikut yang telah kita pelajari:

1. Konsep inti

• Bagaimana Minimax membantu komputer membuat keputusan dalam gim
• Perbedaan antara pemain meminimalkan dan memaksimalkan
• Mengapa disebut “minimax” dan bagaimana cara kerjanya

2. Keterampilan implementasi

• Membangun gim tic-tac-toe dari awal
• Menulis algoritme Minimax di Python
• Menguji dan men-debug logika gim

3. Topik lanjutan

• Membuat algoritme lebih cepat dengan Pemangkasan Alpha-Beta
• Menangani keterbatasan dalam gim yang kompleks
• Peningkatan modern menggunakan pembelajaran mesin

Apa Selanjutnya?

Algoritme Minimax hanyalah satu bagian dari teka-teki AI. Jika Anda tertarik mempelajari lebih jauh tentang AI dan algoritme, berikut beberapa sumber yang bagus untuk melanjutkan perjalanan Anda:

1. Algoritme terkait

• Tutorial Algoritme A* — Pelajari algoritme pencarian jalur
• Panduan Gradient Boosting — Jelajahi algoritme pembelajaran mesin

2. Aplikasi Pembelajaran Mesin

• Kasus Penggunaan Pembelajaran Mesin — Lihat aplikasi dunia nyata

3. Jalur Pembelajaran Lengkap

• Pengembangan Aplikasi AI — Bangun proyek AI praktis
• Dasar-dasar AI — Kuasai dasar-dasar AI

Ingat, apakah Anda membangun gim sederhana atau sistem AI yang kompleks, memahami algoritme seperti Minimax memberi Anda fondasi kuat untuk topik yang lebih lanjut dalam kecerdasan buatan. Terus berlatih, terus belajar, dan yang terpenting, terus ngoding!