MFC Tictactoe alpha-beta pruning bug...
-
can anyone help me find my bug. i wrote a function that would search the tictactoe board for the best possible computer move. i am using alpha beta pruning to optimize my search. the function returns the score from the search and the row and column where the computer should move. ok here is the function... the PossiblePlayerMove function is the same thing but it searches for the best possible player move. int CComputer::CheckForMoves(const CBoard &rConstBoard,int nDepth, int nAlpha, int nBeta, int &nRow, int &nCol) { // Check for invalid data ASSERT(mnDepth >= 0 && mnDepth <= MAXDEPTH); // Check if the row and column return is a valid value ASSERT(nRow < MAXROW && nCol < MAXCOL); int nScore = 0; // The score from the search mnDepth = nDepth; // Set the Depth to the new depth. int Row = nRow; // Copy the Row and Column int Col = nCol; // Create a new Board and Copy the values of other board. CBoard Board = rConstBoard; // Base Case if (Winner(Board) || mnDepth == 0) { nRow = Row; nCol = Col; return Evaluate(Board); } else { // Try all the possible move on a different Board // then return the best move. for (int row = 0; row < MAXROW; row++) for (int col = 0; col < MAXCOL; col++) if (Board.IsEmpty(row,col)) { Board.SetCellValue(row,col,'O'); if (mnDepth == 0) break; nScore = PossiblePlayerMove(Board,mnDepth - 1,nBeta,nAlpha,Row,Col); // Set Row and Column nRow = Row; nCol = Col; if (nAlpha < nScore) nAlpha = nScore; Board.SetCellValue(row,col,NULL); if (nAlpha >= nBeta) break; } } return nAlpha; } i hope this is enough... by the way.. the possible moves function is the same thing ... Thank you very much, John :-D Aloha from Hawaii :-)