井字C ++算法调试帮助 [英] Tic Tac Toe C++ algorithm debugging help
问题描述
请帮助我了解为什么这是行不通的。我不知道是否有在我的code错误，还是我的算法是从根本逻辑上有缺陷。
我的算法是基于极小，但我而放弃一个启发式评估函数的更简单的技术。由于普通的3x3的井字游戏简单，我只是想计算所有可能的比赛结果对于每一个潜在的举动，并选择具有最高得分。创建的有效移动一个顶层矢量以及一个匹配尺寸矢量为它们的相应的分数 - 即对于该举措随后的每一个可能的结果：++一胜 - 出现亏损
不过我这招分数的载体越来越奇怪非对称值。虽然即使code的工作，在逻辑上是有可能，其计算导致最胜少负一动，就盲目的简单的战术，如叉？我的直觉说是的，但我还没有制定出详细的数学。
字符板[9] = {''，''，''，''，''，''，''，''。 ，。 };
INT com_turn（INT转）
{
焦炭球员= COM; //跟踪当前玩家的
COUT＆LT;＆LT;计算机转\ N的;
矢量＆lt; int的＆GT;移动= get_valid_moves（板）; //顶级的举动名单
矢量＆lt; int的＆GT; m_scores（moves.size（），0）; //顶级招分数
对于（INT M = 0; M＆LT; moves.size（）; M +）// EVAL每个顶级移动
{
板[动作[M] =播放器; //做招
评估（板，转，和放大器; m_scores [M]，播放器）;
COUT＆LT;＆LT; m_scores [M] LT;＆LT; '; //调试
板[动作[M] =''; //撤消移动
}
INT bestmove;
的for（int i = 0; I＆LT; moves.size（）;我++）//找到最好成绩
{
bestmove = MAX（bestmove，m_scores [I]）;
}
的for（int i = 0; I＆LT; moves.size（）;我++）//匹配最好的移动
{
如果（bestmove == m_scores [I]）
{
bestmove =移动[I]
打破;
}
}
板[bestmove] = COM; //终于使COM招
print_board（）;
}
矢量＆lt; int的＆GT; get_valid_moves（字符*板）
{
矢量＆lt; int的＆GT; vmoves;
的for（int i = 0; I＆LT; 9;我++）
{
如果（板[I] =='。'）vmoves.push_back（ⅰ）;
}
返回vmoves;
}
无效评估（字符*板，INT反过来，为int * mscore，焦炭播放器）
{
如果（check_win（板））
{
（播放器==人）？ * mscore - = 1：* mscore + = 1;
返回;
}
如果（转＆GT; 9）回报;
矢量＆lt; int的＆GT; child_moves = get_valid_moves（板）;
如果（child_moves.size（）。1）返回;
（播放器== COM）？球员=人：玩家= COM; //开关机
对于（INT M = 0; M＆LT; child_moves.size（）; M +）
{
板[child_moves [M] =播放器; //做招
评估（板，++转，mscore，播放器）;
板[child_moves [M] =''; //撤消移动
}
}
我想你会看到那里的问题是，如果你使评估返回的得分，而不是使用回通过引用。
评估应minimaxing，但现在我认为这是在做一些奇怪的总和，因为加法和减法的副作用叶节点。
为什么要总结成绩不正确
假设我有董事会：
。 。 Ø
。 。 。
。 X X
然后与O只有一个动，（块），因为X的下一步行动将赢得如果可没有做到这一点。不过，也有很多的游戏路径，即在澳开始做其他动作，带O获奖，如：
O2 O1Ø
。 。 X1
。 X X
其中的数字表示该举动是第一位。
所以你看，刚刚在之是不会给你正确的答案。
我建议传递价值上树的原因是，迫使你写出来，究竟在节点比分是随着孩子的函数。在您的code，现在该功能的总和，在极小它要么最小或最大，根据玩家的回合。
Please help me understand why this isn't working. I don't know if there is a bug in my code, or whether my algorithm is fundamentally logically flawed.
My algorithm is based on minimax, but I've forgone a heuristic evaluation function for a more simple technique. Because of the simplicity of plain 3x3 tic tac toe, I just want to calculate all possible game outcomes for each potential move, and select the one with the highest 'score'. I create a 'top level' vector of valid moves as well as a matching sized vector for their corresponding 'scores' -i.e. for every possible outcome subsequent to that move: ++ for a win and -- for a loss.
However my vector of move scores is getting strange non-symmetrical values. Although even if the code worked, logically is it possible that a move which is calculated to lead to the most wins and least losses, would be blind to a simple tactic such as a fork? My instincts say yes, but I haven't worked out the math in detail.
char board [9] = { '.','.','.','.','.','.','.','.','.' };
int com_turn(int turn)
{
char player=COM; // keeps track of current player
cout<<"Computer turn. \n";
vector<int> moves = get_valid_moves(board); // top level move list
vector<int> m_scores (moves.size(), 0); // top level move scores
for (int m=0; m < moves.size(); m++) // eval each top level move
{
board[moves[m]] = player; // do move
evaluate(board, turn, &m_scores[m], player);
cout<< m_scores[m] <<' '; // for debugging
board[moves[m]]='.'; // undo move
}
int bestmove;
for (int i=0; i < moves.size(); i++) // find best score
{
bestmove = max(bestmove, m_scores[i]);
}
for (int i=0; i < moves.size(); i++) // match to best move
{
if (bestmove == m_scores[i])
{
bestmove = moves[i];
break;
}
}
board[bestmove]=COM; // finally make com move
print_board();
}
vector<int> get_valid_moves(char *board)
{
vector<int> vmoves;
for (int i=0; i < 9; i++)
{
if (board[i]=='.') vmoves.push_back(i);
}
return vmoves;
}
void evaluate(char *board, int turn, int *mscore, char player)
{
if (check_win(board))
{
(player==HUMAN)? *mscore -= 1: *mscore += 1;
return;
}
if (turn > 9) return;
vector<int> child_moves = get_valid_moves(board);
if (child_moves.size() < 1) return;
(player==COM)? player=HUMAN: player=COM; // switch player
for (int m=0; m < child_moves.size(); m++)
{
board[child_moves[m]] = player; // do move
evaluate(board, ++turn, mscore, player);
board[child_moves[m]]='.'; // undo move
}
}
I think you'll see where the problem is if you make evaluate return the score rather than using return-by-reference.
Evaluate should be minimaxing, but right now I think it's doing some weird sum of the leaf nodes because of the side-effect of additions and subtractions.
Why summing up the scores is not correct
Suppose I have the board:
. . O
. . .
. X X
Then O only has one move, (block), because X's next move will win if O doesn't make it. However, there are lots of game paths that start at O making other moves, with O winning, like:
O2 O1 O
. . X1
. X X
Where the number indicates which move came first.
So you see, just getting the sum isn't going to give you the right answer.
The reason I recommend passing the values up the tree is that that forces you to write out what the score at a node is as a function of the children. In your code right now the function is the sum, in minimax it's either min or max, depending on the player's turn.
这篇关于井字C ++算法调试帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
