#javascript #algorithm #math
#javascript #алгоритм #математика
Вопрос:
Я работал над простой игрой в крестики-нолики и наткнулся на кирпичную стену.
В то время как большинство функций игр на месте, мне не хватает важного алгоритма, необходимого для правильного размещения компьютерной плитки.
Мне нужен алгоритм, который может выполнять поиск по сетке 3×3 из плиток и искать, где лучше всего разместить компьютерную плитку в сетке.
Я был бы благодарен за любое направление или понимание того, как я могу разработать этот алгоритм.
Неполный алгоритм игры в крестики-нолики:
function placeComputerTile(el){
if(computerTurn === true amp;amp; userTurn === false){
var tileIsEmpty = true;
// If the selected tile has at least one child,
// do not allow placement of another tile.
if (el.firstChild) {
tileIsEmpty = false;
}
if(tileIsEmpty === true){
cloneComputerIcon();
}
el.appendChild(newComputerIcon);
addClass(el, "x");
newComputerIcon.style.display = null;
}
}
Полный Javascript:
var gameIcons = document.getElementsByClassName('gameIcon');
var turnDisplays = document.getElementsByClassName('turnDisplay');
for (var i = 0; i < gameIcons.length; i ) {
gameIcons[i].style.display = 'none';
}
for (var i = 0; i < turnDisplays.length; i ) {
turnDisplays[i].style.display = 'none';
}
var userTurn = true;
var computerTurn = false;
var currentTurn = 1;
var maxTurn = 10;
var userTurnDisplay = document.getElementById("userTurnDisplay");
var computerTurnDisplay = document.getElementById("computerTurnDisplay");
function evaluateTurn(){
currentTurn = 1;
for(var i = 0; i < maxTurn; i ) {
if(currentTurn % 2 === 0){
userTurn = true;
computerTurn = false;
}else if(currentTurn % 2 !== 0){
userTurn = false;
computerTurn = true;
}
}
if(currentTurn === maxTurn){
alert("Draw!");
userTurnDisplay.style.display = "none";
computerTurnDisplay.style.display = "none";
}
//Change display depending on players turn.
if(userTurn === true amp;amp; currentTurn !== maxTurn) {
computerTurnDisplay.style.display = null;
userTurnDisplay.style.display = "none";
}else if(computerTurn === true amp;amp; currentTurn !== maxTurn){
userTurnDisplay.style.display = null;
computerTurnDisplay.style.display = "none";
}
}
var cloneUserIcon = function(){
var userIcon = document.getElementById("userIcon");
newUserIcon = userIcon.cloneNode(true);
}
var cloneComputerIcon = function(){
var computerIcon = document.getElementById("computerIcon");
newComputerIcon = computerIcon.cloneNode(true);
}
function addClass(el, className) {
if (el.classList)
el.classList.add(className)
else if (!hasClass(el, className)) el.className = " " className
}
function placeUserTile(el){
if(userTurn === true amp;amp; computerTurn === false){
var tileIsEmpty = true;
// If the selected tile has at least one child,
// do not allow placement of another tile.
if (el.firstChild) {
tileIsEmpty = false;
}
if(tileIsEmpty === true){
cloneUserIcon();
}
el.appendChild(newUserIcon);
addClass(el, "o");
newUserIcon.style.display = null;
}
}
///////////////////////////////////////////////////////////////////////////////
// computer move logic //
// //
function placeComputerTile(el){
if(computerTurn === true amp;amp; userTurn === false){
var tileIsEmpty = true;
// If the selected tile has at least one child,
// do not allow placement of another tile.
if (el.firstChild) {
tileIsEmpty = false;
}
if(tileIsEmpty === true){
cloneComputerIcon();
}
el.appendChild(newComputerIcon);
addClass(el, "x");
newComputerIcon.style.display = null;
}
}
// //
// //
///////////////////////////////////////////////////////////////////////////////
// Search an array of tiles.
function hasTile(tilesArray){
var allHaveChild = tilesArray.length > 0;
for(var i = 0; i < tilesArray.length; i ){
if(!tilesArray[i].firstChild){
allHaveChild = false;
}
}
if(allHaveChild)
return true;
else
return false;
}
function hasClass(element, className) {
return element.className amp;amp; new RegExp("(^|\s)" className "(\s|$)").test(element.className);
}
// Row 1 Tiles
const R1C1 = document.getElementById('r1c1');
const R1C2 = document.getElementById('r1c2');
const R1C3 = document.getElementById('r1c3');
//
// // Row 2 Tiles
const R2C1 = document.getElementById('r2c1');
const R2C2 = document.getElementById('r2c2');
const R2C3 = document.getElementById('r2c3');
//
// // Row 3 Tiles
const R3C1 = document.getElementById('r3c1');
const R3C2 = document.getElementById('r3c2');
const R3C3 = document.getElementById('r3c3');
//Set of all row tiles
var rowOneTiles = [R1C1,R1C2,R1C3];
var rowTwoTiles = [R2C1,R2C2,R2C3];
var rowThreeTiles = [R3C1,R3C2,R3C3];
// Set of all column tiles
var columnOneTiles = [R1C1,R2C1,R3C1];
var columnTwoTiles = [R1C2,R2C2,R3C2];
var columnThreeTiles = [R1C3,R2C3,R3C3];
//Set of left-diagonal amp; right-diagonal tiles
var leftDiagonalTiles = [R1C1,R2C2,R3C3];
var rightDiagonalTiles = [R1C3,R2C2,R3C1];
function checkRow1(){
// If the entire row is filled:
if(hasTile(rowOneTiles)){
var el_1 = rowOneTiles[0];
var el_2 = rowOneTiles[1];
var el_3 = rowOneTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkRow2(){
// If the entire row is filled:
if(hasTile(rowTwoTiles)){
var el_1 = rowTwoTiles[0];
var el_2 = rowTwoTiles[1];
var el_3 = rowTwoTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkRow3(){
// If the entire row is filled:
if(hasTile(rowThreeTiles)){
var el_1 = rowThreeTiles[0];
var el_2 = rowThreeTiles[1];
var el_3 = rowThreeTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkColumn1(){
// If the entire row is filled:
if(hasTile(columnOneTiles)){
var el_1 = columnOneTiles[0];
var el_2 = columnOneTiles[1];
var el_3 = columnOneTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkColumn2(){
// If the entire row is filled:
if(hasTile(columnTwoTiles)){
var el_1 = columnTwoTiles[0];
var el_2 = columnTwoTiles[1];
var el_3 = columnTwoTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkColumn3(){
// If the entire row is filled:
if(hasTile(columnThreeTiles)){
var el_1 = columnThreeTiles[0];
var el_2 = columnThreeTiles[1];
var el_3 = columnThreeTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkLeftDiagonal(){
// If the entire row is filled:
if(hasTile(leftDiagonalTiles)){
var el_1 = leftDiagonalTiles[0];
var el_2 = leftDiagonalTiles[1];
var el_3 = leftDiagonalTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkRightDiagonal(){
// If the entire row is filled:
if(hasTile(rightDiagonalTiles)){
var el_1 = rightDiagonalTiles[0];
var el_2 = rightDiagonalTiles[1];
var el_3 = rightDiagonalTiles[2];
if(hasClass(el_1,"x") amp;amp; hasClass(el_2,"x") amp;amp; hasClass(el_3,"x")){
alert("Sorry, you've lost.");
}else if(hasClass(el_1,"o") amp;amp; hasClass(el_2,"o") amp;amp; hasClass(el_3,"o")){
alert("Congratulations, you've won!");
}
}
}
function checkForWin(){
checkRow1();
checkRow2();
checkRow3();
checkColumn1();
checkColumn2();
checkColumn3();
checkLeftDiagonal();
checkRightDiagonal();
}
function main(el){
evaluateTurn();
if(userTurn === true){
placeUserTile(el);
}
if(computerTurn === true){
placeComputerTile(el);
}
checkForWin();
}
Полный HTML:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<title>Tic-Tac-Toe</title>
<!-- Latest compiled and minified JavaScript -->
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js" integrity="sha384-Tc5IQib027qvyjSMfHjOMaLkfuWVxZxUPnCJA7l2mCWNIpG9mGCD8wGNIcPD7Txa" crossorigin="anonymous"></script>
<!-- Latest compiled and minified CSS -->
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" integrity="sha384-BVYiiSIFeK1dGmJRAkycuHAHRg32OmUcww7on3RYdg4Va PmSTsz/K68vbdEjh4u" crossorigin="anonymous">
<!-- Custom CSS -->
<link rel="stylesheet" href="styles/game.css">
</head>
<body>
<div class="container">
<h1>Tic-Tac-Toe</h1>
</div>
<div class="container" id="tileContainer">
<!-- id listed by row-column notation. -->
<div class="row">
<div class="col-xs-6 col-md-12 tile rowOne columnOne" id="r1c1" onclick="main(this)"></div>
<div class="col-xs-6 col-md-12 tile rowOne columnTwo" id="r1c2" onclick="main(this)"></div>
<div class="col-xs-6 col-md-12 tile rowOne columnThree" id="r1c3" onclick="main(this)"></div>
</div>
<div class="row">
<div class="col-xs-6 col-md-12 tile rowTwo columnOne" id="r2c1" onclick="main(this)"></div>
<div class="col-xs-6 col-md-12 tile rowTwo columnTwo" id="r2c2" onclick="main(this)"></div>
<div class="col-xs-6 col-md-12 tile rowTwo columnThree" id="r2c3" onclick="main(this)"></div>
</div>
<div class="row">
<div class="col-xs-6 col-md-12 tile rowThree columnOne" id="r3c1" onclick="main(this)"></div>
<div class="col-xs-6 col-md-12 tile rowThree columnTwo" id="r3c2" onclick="main(this)"></div>
<div class="col-xs-6 col-md-12 tile rowThree columnThree" id="r3c3" onclick="main(this)"></div>
</div>
</div>
<!-- End of tile container -->
<div class="container" id="turnDisplayContainer">
<div class="row">
<div class="col-xs-9 col-md-6 turnDisplay" id="userTurnDisplay">
<h4>Your Turn</h4>
</div>
<div class="col-xs-9 col-md-6 turnDisplay" id="computerTurnDisplay">
<h4>Computer's Turn</h4>
</div>
</div>
</div>
<img class="img img-responsive gameIcon" src="assets/img/green-ring.png" alt="Green Ring Icon" id="userIcon" />
<img class="img img-responsive gameIcon" src="assets/img/red-x.png" alt="Red X Icon" id="computerIcon" />
<!-- Custom JS -->
<script type="text/javascript" src="scripts/game.js"></script>
</body>
</html>
Полный CSS:
h1{
text-align: center;
}
h4{
text-align: center;
}
.container{
margin: 0px;
padding: 0px;
width: auto;
}
.row{
margin: 0 auto;
max-width: 300px;
}
.tile{
width: 100px;
height: 100px;
border: 1px solid blue;
background-color: white;
}
Ответ №1:
Взгляните на эту ссылку: http://userpages.umbc.edu /~hoban/FLEX/CourseDocs/TicTacToe.pdf
Подумайте о том, как вы играете в крестики-нолики, как о серии утверждений «если-то»: «ЕСЛИ я пойду первым, ТОГДА поставьте крестик посередине». «ЕСЛИ у моего оппонента два O подряд (сумма количества O в строке, столбце или по диагонали = 2), ТО поставьте X в этой строке» и т.д. и т.п.
Сформулируйте правила, которые вы сами используете во время игры.
Ответ №2:
прокрутите вниз, если вы не хотите умирать от скуки и хотите увидеть реальный код
Типичными алгоритмами, используемыми для этого, являются minimax или alpha beta, при этом alpha beta является оптимизированной версией minimax (вероятно, немного излишне для tac tic toe). Оба они в основном представляют собой поиск в глубину возможных позиций, которые вы можете получить, где вы ищете наилучшую возможную позицию. Вот базовый пример того, как выглядит процедура (попытка объяснения ниже):
max(8,2) 8
/
min(9,8) 8 2 min(7,2)
/ /
9 8 7 2
Вот моя реализация минимакса:
/**
* initialize MiniMax(0, player1) where player1 is computer
* @param depth current depth or degree
* @param player either MAX or MIN
* @return int[] {score,bestRow,bestCol}
*/
int[] miniMax(int depth, int player) {
// list of possible columns to place a checker
List<int[]> moves = nextMoves();
int bestRow = -1;
int bestCol = -1;
int previousPlayer = (player 1) amp; 1;
// if you reached maximum depth or node is a terminal node (game ending position)
// i.e. if (current position has a 3 in row || you reached maximum depth || the board is full (draw))
if (isWin(previousPlayer) || (depth == this.depth) || moves.isEmpty()) {
return new int[]{eval(), bestRow, bestCol};
}
// best current value
int v;
// if its MAX's turn (computer)
if (player==0) {
// assume worst case, MAX value is -infinity,
// and if better value appears replace v with it
v = -inf;
// for each available move
for (int[] move : moves) { // move = {row,column}
makeMove(move[0],move[1],0);
int score = miniMax(depth 1,1)[0];
undoMove(move[0],move[1],0);
// if score is better then update v
if (score > v) {
v = score;
bestRow = move[0];
bestCol = move[1];
}
}
return new int[] {v,bestRow,bestCol};
}
// if its MIN's turn (opponent)
else {
// assume worst case, MIN value is infinity,
// and if better value appears replace v with it
v = inf;
// for each available move
for (int[] move : moves) { // move = {row,column}
makeMove(move[0],move[1],1); // make move
int score = miniMax(depth 1,0)[0];
undoMove(move[0],move[1],1); // undo move
// if score is better then update v
if (v > score) {
v = score;
bestRow = move[0];
bestCol = move[1];
}
}
return new int[] {v,bestRow,bestCol};
}
}
Для 2 игроков вы назначаете каждому бросок:
1. maximizing player (the computer)
2. minimizing player (the computer's opponent)
maximizing player Принимает max возможные доступные ходы, аналогично minimizing player принимает min возможные доступные ходы.
Чтобы прояснить эту операцию, учитывая позицию, на которую вы смотрите (или позицию, полученную в результате 1 из ваших возможных ходов), вы присваиваете ей значение с помощью некоторой функции вычисления или эвристики. Например, если бы я играл X и имел позицию:
=======
|O|X| |
=======
| |X|O|
=======
| |X| |
=======
заданное значение будет ∞ (или какое-то большое число), поскольку я уже выиграл. Но если бы у меня была позиция:
=======
|O| | |
=======
|O|X| |
=======
|X| |X|
=======
пока X еще не выиграл (нет 3 подряд на борту), гарантированный выигрыш для X . Но если бы мы хотели присвоить значение текущему состоянию доски, предполагая, что мы допустили положительное значение, означающее, что позиция хороша X , мы бы сделали ее положительной. Чтобы удовлетворить это, вы могли бы, например, предположить, что в строках нет 3, посчитать все открытые 2 в строках и вернуть это как значение позиции:
value (position){
if position has a 3 in row return infinity
result = 0
add 1 to result for each 2 in row with an empty space in between
return result
}
Итак, для приведенного выше примера вы бы присвоили ему значение 2 (нижняя горизонталь плюс диагональ, идущая вверх вправо). Существуют и другие, более эффективные способы выполнения функции вычисления, но приведенного выше достаточно. Вы также можете просто return infinity выиграть на доске, но ваша глубина поиска может быть большой, не то чтобы это было проблемой в tic tac toe.
Вот класс java с методом main (и примером) внизу, если вы хотите его попробовать:
import java.util.*;
public class f {
int inf = 1000000000; // infinity
int depth;
char computer = 'O';
char opponent = 'X';
/*
[0] = computer
[1] = opponent
the computer and opponent's moves are stored in binary numbers
where 1 represents that a checker is there and 0 represents an
empty space
=======
|O|O| |
=======
| |X| |
=======
| |X| |
=======
the above board would be represented by:
computer = 110000000 (computer is 'O')
opponent = 000010010 (opponent is 'X')
*/
int[] playerBoards = {0b100010000,0b000000000};
// count number of bits in i
int count(int i){
int n = 0;
while(i!=0){
i = i amp; (i-1);
n ;
}
return n;
}
void printBoard(){
int p1 = playerBoards[0];
int p2 = playerBoards[1];
int count = 1 << 8;
String line = "";
String border = "=======";
System.out.println(border);
for(int i=0; i < 12; i ){
if ((i 1)%4 == 0) {
line = "|" line;
System.out.println(line);
System.out.println(border);
line = "";
continue;
}
if ((p1 amp; count) > 0) {
line = computer "|";
}
else if ((p2 amp; count) > 0){
line = opponent "|";
}
else line = " |";
count = count >> 1;
}
}
// turn on the nth bit
void makeMove(int row,int col,int player){
playerBoards[player] |= 1 << 8 - row*3 - col;
}
// turn off the nth bit
void undoMove(int row,int col,int player){
playerBoards[player] ^= 1 << 8 - row*3 - col;
}
List<int[]> nextMoves(){
int p = playerBoards[0]^playerBoards[1];
List<int[]> moves = new ArrayList<>();
for(int i = 8; i >= 0; i--){
if((p amp; 1) == 0) moves.add(new int[]{i/3,i%3});
p = p >> 1;
}
return moves;
}
// check if current position has a win (3 in row)
boolean isWin(int player) {
int board = playerBoards[player];
// vertical
if ((board amp; board>>3 amp; board>>6) != 0) return true;
// horizontal
if ((board amp; board>>1 amp; board>>2) != 0) return true;
// left diagonal
if ((board amp; board>>4 amp; board>>8) != 0) return true;
// right diagonal
if ((board amp; board>>2 amp; board>>4) != 0) return true;
return false;
}
/**
* Static evaluation (heuristic): if there is an open 2 i.e. there is a 2 in row with an
* empty space in between then add 1 to result
*
* @param player is either 0 or 1 for the computer and opponent respectively
* @return the value of the current position
*/
int evaluation(int player){
int board = playerBoards[player];
if (isWin(player)) return inf;
int opponent = playerBoards[(player 1) amp; 1];
int result = 0;
// open vertical
int a = board amp; (board<<3);
int b = board amp; (board<<6);
int c = (board << 3) amp; (board << 6);
if (a!=0 amp;amp; (aamp;(opponent<<6))==0)
result = count(a);
if (b!=0 amp;amp; (bamp;(opponent<<3))==0)
result = count(b);
if (c!=0 amp;amp; (camp;opponent)==0)
result = count(c);
// open horizontal
a = board amp; (board<<1);
b = board amp; (board<<2);
c = (board << 1) amp; (board << 2);
if (a!=0 amp;amp; (aamp;(opponent<<2))==0)
result = count(a);
if (b!=0 amp;amp; (bamp;(opponent<<1))==0)
result = count(b);
if (c!=0 amp;amp; (camp;opponent)==0)
result = count(c);
// open left diagonal
a = board amp; (board<<4);
b = board amp; (board<<8);
c = (board << 4) amp; (board << 8);
if (a!=0 amp;amp; (aamp;(opponent<<8))==0)
result = count(a);
if (b!=0 amp;amp; (bamp;(opponent<<4))==0)
result = count(b);
if (c!=0 amp;amp; (camp;opponent)==0)
result = count(c);
// open rght diagonal
a = board amp; (board<<2);
b = board amp; (board<<4);
c = (board << 2) amp; (board << 4);
if (a!=0 amp;amp; (aamp;(opponent<<4))==0)
result = count(a);
if (b!=0 amp;amp; (bamp;(opponent<<2))==0)
result = count(b);
if (c!=0 amp;amp; (camp;opponent)==0)
result = count(c);
return resu<
}
// player1's score - player2's score
int eval() {return evaluation(0) - evaluation(1);}
/**
* initialize MiniMax(0, player1) where player1 is computer
* @param depth current depth or degree
* @param player either MAX or MIN
* @return int[] {score,bestRow,bestCol}
*/
int[] miniMax(int depth, int player) {
// list of possible coordinates to place a checker
List<int[]> moves = nextMoves();
int bestRow = -1;
int bestCol = -1;
int previousPlayer = (player 1) amp; 1;
// if you reached maximum depth or node is a terminal node (game ending position)
// i.e. if (current position has a 3 in row || you reached maximum depth || the board is full (draw))
if (isWin(previousPlayer) || (depth == this.depth) || moves.isEmpty()) {
return new int[]{eval(), bestRow, bestCol};
}
int v;
// if its MAX's turn (computer)
if (player==0) {
// assume worst case, MAX value is -infinity,
// and if better value appears replace v with it
v = -inf;
// for each available move
for (int[] move : moves) { // move = {row,column}
makeMove(move[0],move[1],0);
int score = miniMax(depth 1,1)[0];
undoMove(move[0],move[1],0);
if (score > v) {
v = score;
bestRow = move[0];
bestCol = move[1];
}
}
return new int[] {v,bestRow,bestCol};
}
// if its MIN's turn (opponent)
else {
// assume worst case, MIN value is infinity,
// and if better value appears replace v with it
v = inf;
// for each available move
for (int[] move : moves) { // move = {row,column}
makeMove(move[0],move[1],1); // make move
int score = miniMax(depth 1,0)[0];
undoMove(move[0],move[1],1); // undo move
if (v > score) {
v = score;
bestRow = move[0];
bestCol = move[1];
}
}
return new int[] {v,bestRow,bestCol};
}
}
/**
* @return the best move: int[] {row, column}
*/
int[] minMax(){
int[] m = miniMax(0,0);
return new int[] {m[1],m[2]};
}
public static void main(String[] args) {
f o = new f();
// the max depth (4 moves ahead)
o.depth = 4;
System.out.println("initial board:");
o.printBoard();
System.out.println();
// get best move using miniMax {row, column}
int[] bestMove = o.minMax();
o.makeMove(bestMove[0],bestMove[1],0);
System.out.println("board after computer move:");
o.printBoard();
}
}
вывод:
initial board:
=======
|O| | |
=======
| |O| |
=======
| | | |
=======
board after computer move:
=======
|O| | |
=======
| |O| |
=======
| | |O|
=======