mcts
1.0.0
ในบทช่วยสอนนี้ เราจะอธิบายอัลกอริทึม Monte Carlo Tree Search และแต่ละส่วนของโค้ด ล่าสุดเราใช้ MCTS เพื่อพัฒนาเกมของเรา
โค้ดนี้เป็นโค้ดทั่วไปและถือว่ามีความคุ้นเคยกับ Python พื้นฐานเท่านั้น เราได้อธิบายเกี่ยวกับเกมของเราแล้ว หากคุณต้องการใช้สำหรับโปรเจ็กต์หรือเกมของคุณ คุณจะต้องปรับเปลี่ยนฟังก์ชันที่ผมได้กล่าวถึงด้านล่างนี้เล็กน้อย
นี่คือลิงก์ playstore ไปยังเกม: Sudo Tic Tac Toe
กฎสำหรับเกมของเรา (โหมด 1) มีดังนี้:
อย่างที่คุณเห็นเกมนี้มีปัจจัยการแตกแขนงที่สูงมาก ในการย้ายครั้งแรกกระดานทั้งหมดจะว่างเปล่า มีจุดว่าง 81 จุด ในเทิร์นแรกจะมีการเคลื่อนไหวที่เป็นไปได้ 81 ครั้ง สำหรับเทิร์นที่สองโดยใช้กฎข้อ 4 จะมีการเคลื่อนไหวที่เป็นไปได้ 8 หรือ 9 ครั้ง
สำหรับ 2 การเคลื่อนไหวแรก ผลลัพธ์ที่ได้คือ 81*9 = 729 ชุดค่าผสมที่เป็นไปได้ ดังนั้นจำนวนของชุดค่าผสมที่เป็นไปได้จะเพิ่มขึ้นเมื่อเกมดำเนินไป ส่งผลให้มีปัจจัยการแตกแขนงสูง สำหรับทั้งสองโหมดของเกมของเรา ปัจจัยการแตกสาขานั้นสูงมาก สำหรับเกมที่มีปัจจัยการแตกสาขาสูง ไม่สามารถใช้อัลกอริธึม minimax ได้ อัลกอริทึม MCTS ใช้ได้กับเกมประเภทนี้
อย่างที่คุณจะได้เห็นจากการเล่นเกม เวลาที่ AI ใช้ในการเคลื่อนที่นั้นเป็นเพียงประมาณหนึ่งวินาทีเท่านั้น ดังนั้น MCTS จึงทำงานอย่างรวดเร็ว MCTS ถูกนำไปใช้กับทั้งสองโหมดของเกม
ด้านล่างนี้เราจะสาธิตโค้ด MCTS ใน Python ก่อนอื่นเราต้องนำเข้า numpy และ defaultdict
import numpy as np
from collections import defaultdictกำหนดคลาส MCTS ดังที่แสดงด้านล่าง
class MonteCarloTreeSearchNode ():
def __init__ ( self , state , parent = None , parent_action = None ):
self . state = state
self . parent = parent
self . parent_action = parent_action
self . children = []
self . _number_of_visits = 0
self . _results = defaultdict ( int )
self . _results [ 1 ] = 0
self . _results [ - 1 ] = 0
self . _untried_actions = None
self . _untried_actions = self . untried_actions ()
returnคลาสประกอบด้วยฟังก์ชันสมาชิกดังต่อไปนี้ ฟังก์ชันทั้งหมดด้านล่างนี้เป็นฟังก์ชันสมาชิก ยกเว้นฟังก์ชัน main()
def untried_actions ( self ):
self . _untried_actions = self . state . get_legal_actions ()
return self . _untried_actionsส่งคืนรายการการดำเนินการที่ยังไม่ได้ทดลองจากสถานะที่กำหนด สำหรับเทิร์นแรกของเกมของเรา มีการกระทำที่เป็นไปได้ 81 แบบ สำหรับเทิร์นที่สองคือ 8 หรือ 9 ซึ่งจะแตกต่างกันไปในเกมของเรา
def q ( self ):
wins = self . _results [ 1 ]
loses = self . _results [ - 1 ]
return wins - losesคืนส่วนต่างชนะ-ขาดทุน
def n ( self ):
return self . _number_of_visitsส่งกลับจำนวนครั้งที่แต่ละโหนดมีการเยี่ยมชม
def expand ( self ):
action = self . _untried_actions . pop ()
next_state = self . state . move ( action )
child_node = MonteCarloTreeSearchNode (
next_state , parent = self , parent_action = action )
self . children . append ( child_node )
return child_node จากสถานะปัจจุบัน สถานะถัดไปจะถูกสร้างขึ้นขึ้นอยู่กับการกระทำที่ดำเนินการ ในขั้นตอนนี้ สถานะที่เป็นไปได้ทั้งหมดจะถูกผนวกเข้ากับอาร์เรย์ของลูก และจะส่งกลับค่า child_node สถานะที่เป็นไปได้จากสถานะปัจจุบันจะถูกผนวกเข้ากับอาร์เรย์ย่อยทั้งหมด และจะส่งคืนค่า child_node ที่สอดคล้องกับสถานะนี้
def is_terminal_node ( self ):
return self . state . is_game_over ()ใช้เพื่อตรวจสอบว่าโหนดปัจจุบันเป็นเทอร์มินัลหรือไม่ ถึงโหนดเทอร์มินัลเมื่อเกมจบลง
def rollout ( self ):
current_rollout_state = self . state
while not current_rollout_state . is_game_over ():
possible_moves = current_rollout_state . get_legal_actions ()
action = self . rollout_policy ( possible_moves )
current_rollout_state = current_rollout_state . move ( action )
return current_rollout_state . game_result ()จากสถานะปัจจุบัน เกมทั้งหมดจะถูกจำลองจนกระทั่งมีผลการแข่งขัน ผลลัพธ์ของเกมนี้จะถูกส่งคืน ตัวอย่างเช่น หากส่งผลให้ชนะ ผลลัพธ์จะเป็น 1 มิฉะนั้นจะเป็น -1 หากส่งผลให้แพ้ และมันจะเป็น 0 ถ้ามันเสมอกัน หากทั้งเกมได้รับการสุ่มจำลอง นั่นคือในแต่ละตา การเคลื่อนไหวจะถูกเลือกแบบสุ่มจากชุดการเคลื่อนไหวที่เป็นไปได้ เรียกว่าการเล่นแบบเบา
def backpropagate ( self , result ):
self . _number_of_visits += 1.
self . _results [ result ] += 1.
if self . parent :
self . parent . backpropagate ( result )ในขั้นตอนนี้ สถิติทั้งหมดสำหรับโหนดจะได้รับการอัปเดต จนกว่าจะถึงโหนดหลัก จำนวนการเข้าชมสำหรับแต่ละโหนดจะเพิ่มขึ้น 1 หากผลลัพธ์เป็น 1 นั่นคือส่งผลให้ชนะ การชนะก็จะเพิ่มขึ้น 1 มิฉะนั้นหากผลลัพธ์คือแพ้ก็แพ้ เพิ่มขึ้นทีละ 1
def is_fully_expanded ( self ):
return len ( self . _untried_actions ) == 0การกระทำทั้งหมดจะแสดงออกมาจาก _untried_actions ทีละรายการ เมื่อว่างเปล่า นั่นคือเมื่อขนาดเป็นศูนย์ จะถูกขยายจนสุด
def best_child ( self , c_param = 0.1 ):
choices_weights = [( c . q () / c . n ()) + c_param * np . sqrt (( 2 * np . log ( self . n ()) / c . n ())) for c in self . children ]
return self . children [ np . argmax ( choices_weights )]เมื่อขยายจนสุดแล้ว ฟังก์ชันนี้จะเลือกรายการลูกที่ดีที่สุดจากอาร์เรย์ลูก เทอมแรกในสูตรสอดคล้องกับการหาประโยชน์ และเทอมที่สองสอดคล้องกับการสำรวจ
def rollout_policy ( self , possible_moves ):
return possible_moves [ np . random . randint ( len ( possible_moves ))]สุ่มเลือกการย้ายออกจากการเคลื่อนไหวที่เป็นไปได้ นี่คือตัวอย่างการเล่นแบบสุ่ม
def _tree_policy ( self ):
current_node = self
while not current_node . is_terminal_node ():
if not current_node . is_fully_expanded ():
return current_node . expand ()
else :
current_node = current_node . best_child ()
return current_nodeเลือกโหนดเพื่อเริ่มการเปิดตัว
def best_action ( self ):
simulation_no = 100
for i in range ( simulation_no ):
v = self . _tree_policy ()
reward = v . rollout ()
v . backpropagate ( reward )
return self . best_child ( c_param = 0. )นี่คือฟังก์ชันการดำเนินการที่ดีที่สุดซึ่งจะส่งคืนโหนดที่สอดคล้องกับการเคลื่อนไหวที่ดีที่สุดเท่าที่จะเป็นไปได้ ขั้นตอนการขยาย การจำลอง และการขยายพันธุ์กลับดำเนินการโดยใช้โค้ดด้านบน
def get_legal_actions ( self ):
'''
Modify according to your game or
needs. Constructs a list of all
possible states from current state.
Returns a list.
''' def is_game_over ( self ):
'''
Modify according to your game or
needs. It is the game over condition
and depends on your game. Returns
true or false
''' def game_result ( self ):
'''
Modify according to your game or
needs. Returns 1 or 0 or -1 depending
on your state corresponding to win,
tie or a loss.
''' def move ( self , action ):
'''
Modify according to your game or
needs. Changes the state of your
board with a new value. For a normal
Tic Tac Toe game, it can be a 3 by 3
array with all the elements of array
being 0 initially. 0 means the board
position is empty. If you place x in
row 2 column 3, then it would be some
thing like board[2][3] = 1, where 1
represents that x is placed. Returns
the new state after making a move.
''' def main ():
root = MonteCarloTreeSearchNode ( state , None , action )
selected_node = root . best_action ()
return นี่คือฟังก์ชัน main() เริ่มต้นโหนดรูทและเรียกใช้ฟังก์ชัน best_action เพื่อรับโหนดที่ดีที่สุด นี่ไม่ใช่ฟังก์ชันสมาชิกของคลาส ฟังก์ชันอื่นๆ ทั้งหมดเป็นฟังก์ชันสมาชิกของคลาส
MCTS ประกอบด้วย 4 ขั้นตอน:
แนวคิดคือการเลือกโหนดลูกที่ดีที่สุดต่อไปจนกว่าเราจะไปถึงโหนดใบของแผนผัง วิธีที่ดีในการเลือกโหนดลูกคือการใช้สูตร UCT (Upper Confidence Bound ที่ใช้กับต้นไม้):
wi/ni + c*sqrt(t)/ni
wi = จำนวนชัยชนะหลังจากการเคลื่อนไหวครั้งที่ i
ni = จำนวนการจำลองหลังการเคลื่อนที่ i-th
c = พารามิเตอร์การสำรวจ (ตามทฤษฎีเท่ากับ √2)
t = จำนวนการจำลองทั้งหมดสำหรับโหนดหลัก
เมื่อไม่สามารถใช้ UCT เพื่อค้นหาโหนดตัวตายตัวแทนได้อีกต่อไป มันจะขยายแผนผังเกมโดยผนวกสถานะที่เป็นไปได้ทั้งหมดจากโหนดปลายสุด
หลังจากการขยายตัว อัลกอริธึมจะเลือกโหนดลูกตามอำเภอใจ และจำลองเกมทั้งหมดจากโหนดที่เลือกจนกว่าจะถึงสถานะผลลัพธ์ของเกม หากมีการเลือกโหนดแบบสุ่มระหว่างการเล่น จะเรียกว่าการเล่นแบบเบา คุณยังสามารถเลือกที่จะเล่นอย่างหนักโดยการเขียนการวิเคราะห์พฤติกรรมที่มีคุณภาพหรือฟังก์ชันการประเมินผล
เมื่ออัลกอริทึมมาถึงจุดสิ้นสุดของเกม มันจะประเมินสถานะเพื่อดูว่าผู้เล่นคนไหนชนะ โดยจะลัดเลาะขึ้นไปถึงรูทและเพิ่มคะแนนการเข้าชมสำหรับโหนดที่เยี่ยมชมทั้งหมด นอกจากนี้ยังอัปเดตคะแนนการชนะสำหรับแต่ละโหนดหากผู้เล่นในตำแหน่งนั้นชนะการแข่งขัน
หากคุณวางแผนที่จะสร้างเกมของคุณเอง คุณจะต้องคิดถึงคำถามต่อไปนี้
ซูโด ติก แทค โท
หากคุณมีคำถามหรือข้อเสนอแนะ โปรดติดต่อเราที่ [email protected]
