การพัฒนาเกมแบบผลัดกันเล่น (Turn-based game) เป็นหนึ่งในงานที่ท้าทายทั้งสำหรับโปรแกรมเมอร์และนักพัฒนา AI (Artificial Intelligence) ด้วยเหตุนี้ Minimax Algorithm จึงเป็นเครื่องมือที่มีค่ายิ่งในการสร้างความท้าทายให้กับผู้เล่น โดยธรรมชาติของมันคือการทำงานในลักษณะที่พยายามทำนายและเลือกคำสั่งที่ดีที่สุดจากมุมมองของ AI เพื่อให้สามารถเอาชนะผู้เล่นได้
Minimax เป็น Algorithm ที่ใช้ในเกมที่มีสองผู้เล่น โดยหนึ่งในนั้นคือ AI ที่จะพยายามสร้าง 'game tree' ซึ่งเป็นโครงสร้างแบบต้นไม้ที่แสดงถึงทุกสถานการณ์ที่อาจเกิดขึ้นโดยพิจารณาจากการเคลื่อนไหวที่เป็นไปได้ทั้งหมด นั่นคือการทำนายทุกการเคลื่อนไหวทั้งของตัวเองและคู่แข่ง
Minimax ใช้สำหรับการเล่นเกมต่างๆ เช่น หมากรุก, โอเซลโล่ หรือ เกมตีขี้ เป็นต้น ที่มีลักษณะการเล่นของผู้เล่นสองฝ่ายที่ผลัดกันทำการเคลื่อนไหว โดยที่ Algorithm จะคำนวณความเป็นไปได้ของการเคลื่อนไหวแต่ละครั้งเพื่อเลือกการเคลื่อนไหวที่ดีที่สุดสำหรับ AI
#include
#include
#include
const int MAX = 1000;
const int MIN = -1000;
struct Move {
int row, col;
};
char player = 'x', opponent = 'o';
// This function evaluates the state of the board
int evaluate(char b[3][3]) {
// Checking for Rows for X or O victory.
// ...
// Checking for Columns for X or O victory.
// ...
// Checking for Diagonals for X or O victory.
// ...
// Else if none of them have won then return 0
return 0;
}
// This is the minimax function. It considers all the possible ways the game can go and returns the value of the board
int minimax(char board[3][3], int depth, bool isMax) {
int score = evaluate(board);
// If Maximizer has won the game return his/her evaluated score
if (score == 10)
return score;
// If Minimizer has won the game return his/her evaluated score
if (score == -10)
return score;
// If there are no more moves and no winner then it is a tie
if (isMovesLeft(board) == false)
return 0;
// If this maximizer's move
if (isMax) {
int best = MIN;
// Traverse all cells
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] == '_') {
// Make the move
board[i][j] = player;
// Call minimax recursively and choose the maximum value
best = std::max(best, minimax(board, depth + 1, !isMax));
// Undo the move
board[i][j] = '_';
}
}
}
return best;
}
// If this minimizer's move
else {
int best = MAX;
// Traverse all cells
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] == '_') {
// Make the move
board[i][j] = opponent;
// Call minimax recursively and choose the minimum value
best = std::min(best, minimax(board, depth + 1, !isMax));
// Undo the move
board[i][j] = '_';
}
}
}
return best;
}
}
// This will return the best possible move for the player
Move findBestMove(char board[3][3]) {
int bestVal = MIN;
Move bestMove;
bestMove.row = -1;
bestMove.col = -1;
// Traverse all cells, evaluate minimax function for all empty cells. And return the cell with optimal value.
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] == '_') {
// Make the move
board[i][j] = player;
// compute evaluation function for this move.
int moveVal = minimax(board, 0, false);
// Undo the move
board[i][j] = '_';
// If the value of the current move is more than the best value, then update best
if (moveVal > bestVal) {
bestMove.row = i;
bestMove.col = j;
bestVal = moveVal;
}
}
}
}
printf("The value of the best Move is : %d\n\n", bestVal);
return bestMove;
}
// Driver code
int main() {
char board[3][3] =
{
{ 'x', 'o', 'x' },
{ 'o', 'o', 'x' },
{ '_', '_', '_' }
};
Move bestMove = findBestMove(board);
printf("The Optimal Move is :\n");
printf("ROW: %d COL: %d\n\n", bestMove.row, bestMove.col );
return 0;
}
ในตัวอย่าง code ข้างต้นนี้ ได้อธิบายฟังก์ชันที่สำคัญๆ ของ Minimax Algorithm พร้อมทั้งนำมาใช้หาตำแหน่งเคลื่อนไหวที่ดีที่สุดในเกม Tic-Tac-Toe
Minimax Algorithm ไม่เพียงแต่ถูกใช้งานในเกมคลาสสิกเท่านั้น แต่ยังรวมไปถึงเกมที่มีความซับซ้อนสูง เช่น เกมในระดับแข่งขันอย่าง Dota 2 หรือ Starcraft II ที่ AI ต้องการการวิเคราะห์และวางกลยุทธ์ที่ซับซ้อนมากขึ้น
ความซับซ้อน (Complexity)
ในส่วนของการวิเคราะห์ความซับซ้อน (Complexity Analysis) ของ Minimax Algorithm พบว่ามีความซับซ้อนในระดับ O(b^d) โดยที่ b คือ branching factor (จำนวนเคลื่อนไหวที่เป็นไปได้ในแต่ละสเต็ป) และ d คือ depth of the tree (ระดับความลึกของต้นไม้เกม)
ข้อดี
- การทำนายที่แม่นยำ: Minimax ดีที่สุดในการทำนายผลลัพธ์ให้ได้มากที่สุดผ่านการคำนวณทั้งหมดเพื่อหาผลลัพธ์ที่ดีที่สุดสำหรับ AI - ความกระจ่าง: ทำให้ AI สามารถใช้กลยุทธ์ที่มีพื้นฐานจากกฎของเกมได้อย่างชัดเจนข้อเสีย
- ใช้ทรัพยากรมาก: การประมวลผลได้รับผลกระทบจาก exponential time complexity เนื่องจากมันต้องคำนวณทุกหนทางที่เป็นไปได้ - ไม่เหมาะกับเกมที่มี branching factor สูง: เช่นเกมหมากรุก หรือเกมที่มีปัจจัยซับซ้อนหลายอย่าง - ต้องการการปรับปรุง: มักจะต้องใช้ร่วมกับเทคนิคการตัด pruning, เช่น Alpha-Beta Pruning เพื่อลดจำนวนทางเลือกที่ต้องวิเคราะห์
เข้าใจโลกของ AI และเกมส์ผ่านการเรียนรู้ Minimax Algorithm เป็นการต่อยอดทักษะในการเขียนโปรแกรมได้อย่างล้ำลึก ที่สถาบัน EPT คุณจะได้พัฒนาความรู้ในด้านนี้ พร้อมทั้งเทคนิคการคิดเชิงวิเคราะห์ขั้นสูงผ่านการฝึกฝนและสั่งสมประสบการณ์ที่มีคุณภาพ ค้นพบพลังของตัวคุณกับหลักสูตรต่างๆ ที่เราจัดเตรียมไว้ เพื่อเป็นมือโปรในโลกของการเขียนโค้ดและ AI กับเราที่ EPT!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM