Coding the Unbeatable Tic-tac-toe A.I. with Python [1]
ဒီ Project မှာတော့ Tictactoe ကို ဘယ်တော့မှ မရှုံးအောင်ကစားနိုင်တဲ့ A.I. တစ်ခုကို ဖန်တီးသွားမှာပါ။ ဒီ A.I. လေးကို နားလည်ရလွယ်ပြီး အရမ်းအသုံးဝင်တဲ့ Minimax Algorithm သုံးပြီး ရေးမှာ ဖြစ်ပါတယ်။ ဒီ Project လေးကို ရေးရင်းနဲ့ Strategy game တွေထဲက A.I. Player တွေရဲ့ အခြေခံအလုပ်လုပ်ပုံကို နားလည်လာမှာဖြစ်ပြီး တစ်ခြားအဆင့်မြင့် ဂိမ်းတွေမှာပါ ကိုယ်ပိုင် A.I. တစ်ခုကို ရေးနိုင်လာမှာဖြစ်ပါတယ်။ ကုဒ်တွေကို Python နဲ့ ရေးပြထားတာဖြစ်ပေမယ့် JS တို့၊ Java တို့နဲ့ ရေးရင်လည်း Algorithm က သဘောတရားအတူတူပါပဲ။ Syntax ပဲ ပြောင်းသွားမှာပါ။
What is a Minimax algorithm?
Minimax Algorithm ဆိုတာ Computer တွေ ဆုံးဖြတ်ချက်ချတဲ့နေရာမှာ သုံးလေ့ရှိတဲ့ Recursive backtracking algorithm ပါ။
Function တစ်ခုထဲမှာ အဲဒီ Function ကိုပဲ ထပ်ခေါ်တာကို Recursive လို့ခေါ်ပါတယ်။ Backtracking ဆိုတာက ဖြစ်နိုင်ခြေအကုန်လုံးကို တွက်ပြီးတော့မှ ကိုယ့်အတွက် အကောင်းဆုံးလမ်းကို နောက်ပြန်ရှာတဲ့ နည်းပါ။
Minimax algorithm က ပြိုင်ဘက်ကစားသမားဟာ သူ့အတွက် အကောင်းဆုံးအကွက်တွေကို ကစားမယ်လို့ ယူဆပြီး ကိုယ့်အတွက် ရှုံးနိုင်ခြေအနည်းဆုံး ကစားကွက်ကို ရှာပေးတာဖြစ်ပါတယ်။
Minimax ကို တစ်ခြား Turn-based Strategy game တွေဖြစ်တဲ့ Chess, Checker တို့မှာလည်း သုံးနိုင်ပါတယ်။ ဒီ Tutorial မှာတော့ Tictactoe ဂိမ်းလေးမှာ နမူနာ အဖြစ် သုံးပြီး လေ့လာကြမှာ ဖြစ်ပါတယ်။ ဒီဂိမ်းလေးရေးပြီးရင် Checker နဲ့ Chess တို့လို အဆင့်မြင့်ဂိမ်းတွေမှာ Minimax အသုံးပြုပုံကို လေ့လာသွားမှာပါ။
Minimax Structure
Minimax ရဲ့ တည်ဆောက်ပုံကို Pseudo-code တွေနဲ့ လေ့လာကြည့်ပါမယ်။
Players
Minimax မှာ ကစားသမား ၂ ယောက်ရှိပါမယ်။ သူတို့ကို MaxPlayer နဲ့ MinPlayer လို့သတ်မှတ်လိုက်ပါတယ်။
Minimax က MaxPlayer အတွက် အကောင်းဆုံးကစားကွက်ကို ရှာပေးရမှာ ဖြစ်ပါတယ်။ ဒီနေရာမှာတော့ A.I. က MaxPlayer ဖြစ်ပြီး သူနဲ့ ကစားမယ့်လူက MinPlayer ဖြစ်ပါတယ်။
အကောင်းဆုံးကစားကွက်ကို ရှာနိုင်ဖို့အတွက် ဂိမ်းမှာ ဘယ်သူသာနေတယ်ဆိုတာကို သိရပါမယ်။ ဒီတော့ ကျွန်တော်တို့က State တစ်ခုစီမှာ ဂိမ်းရဲ့ အခြေအနေကို တန်ဖိုးတွက်ကြည့်မှာ ဖြစ်ပါတယ်။ ရလဒ်ကိုပြတဲ့ နေရာမှာ တစ်ကယ့် ကစားပွဲတွေမှာ ပြသလို 0-3, 5-2, 4-4 စသဖြင့် တစ်ဘက်စီမပြတော့ပါဘူး။ Overall score တစ်ခုသတ်မှတ်ပြီး အဲဒီထဲကမှ တစ်ဘက်ကသာရင် သာသလို ပေါင်းတာ၊ နုတ်တာတွေ လုပ်သွားပါမယ်။
ဒီ Score တွက်ပုံက Chess engine တွေ တွက်သလိုပါပဲ။ Chess engine တွေက Chessboard တစ်ခုကို တွက်တဲ့အခါမှာ အဖြူဘက်ကသာရင် Positive (+) နဲ့ ပြပြီး အနက်ဘက်က သာတယ်ဆိုရင် Negative (-) နဲ့ ပြပါတယ်။ ဉပမာ- Chess ကစားပွဲ တစ်ခုမှာ Evaluation (-5) ဆိုရင် လက်ရှိအခြေအနေမှာ အနက်ကစားသမားက ၅ မှတ်သာနေတယ်လို့ အဓိပ္ပါယ်ရပါတယ်။ Minimax အနေနဲ့ ကြည့်မယ်ဆိုရင် အဖြူက MaxPlayer ဖြစ်ပြီး အနက်က MinPlayer ဖြစ်ပါတယ်။ ရလဒ်တန်ဖိုးများရင် MaxPlayer က သာပြီး တန်ဖိုးနည်းရင် MinPlayer က သာပါတယ်။
ဒီတော့ MaxPlayer က ကစားကွက်ကို ရလဒ်အများဆုံးထွက်အောင် ကစားရမှာ ဖြစ်ပြီး MinPlayer ကတော့ ရလဒ်အနည်းဆုံးဖြစ်အောင် ကစားမှာဖြစ်ပါတယ်။ ဒါကို Minimax function ထဲမှာ နမူနာထည့်ပြပါမယ်။
def minimax(max_player):
if max_player:
max_the_score()
else:
min_the_score()Minimax က Recursive algorithm တစ်ခုဖြစ်တဲ့ အတွက် သူ့ကို ရပ်ပေးရမယ့် Final Condition တစ်ခုလိုပါတယ်။ ဒီလိုရပ်မပေးရင် Infinite loop ဖြစ်သွားနိုင်ပါတယ်။ဒီတော့ ဂိမ်းမှာ နိုင်တဲ့သူရှိသွားရင် ဒါမှမဟုတ် သရေကျသွားရင် Minimax function ကို ရပ်ပေးရပါမယ်။
def minimax(game, max_player):
if game.is_end():
return the_result
...
...Calculating The Game
Minimax ကို ဂိမ်းတစ်ခုမှာ သုံးတော့မယ်ဆိုရင် အဲဒီဂိမ်းရဲ့ လက်ရှိကစားကွက်တန်ဖိုးကို တွက်ပေးဖို့လိုပါတယ်။ Tictactoe ဂိမ်းမှာတော့ နောက်ဆုံး A.I. ဘက်ကနိုင်မယ်ဆိုရင် (+1) ရှုံးရင် (-1) နဲ့ သရေကျမယ်ဆိုရင် (0) လို့ ထုတ်ပေးပါမယ်။ တန်ဖိုးတွေက ၁၀ ဖြစ်ဖြစ် ၉၉ ဖြစ်ဖြစ် ကြိုက်တာ ထားလို့ရပါတယ်။ ဒီမှာတော့ ရှင်းအောင်လို့ ၁ နဲ့ပဲ တွက်ပါမယ်။ တစ်ကယ်လို့ Minimax ထဲမှာ (+1) နဲ့ (0) ဆိုပြီး ဖြစ်နိုင်ခြေနှစ်ခုရလာရင် MaxPlayer အနေနဲ့ (+1) ဖြစ်မယ့်လမ်းကို ရွေးမှာ ဖြစ်ပြီး MinPlayer ဆိုရင်တော့ (0) ဖြစ်အောင် ကစားမှာပါ။
def calculate_game():
if ai_win:
return +score
elif ai_lose:
return -score
else:
return 0Coding the Tic-tac-toe game
Minimax ရဲ့ သဘောတရားကို လေ့လာပြီးပြီဆိုတော့ သူ့ကို အသုံးချဖို့အတွက် Tictactoe ဂိမ်းတစ်ခု ရေးပေးရပါမယ်။ ဒီနေရာမှာ ကျွန်တော်ရေးထားတဲ့ Tictactoe ဂိမ်းလေးကို အသုံးပြုသွားပါမယ်။ ဂိမ်းရေးပုံအဆင့်ဆင့်ကိုတော့ မဖော်ပြတော့ပါဘူး။ အဓိက Algorithm နဲ့ ဆိုင်တဲ့ အပိုင်းလေးတွေကိုပဲ ရှင်းပြပါမယ်။ ဒီ Tictactoe ဂိမ်းထဲမှာ Board နဲ့ Gui ဆိုပြီး Module နှစ်ခု ပါပါတယ်။ ဂိမ်းနဲ့ သက်ဆိုင်တဲ့ လုပ်ဆောင်ချက်တွေကို Board ထဲမှာ ရေးထားပြီး Gui ကတော့ Pygame ကိုသုံးပြီး ဂိမ်းမျက်နှာပြင်နဲ့ Board ကို ချိတ်ဆက်ပေးတာပါ။ ကိုယ်က Algorithm ကိုပဲ အဓိက လေ့လာချင်တယ်ဆိုရင် Pygame gui တွေ ဘာတွေ ရေးစရာမလိုပါဘူး။ CLI ထဲမှာ ကစားလို့ရမယ့် Text-based Tictactoe ဂိမ်းလေးတစ်ခုပဲ ရေးလိုက်ပါ။ ရေးပြီးသားရှိရင်လည်း Algorithm အတွက် လိုအပ်တဲ့ အပိုင်းတွေကို ပြင်ပြီး သုံးလို့ရပါတယ်။ ဂိမ်းကို ကိုယ်တိုင်ရေးချင်တဲ့ သူတွေအတွက် Board ထဲမှာ လုပ်ဆောင်နိုင်ရမယ့် အဓိက Function တွေကို ပုံမှာပြပေးထားပါတယ်။ ကုဒ်အပြည့်အစုံကိုတော့ အောက်က Link မှာ လေ့လာနိုင်ပါတယ်။
Board Module --> Tictactoe Board Module - Pastebin.com
ဒီဂိမ်းလေးကို run နိုင်ဖို့ Program တစ်ခုရေးရပါမယ်။ ကျွန်တော်အောက်မှာ ရေးပြထားတာနဲ့ တစ်ပုံစံတည်းဖြစ်စရာမလိုပါဘူး။ အဓိကက Player နှစ်ယောက်တစ်ယောက်တစ်လှည့်စီ ကစားနိုင်ပြီး အနိုင်အရှုံးပြပေးနိုင်ဖို့ပဲ လိုပါတယ်။
from tictactoe.board import Board
from tictactoe.gui import Gui
import pygame
def main():
board = Board()
player = board.P1
ai_player = board.P2
gui = Gui(board, "Tic Tac Toe")
clock = pygame.time.Clock()
running = True
while running:
gui.update_display()
clock.tick(60)
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
if event.type == pygame.MOUSEBUTTONUP:
if board.is_gameover():
board.reset()
continue
tile = gui.get_clicked_tile(event.pos)
if tile is not None:
board.move(tile)
if __name__ == "__main__":
main()ဒါကို run လိုက်ရင် Tictactoe ဂိမ်းလေးကို ကစားလို့ရလာမှာ ဖြစ်ပါတယ်။ ကိုယ်ရဲ့ ဂိမ်းလေးက ဒီအဆင့်ထိ ကစားလို့ရပြီဆိုရင် Minimax ကို သုံးပြီး A.I. Player စရေးလို့ ရပါပြီ။ ဒီ Post ကိုတော့ ဒီမှာ ရပ်ထားပြီး Minimax algorithm ကို နောက်တစ်ဆင့် မှာ ဆက်ရေးကြပါမယ်။ အခုရှင်းပြထားတဲ့ Algorithm အလုပ်လုပ်ပုံနဲ့ ပတ်သက်ပြီး နားမလည်တာရှိရင် Comment ကနေဖြစ်ဖြစ်၊ Facebook Messenger ကနေဖြစ်ဖြစ် မေးမြန်းနိုင်ပါတယ်။
Happy Coding!