Đề bài
Minimax là cách các chương trình chơi game chọn nước đi: giả sử cả hai người chơi đều chơi hoàn hảo, chấm điểm mọi ván đã kết thúc, rồi đưa điểm ngược lên cây trò chơi. Người đến lượt chọn nhánh con có điểm cao nhất cho mình.
Bàn cờ là chuỗi 9 ký tự đọc theo từng hàng (chỉ số 0-8), gồm "X", "O" hoặc "." cho ô trống. X luôn đi trước, nên đến lượt X khi hai bên có số quân bằng nhau, ngược lại là lượt O.
Chấm điểm ván đã kết thúc theo góc nhìn của người đến lượt: +1 nếu thắng, 0 nếu hòa, -1 nếu thua. Trả về ô trống có điểm minimax tốt nhất; nếu nhiều ô tốt như nhau, trả về chỉ số nhỏ nhất.
Hãy viết best_move(board).
Đầu vào
board: Một thế cờ hợp lệ, chưa ai thắng và còn ít nhất một ô trống.
Đầu ra
Trả về chỉ số (0-8) của nước đi tốt nhất.
Ràng buộc
board có đúng 9 ký tự, mỗi ký tự là X, O hoặc .
Thế cờ có thể xuất hiện trong một ván thật, chưa ai thắng và còn ít nhất một ô trống
Ví dụ
Đầu vào:
board = "XX.OO...."
Kết quả mong đợi:
expected = 2Đầu vào:
std::string board = "XX.OO....";
Kết quả mong đợi:
long long expected = 2;Đầu vào:
string board = "XX.OO....";
Kết quả mong đợi:
long expected = 2;Giải thích
X và O mỗi bên có hai quân, nên đến lượt X. Đánh vào ô 2 hoàn thành hàng trên cùng và thắng ngay (+1).
Đầu vào:
board = "X..OO...X"
Kết quả mong đợi:
expected = 5Đầu vào:
std::string board = "X..OO...X";
Kết quả mong đợi:
long long expected = 5;Đầu vào:
string board = "X..OO...X";
Kết quả mong đợi:
long expected = 5;Giải thích
Đến lượt X. O đang dọa hoàn thành hàng giữa ở ô 5. Mọi nước khác đều để O thắng (-1), còn chặn ở ô 5 dẫn đến hòa (0), nên đáp án là 5.
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.