尝试在我的井字游戏中实现 Minimax AI (javascript)
Trying to implement Minimax AI in my tic tac toe (javascript)
所以在阅读了一些关于 Minimax 的博客之后，例如 http://neverstopbuilding.com/minimax，从概念上我理解了，但是使用我当前的代码，我很难执行它。
到目前为止，我有一个非常简单的计算机 AI，它只是随机选择当前状态下的任何可用移动。
谁能告诉我 hint/tip 从哪里开始？我会假设创建类似新状态对象的东西但不确定..
$(document).ready(function(){
var human;
var computer;
var board = new Board()
var game;
function Human(symbol){
this.name = "Player",
this.symbol = symbol;
}
function Computer(symbol){
this.name = "Computer",
this.symbol = symbol;
}
//Modal opens when page is rendered. User can choose symbol
$("#myModal").modal()
$("#xPlayer").on('click',function(){
human = new Human("X");
computer = new Computer("O");
board.initalize();
game = new Game(human)
game.play();
})
$("#oPlayer").on('click',function(){
human = new Human("O")
computer = new Computer("X");
board.initalize();
game = new Game(computer)
game.play();
})
//Board constuctor
function Board(){
this.board = []
this.status = "";
}
//method calls for an empty board filled with "E"
Board.prototype.initalize = function(){
$("td p").empty()
this.board = ["E","E","E","E","E","E","E","E","E"]
this.status = "New Game";
}
//return true if there is a win. Otherwise, false
Board.prototype.win = function(){
var B = this.board;
//check row
for (var i = 0; i <= 6; i = i + 3){
if (B[i] !== "E" && (B[i] === B[i+1]) && (B[i+1] === B[i+2])){
board.status = "Winner is: " + game.currentPlayer.name
return true
}
}
//check column
for (var i = 0; i <= 2 ; i++ ){
if (B[i] !== "E" && (B[i] === B[i+3]) && (B[i+3] === B[i+6])){
board.status = "Winner is: " + game.currentPlayer.name
return true
}
}
//check diagonal
for(var i = 0, j = 4; i <= 2 ; i = i + 2, j = j - 2) {
if(B[i] !== "E" && (B[i] == B[i + j]) && (B[i + j] === B[i + 2 * j]) ) {
board.status = "Winner is: " + game.currentPlayer.name
return true;
}
}
return false
}
//checks if the current status is draw. If so, updates the status to "Draw"
Board.prototype.draw = function(){
//checks if the board itself is draw
for(var i = 0; i < this.board.length ; i++){
if (this.board[i] === "E"){
return false;
}
}
board.status = "Draw!"
return true;
}
//method returns array of indexes that are not empty cells in the board
Board.prototype.available = function(){
var B = this.board;
var indexes = [];
for (var i = 0; i < B.length ; i ++){
if (B[i] === "E"){
indexes.push(i)
}
}
return indexes;
}
//checks first if the User Input is valid or not
Board.prototype.validMove = function(position){
var availableCells = this.available();
return availableCells.includes(position);
}
//updates the board when using jQuery click
Board.prototype.updateBoard = function(position,playerInput) {
var availableCells = this.available();
if (availableCells.includes(position)){
this.board[position] = playerInput
}
};
function Game(firstPlayer){
this.currentPlayer = firstPlayer;
this.over = false;
this.win = "";
}
Game.prototype.switchPlayer = function(){
this.currentPlayer = (this.currentPlayer === human) ? computer : human
}
Game.prototype.restart = function(){
board.initalize();
}
Game.prototype.gameover = function(){
if (board.win() || board.draw()){
alert(board.status)
game.restart();
}
}
Game.prototype.play = function(){
board.status = "Game playing"
if(game.currentPlayer === computer){
computer.makeMove();
game.switchPlayer();
};
// console.log(game.currentPlayer)
$("td").click(function(){
var position = $(this).attr("id");
var positionNumber = parseInt(position.slice(4,5));
// This here renders to the board and updates board.board
if(board.validMove(positionNumber)){
//Checks if the move is valid. If it is, append it.
//Otherwise, alert the user that it is taken
$(this).find("p").append(game.currentPlayer.symbol)
board.updateBoard(positionNumber, game.currentPlayer.symbol)
//Check if it the game is over or draw
//If either is true, play new game
game.gameover();
game.switchPlayer();
if (game.currentPlayer.name === "Computer" ){
computer.makeMove();
game.gameover();
game.switchPlayer();
}
}else{
alert("Try Again!")
}
})
}
Computer.prototype.makeMove = function(){
var availableMoves = board.available()
// random move without any AI implementation
var computerPosition = availableMoves[Math.floor(Math.random() * availableMoves.length)];
$("#cell" + computerPosition + " p").append(game.currentPlayer.symbol);
board.updateBoard(computerPosition,game.currentPlayer.symbol)
}
})
body {
background: skyblue; }
#tictactoe {
max-width: 700px;
min-height: 300px;
margin: 68px auto;
display: flex;
width: 100%; }
#tictactoe table {
width: 100%;
font-size: 65px;
text-align: center;
vertical-align: middle;
table-layout: fixed; }
td {
height: 115px;
color: #101935;
background: #F2FDFF;
border: 5px solid #DBCBD8;
border-radius: 12px;
cursor: pointer;
transition: background 0.5s ease-out, color 0.5s ease-out; }
td:hover {
background: #564787;
color: #F2FDFF; }
.modal-dialog {
text-align: center; }
.modal-dialog .modal-footer {
text-align: center; }
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>TicTacToe FCC</title>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" integrity="sha384-1q8mTJOASx8j1Au+a5WDVnPi2lkFfwwEAa8hDDdjZlpLegxhjVME1fgjWPGmkzs7" crossorigin="anonymous">
<link rel="stylesheet" href="css/styles.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.2.4/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"></script>
</head>
<body>
<div id="tictactoe">
<table id="game-board">
<tbody>
<tr id="row1">
<td id="cell0"><p></p></td>
<td id="cell1"><p></p></td>
<td id="cell2"><p></p></td>
</tr>
<tr id="row2">
<td id="cell3"><p></p></td>
<td id="cell4"><p></p></td>
<td id="cell5"><p></p></td>
</tr>
<tr id="row3">
<td id="cell6"><p></p></td>
<td id="cell7"><p></p></td>
<td id="cell8"><p></p></td>
</tr>
</tbody>
</table>
</div>
<!--Modal Window -->
<div id="myModal" class="modal fade" role="dialog">
<div class="modal-dialog">
<div class="modal-content">
<div class="modal-header">
<h4 class="modal-title">Choose your character!</h4>
</div>
<div class="modal-body">
<p>Have fun!</p>
</div>
<div class="modal-footer">
<button type="button" id="xPlayer" class="btn btn-default" data-dismiss="modal">X</button>
<button type="button" id="oPlayer" class="btn btn-default" data-dismiss="modal">O</button>
</div>
</div>
</div>
</div>
</body>
<script src="js/javascript.js" type="text/javascript"></script>
</html>
这是基本思路，您必须填写 evaluate() 和 board.isTerminal() 的详细信息，并且可能还要调试它，因为我没有检查它。使用称为 negamax 的算法可以实现更清晰的实现，但请坚持使用它，直到您对它感到满意并且 why/how 它起作用。
Computer.prototype.makeMove = function() {
function evaluate(board) {
// if win for current player, return 1, loss return -1, tie return 0
}
function max(board) {
if (board.isTerminal()) return evaluate(board);
var successors = board.available();
var best = Number.NEGATIVE_INFINITY;
for(var i = 0; i < successors.length; i++) {
var moveScore = min(successors[i]);
best = Math.max(best, moveScore);
}
return best;
}
function min(board) {
if (board.isTerminal()) return evaluate(board);
var successors= board.available();
var best = Number.POSITIVE_INFINITY;
for(var i = 0; i < successors.length; i++) {
var moveScore = max(successors[i]);
best = Math.min(best, moveScore);
}
return best;
}
function selectMove(board) {
if (board.isTerminal()) throw "something went terribly wrong";
var successors = board.available();
var best = Number.NEGATIVE_INFINITY;
var bestMove = null;
for(var i = 0; i < successors.length; i++) {
var moveScore = min(successors[i]);
if (moveScore < best) {
bestMove = successors[i];
best = moveScore;
}
}
return bestMove;
}
var computerPosition = selectMove(board);
$("#cell" + computerPosition + " p").append(game.currentPlayer.symbol);
board.updateBoard(computerPosition,game.currentPlayer.symbol)
}
所以在阅读了一些关于 Minimax 的博客之后，例如 http://neverstopbuilding.com/minimax，从概念上我理解了，但是使用我当前的代码，我很难执行它。
到目前为止，我有一个非常简单的计算机 AI，它只是随机选择当前状态下的任何可用移动。
谁能告诉我 hint/tip 从哪里开始？我会假设创建类似新状态对象的东西但不确定..
$(document).ready(function(){
var human;
var computer;
var board = new Board()
var game;
function Human(symbol){
this.name = "Player",
this.symbol = symbol;
}
function Computer(symbol){
this.name = "Computer",
this.symbol = symbol;
}
//Modal opens when page is rendered. User can choose symbol
$("#myModal").modal()
$("#xPlayer").on('click',function(){
human = new Human("X");
computer = new Computer("O");
board.initalize();
game = new Game(human)
game.play();
})
$("#oPlayer").on('click',function(){
human = new Human("O")
computer = new Computer("X");
board.initalize();
game = new Game(computer)
game.play();
})
//Board constuctor
function Board(){
this.board = []
this.status = "";
}
//method calls for an empty board filled with "E"
Board.prototype.initalize = function(){
$("td p").empty()
this.board = ["E","E","E","E","E","E","E","E","E"]
this.status = "New Game";
}
//return true if there is a win. Otherwise, false
Board.prototype.win = function(){
var B = this.board;
//check row
for (var i = 0; i <= 6; i = i + 3){
if (B[i] !== "E" && (B[i] === B[i+1]) && (B[i+1] === B[i+2])){
board.status = "Winner is: " + game.currentPlayer.name
return true
}
}
//check column
for (var i = 0; i <= 2 ; i++ ){
if (B[i] !== "E" && (B[i] === B[i+3]) && (B[i+3] === B[i+6])){
board.status = "Winner is: " + game.currentPlayer.name
return true
}
}
//check diagonal
for(var i = 0, j = 4; i <= 2 ; i = i + 2, j = j - 2) {
if(B[i] !== "E" && (B[i] == B[i + j]) && (B[i + j] === B[i + 2 * j]) ) {
board.status = "Winner is: " + game.currentPlayer.name
return true;
}
}
return false
}
//checks if the current status is draw. If so, updates the status to "Draw"
Board.prototype.draw = function(){
//checks if the board itself is draw
for(var i = 0; i < this.board.length ; i++){
if (this.board[i] === "E"){
return false;
}
}
board.status = "Draw!"
return true;
}
//method returns array of indexes that are not empty cells in the board
Board.prototype.available = function(){
var B = this.board;
var indexes = [];
for (var i = 0; i < B.length ; i ++){
if (B[i] === "E"){
indexes.push(i)
}
}
return indexes;
}
//checks first if the User Input is valid or not
Board.prototype.validMove = function(position){
var availableCells = this.available();
return availableCells.includes(position);
}
//updates the board when using jQuery click
Board.prototype.updateBoard = function(position,playerInput) {
var availableCells = this.available();
if (availableCells.includes(position)){
this.board[position] = playerInput
}
};
function Game(firstPlayer){
this.currentPlayer = firstPlayer;
this.over = false;
this.win = "";
}
Game.prototype.switchPlayer = function(){
this.currentPlayer = (this.currentPlayer === human) ? computer : human
}
Game.prototype.restart = function(){
board.initalize();
}
Game.prototype.gameover = function(){
if (board.win() || board.draw()){
alert(board.status)
game.restart();
}
}
Game.prototype.play = function(){
board.status = "Game playing"
if(game.currentPlayer === computer){
computer.makeMove();
game.switchPlayer();
};
// console.log(game.currentPlayer)
$("td").click(function(){
var position = $(this).attr("id");
var positionNumber = parseInt(position.slice(4,5));
// This here renders to the board and updates board.board
if(board.validMove(positionNumber)){
//Checks if the move is valid. If it is, append it.
//Otherwise, alert the user that it is taken
$(this).find("p").append(game.currentPlayer.symbol)
board.updateBoard(positionNumber, game.currentPlayer.symbol)
//Check if it the game is over or draw
//If either is true, play new game
game.gameover();
game.switchPlayer();
if (game.currentPlayer.name === "Computer" ){
computer.makeMove();
game.gameover();
game.switchPlayer();
}
}else{
alert("Try Again!")
}
})
}
Computer.prototype.makeMove = function(){
var availableMoves = board.available()
// random move without any AI implementation
var computerPosition = availableMoves[Math.floor(Math.random() * availableMoves.length)];
$("#cell" + computerPosition + " p").append(game.currentPlayer.symbol);
board.updateBoard(computerPosition,game.currentPlayer.symbol)
}
})
body {
background: skyblue; }
#tictactoe {
max-width: 700px;
min-height: 300px;
margin: 68px auto;
display: flex;
width: 100%; }
#tictactoe table {
width: 100%;
font-size: 65px;
text-align: center;
vertical-align: middle;
table-layout: fixed; }
td {
height: 115px;
color: #101935;
background: #F2FDFF;
border: 5px solid #DBCBD8;
border-radius: 12px;
cursor: pointer;
transition: background 0.5s ease-out, color 0.5s ease-out; }
td:hover {
background: #564787;
color: #F2FDFF; }
.modal-dialog {
text-align: center; }
.modal-dialog .modal-footer {
text-align: center; }
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>TicTacToe FCC</title>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" integrity="sha384-1q8mTJOASx8j1Au+a5WDVnPi2lkFfwwEAa8hDDdjZlpLegxhjVME1fgjWPGmkzs7" crossorigin="anonymous">
<link rel="stylesheet" href="css/styles.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.2.4/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"></script>
</head>
<body>
<div id="tictactoe">
<table id="game-board">
<tbody>
<tr id="row1">
<td id="cell0"><p></p></td>
<td id="cell1"><p></p></td>
<td id="cell2"><p></p></td>
</tr>
<tr id="row2">
<td id="cell3"><p></p></td>
<td id="cell4"><p></p></td>
<td id="cell5"><p></p></td>
</tr>
<tr id="row3">
<td id="cell6"><p></p></td>
<td id="cell7"><p></p></td>
<td id="cell8"><p></p></td>
</tr>
</tbody>
</table>
</div>
<!--Modal Window -->
<div id="myModal" class="modal fade" role="dialog">
<div class="modal-dialog">
<div class="modal-content">
<div class="modal-header">
<h4 class="modal-title">Choose your character!</h4>
</div>
<div class="modal-body">
<p>Have fun!</p>
</div>
<div class="modal-footer">
<button type="button" id="xPlayer" class="btn btn-default" data-dismiss="modal">X</button>
<button type="button" id="oPlayer" class="btn btn-default" data-dismiss="modal">O</button>
</div>
</div>
</div>
</div>
</body>
<script src="js/javascript.js" type="text/javascript"></script>
</html>
这是基本思路，您必须填写 evaluate() 和 board.isTerminal() 的详细信息，并且可能还要调试它，因为我没有检查它。使用称为 negamax 的算法可以实现更清晰的实现，但请坚持使用它，直到您对它感到满意并且 why/how 它起作用。
Computer.prototype.makeMove = function() {
function evaluate(board) {
// if win for current player, return 1, loss return -1, tie return 0
}
function max(board) {
if (board.isTerminal()) return evaluate(board);
var successors = board.available();
var best = Number.NEGATIVE_INFINITY;
for(var i = 0; i < successors.length; i++) {
var moveScore = min(successors[i]);
best = Math.max(best, moveScore);
}
return best;
}
function min(board) {
if (board.isTerminal()) return evaluate(board);
var successors= board.available();
var best = Number.POSITIVE_INFINITY;
for(var i = 0; i < successors.length; i++) {
var moveScore = max(successors[i]);
best = Math.min(best, moveScore);
}
return best;
}
function selectMove(board) {
if (board.isTerminal()) throw "something went terribly wrong";
var successors = board.available();
var best = Number.NEGATIVE_INFINITY;
var bestMove = null;
for(var i = 0; i < successors.length; i++) {
var moveScore = min(successors[i]);
if (moveScore < best) {
bestMove = successors[i];
best = moveScore;
}
}
return bestMove;
}
var computerPosition = selectMove(board);
$("#cell" + computerPosition + " p").append(game.currentPlayer.symbol);
board.updateBoard(computerPosition,game.currentPlayer.symbol)
}