Java : เขียน AI ด้วย Minimax Algorithm – 3

เรานำหลักการของ Minimax Algorithm มาเขียนเป็นโปรแกรมในรูปแบบ recursive ซึ่งจะเรียกตัวเองไปเรื่อยๆเพื่อจำลองการเล่นที่จะเกิดขึ้นจนกว่าจะจบตามเงื่อนไขที่กำหนดคือต้องมีใครชนะหรือเสมอและกำหนดค่าเสียโอกาสตามที่กำหนด ซึ่งค่าเสียโอกาสจะถูกส่งกลับไปยังระดับชั้นความลึกก่อนหน้าเพื่อให้ผู้เล่นเลือกค่าเสียโอกาสตามบทบาทของตัวเอง และส่งค่าเสียโอกาสนั้นกลับขึ้นไปเป็นทอดๆจนกระทั่งระดับบนสุดซึ่งในโปรแกรมนี้คือ X ซึ่งจะเลือกดัชนีที่มีค่าเสียโอกาสสูงสุดไปใช้งาน

เริ่มจากเมธอดจะรับค่าอาเรย์ที่เป็นพื้นที่เล่นด้วยพารามิเตอร์ newBoard แต่เนื่องจากอาเรย์เป็นข้อมูลชนิด reference ดังนั้นการกระทำอะไรก็ตามจะมีผลกับอาเรย์โดยตรง ใช้พารามิเตอร์ player เพื่อรับค่าผู้เล่นว่าเป็น X หรือ O และใช้พารามิเตอร์ bestMove เพื่อเก็บค่าดัชนีที่จะนำไปใช้งาน

    public static int minimax (String[] newBoard, String player, int[] bestMove) { // minimax algorithm

จากนั้นสร้างอาเรย์ availSpots เพื่อเก็บค่าดัชนีของช่องที่ยังว่างอยู่

        int[] availSpots = emptyIndexies(newBoard); // define array to keep available position index

จากนั้นตรวจสอบว่า newBoard มีการชนะเกิดขึ้นแล้วหรือยัง หากมีให้ส่งค่าเสียโอกาสกลับไปยังระดับก่อนหน้า โดยหาก O ชนะให้ค่าเป็น -10 หาก X ชนะให้ค่าเป็น 10 และหากเสมอ คือไม่มีช่องว่างเหลือแล้วจากตรวจอาเรย์ availSpots มีขนาดเป็น 0 หรือไม่ และหากเสมอจะให้ค่าเป็น 0 ซึ่งโปรแกรมส่วนนี้คือจุดจบของ recursive

        if (winning(newBoard, "O" )){ // check if game over due to someone win or draw and return score
            return -10;
        } else if (winning(newBoard, "X" )){
            return 10;
        } else if (availSpots.length == 0){
            return 0;
        }

ประกาศอาเรย์ score เพื่อเก็บดัชนีของช่องที่ว่างคู่กับค่าเสียโอกาสของทุกวิธีการเพื่อเอาไปเลือกในส่วนท้ายของโปรแกรมในแต่ละระดับชั้นความลึก

        int[][] score = new int[availSpots.length][2]; // define ato keep mapping index and score

ใช้ลูป for เพื่อวนอ่านค่าดัชนีของช่องที่ว่างจาก availSpots มาเก็บไว้ในอาเรย์ score จากนั้นใส่ค่า X หรือ O ตามแต่รอบของผู้เล่นลงไปยังตำแหน่งดัชนีดังกล่าว จากนั้นสลับค่าของ player เป็นผู้เล่นอีกฝั่งและเรียกเมธอดตัวเอง ซึ่งก็คือการทำ recursive เพื่อจำลองการเล่นสลับกันไปมาที่จนถึงจุดจบตามเงื่อนไขคือการตรวจสอบหาผู้ชนะหรือการเสมอในโปรแกรมส่วนก่อนหน้านี้ ซึ่งค่าเสียโอกาสที่ส่งกลับมาจะถูกส่งมาเก็บที่อาเรย์ score โดยเก็บคู่ไว้คู่กับดัชนี เป็นเหมือนการให้คะแนนแต่ละดัชนี จากนั้นจึงคืนค่าที่เป็นดัชนีไปยัง newBoard ในตำแหน่งเดิมเพื่อทำให้อาเรย์ของ newBoard มีค่าเหมือนเดิมก่อนที่จะจำลองการเล่น ในขั้นตอนนี้จะต้องจินตนาการตามสักนิดว่าในแต่ละระดับชั้นจะเกิดอาเรย์ score ของตนเองซึ่งเมื่อถูกเลือกในขั้นตอนด้านล่างและคืนค่ากลับระดับบนแล้วอาเรย์ score ดังกล่าวก็จะหายไป ดังนั้นจะไม่มีการสับสนปนกัน

for (int i = 0; i < availSpots.length; i++) { // loop through all index for next simulation move
    score[i][0] = availSpots[i]; // keep index
    newBoard[availSpots[i]] = player; // try mark
    if (player.equals("X")) { // turn player for next simulation move
        player = "O";
    } else {
        player = "X";
    }
    score[i][1] = minimax(newBoard, player, bestMove); // simulate next move in recursive until end path and get score
    if (player.equals("X")) {
        player = "O";
    } else {
        player = "X";
    }
    newBoard[availSpots[i]] = String.valueOf(score[i][0]); // roll back board status for another move
}

ในขั้นตอนสุดท้ายของแต่ละระดับชั้นจะนำเอาข้อมูลในอาเรย์ score ซึ่งจะจับคู่ระหว่างดัชนีกับค่าเสียโอกาสมาเลือกดัชนีโดยดูจากค่าเสียโอกาส ซึ่งในกรณีที่เลือกโดย X จะเลือกค่าสูงและ O จะเลือกค่าต่ำ และเก็บค่าดัชนีไว้ในอาเรย์ bestMove

int bestScore = -1; // define variable tp keep best score
if (player.equals("X")){
    bestScore = -10000; // assign lowest value as initial value
    for(var i = 0; i < score.length; i++){ // loop check all available index to get +10 score
        if(score[i][1] > bestScore){
            bestScore = score[i][1];
            bestMove[0] = score[i][0];
        }
    }
} else {
    bestScore = 10000; // assign highest value as initial value
    for(var i = 0; i < score.length; i++){ // loop check all index available index to get -10 score
        if(score[i][1] < bestScore){
            bestScore = score[i][1];
            bestMove[0] = score[i][0];
        }
    }
}
return bestScore;

เราจะมาดูผลการทดวอบกันในหัวข้อถัดไป Java : เขียน AI ด้วย Minimax Algorithm – 4