Tic-tac-toe rate алгоритм платы

Question

Я внедрил tic-tac-toc с ai, но теперь им приходится сталкиваться с одной проблемой, как оценивать доску игры tic-tac-toe?

Может быть, в начале я неописуемый, как он должен работать:

1. Мы имеем п доску крестики-нолики игры (с различными вариантами)
2. Наших ай должны ставкой, которая плата является лучшим для перейти/худшую для противника
3. Ai высчитывает шаг минимаксного алгоритма (сделано)

проблемы в 2. есть ли способ, чтобы «курс» доска?

Я хочу сказать, что я не хочу, чтобы кто-нибудь написать мне код, просто, чтобы помочь мне найти алгоритм или что-то :)

Спасибо за помощь, ребята!

Редактировать # 1

Хорошо, у меня есть минимаксный играть доску, но как оценить много советов и выбрать лучший. Может быть, я не ясно говорю, что хочу, поэтому покажу это.

е = пусто

* x | e | e  e | o | e 
* ---+---+--- ---+---+--- 
* x | e | e  e | o | e 
* ---+---+--- ---+---+--- 
* o | e | e  x | x | e 

А теперь, моя реализация минимаксном Алгоритм Построения просто говорит мне, где я должен поставить свой знак (позволяет говорить о), но я должен сказать, на борту которого, так как использовать это, чтобы оценить всю доску, на которую можно играть?

Минимакс код:

minimax : function(tempBoard,depth){ 
    if (CheckForWinner(tempBoard) !== 0) 
     return score(tempBoard, depth); 
    depth+=1; 
    var scores = new Array(); 
    var moves = new Array(); 
    var availableMoves = Game.emptyCells(tempBoard); 
    var move, possibleGame, maxScore, maxScoreIndex, minScore,minScoreIndex; 

    for(var i=0; i < availableMoves.length; i++) { 
     move = availableMoves[i]; 
     possibleGame = Game.getNewBoard(move,tempBoard); 
     scores.push(Ai.minimax(possibleGame, depth)); 
     moves.push(move); 
     tempBoard = Game.undoMove(tempBoard, move); 
    } 
    if (Game.turn === "ai") { 
     maxScore = Math.max.apply(Math, scores); 
     maxScoreIndex = scores.indexOf(maxScore); 
     choice = moves[maxScoreIndex]; 
     return scores[maxScoreIndex]; 

    } else { 
     minScore = Math.min.apply(Math, scores); 
     minScoreIndex = scores.indexOf(minScore); 
     choice = moves[minScoreIndex]; 
     return scores[minScoreIndex]; 
    } 
} 

Answer 1

Вот одна формула, с которой вы можете оценить плату:

value = (10 * x3 + 3 * x2 + x1) - (10 * o3 + 3 * o2 + o1) 

где:

• Xn => количество строк/столбцов/диагоналей с Nx's на нем и не o's
• oN => количество рядов/столбцов/диагоналей с No's на нем и нет x's

Предполагается, что max-player является X. Вы можете изменить знаки, если это в противном случае.

Answer 2

Оценка ходов крестики-нолики можно сделать с помощью алгоритма Minimax. Этот алгоритм нацелен на выполнение движения, чтобы оценить, переключиться на перспективу противника (который, в свою очередь, также пытается сделать соответствующий лучший ход) и рекурсивно оценивать ходы, пока один из игроков не выиграет (это означает, что лист игровое дерево было достигнуто).

Хотя реализация базовой версии этого алгоритма не является невероятно сложной, понимание подхода имеет решающее значение; обратите внимание, что «искусственный интеллект» в основном состоит из гипотетического воспроизведения всей игры со всеми возможными движениями - это не эвристический, а точный алгоритм. Его можно уточнить, используя Alpha-Beta-Pruning, чтобы сэкономить поддеревья игрового дерева, которые не нужны для оценки.