--- /dev/null
+/*
+Mancala - A Historical Board Game
+Copyright (C) 2009-2010 A.H.M.Mahfuzur Rahman 65mahfuz90@gmail.com
+Copyright (c) 2010 Reto Zingg g.d0b3rm4n@gmail.com
+
+This program is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 2 of
+the License, or (at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+
+#include "MoveGenerator.h"
+
+// #include <kdebug.h>
+
+#include "GameInfo.h"
+#include "GameController.h"
+
+
+MoveGenerator::MoveGenerator(int gameDifficulty,GameInfo *gameInfo,GameController *gameController){
+
+ m_gameDifficulty = gameDifficulty;
+ m_gameInfo = gameInfo;
+ m_gameController = gameController;
+ m_gameDifficulty = 0;
+
+ //we need to use m_depthList[m_gameDifficulty];
+ m_depthList[0] = 2;
+ m_depthList[1] = 6;
+ m_depthList[2] = 8;
+
+}
+
+int MoveGenerator::bestMove(QList<int> currentState,bool humanTurn){
+
+ // As we are calculating move only for computer player, humanTurn is currently
+ // unused
+ int cupIndex = -1,utility; //The valid move we want to return
+ int value = -1000;
+
+ //rootNode is a maximizer
+ Node* rootNode = new Node(m_gameInfo);
+ copyBoard(rootNode,currentState);
+ rootNode->setTurn(false);
+ showBoardState(rootNode);
+ QList<Node*> m_possibleMoves;
+ Node* node;
+
+ simulateMoves(rootNode,m_possibleMoves);
+ //kDebug() << "Move simulation ended";
+
+ while(allEvaluations.count())
+ allEvaluations.pop_back();
+ while(allCupIndexes.count())
+ allCupIndexes.pop_back();
+
+
+ while(m_possibleMoves.count()){
+
+ node = m_possibleMoves.front();
+
+ //we have a bonus turn, so we maximize again
+ if(rootNode->turn() == node->turn()){
+// kDebug() << "Calling maxValue";
+ allCupIndexes.append(node->move());
+ utility = maxValue(node,-1000,1000);
+ allEvaluations.append(utility);
+ if(utility > value){
+ value = utility;
+ cupIndex = node->move();
+ }
+ }
+ //we are making turn, so it is a minimizer
+ else {
+// kDebug() << "Calling minValue";
+ allCupIndexes.append(node->move());
+ utility = minValue(node,-1000,1000);
+ allEvaluations.append(utility);
+ if(utility > value){
+ value = utility;
+ cupIndex = node->move();
+ }
+ }
+
+ m_possibleMoves.pop_front();
+ }
+
+ //kDebug() << "Evaluations: " << allEvaluations;
+ // kDebug() << "Index: " << cupIndex << " value " << value ;
+ return cupIndex;
+}
+
+int MoveGenerator::maxValue(Node *parentNode,int alpha,int beta){
+
+ if(isGameOver( parentNode->getBoard() ) || parentNode->depth() == m_depthList[m_gameDifficulty])
+ return parentNode->evaluationFunction(m_gameController);
+
+ int value = -1000,utility;
+ //kDebug() << alpha << beta << parentNode->turn();
+
+ QList<Node*> m_possibleMoves;
+ Node* node;
+ simulateMoves(parentNode,m_possibleMoves);
+
+ while(m_possibleMoves.count()){
+
+ node = m_possibleMoves.front();
+// kDebug() << "cost: " << node->evaluationFunction(m_gameController);
+
+ //we have a bonus turn, so we maximize again
+ if(parentNode->turn() == node->turn()){
+// kDebug() << "Calling maxValue";
+ allCupIndexes.append(node->move());
+ utility = maxValue(node,alpha,beta);
+ allEvaluations.append(utility);
+ if(utility > value){
+ value = utility;
+ }
+ }
+ //we are making turn, so it is a minimizer
+ else {
+// kDebug() << "Calling minValue";
+ allCupIndexes.append(node->move());
+ utility = minValue(node,alpha,beta);
+ allEvaluations.append(utility);
+ if(utility > value){
+ value = utility;
+ }
+ }
+
+ if(value >= beta)
+ return value;
+ if(value > alpha)
+ alpha = value;
+
+
+ m_possibleMoves.pop_front();
+ }
+
+ return value;
+}
+
+int MoveGenerator::minValue(Node *parentNode,int alpha,int beta){
+
+ if(isGameOver(parentNode->getBoard()) || parentNode->depth() == m_depthList[m_gameDifficulty])
+ return parentNode->evaluationFunction(m_gameController);
+
+ int value = 1000,utility;
+ //kDebug() << alpha << beta << parentNode->turn();
+
+ QList<Node*> m_possibleMoves;
+ Node* node;
+ simulateMoves(parentNode,m_possibleMoves);
+
+
+ while(m_possibleMoves.count()){
+
+ node = m_possibleMoves.front();
+// kDebug() << "cost: " << node->evaluationFunction(m_gameController);
+
+ //we have a bonus turn, so we minimize again
+ if(parentNode->turn() == node->turn()){
+// kDebug() << "Calling minValue";
+ allCupIndexes.append(node->move());
+ utility = minValue(node,alpha,beta);
+ allEvaluations.append(utility);
+ if(utility < value){
+ value = utility;
+ }
+ }
+ //we are making turn, so it is a maximizer
+ else {
+// kDebug() << "Calling maxValue";
+ utility = maxValue(node,alpha,beta);
+ allCupIndexes.append(node->move());
+ allEvaluations.append(utility);
+ if(utility < value){
+ value = utility;
+ }
+ }
+
+ if(value < beta)
+ beta = value;
+ if(value <= alpha)
+ return value;
+
+
+ m_possibleMoves.pop_front();
+ }
+
+ return value;
+
+}
+
+void MoveGenerator::simulateMoves(Node* currentNode,QList<Node*> &nodes){
+
+ // Node* tempNode;
+ int count1,count2;
+ QList<int> parentBoard = currentNode->getBoard();
+ // QPair<bool,QList<int> > infoNode;
+
+ //Computer turn
+ if(currentNode->turn() == false){
+ count1 = 0;
+ for(int i = 0 ; i < m_gameInfo->numCupsPerRow() ; i++){
+ //If there is enough stone to sow
+ if( parentBoard[i] > m_gameInfo->leftToCup()){
+
+ count1++;
+ Node* tempNode = new Node(m_gameInfo);
+ QPair<bool,QList<int> > infoNode;
+
+ infoNode = m_gameController->logicalMoveController(parentBoard,i,currentNode->turn());
+
+ //setting node information
+ copyBoard(tempNode,infoNode.second);
+ tempNode->setTurn(infoNode.first);
+ tempNode->setDepth( currentNode->depth() + 1 );
+ tempNode->setMove(i);
+
+ //kDebug() << "Node Info:";
+ //kDebug() << tempNode->getBoard();
+ //kDebug() << "Turn: " << tempNode->turn() << " Move: " << tempNode->move();
+
+ nodes.append(tempNode);
+ }
+ }
+
+ }
+
+ //Human Turn
+ else{
+ count2 = 0;
+ for(int i = m_gameInfo->numCupsPerRow() ; i < 2*m_gameInfo->numCupsPerRow() ; i++){
+ //If there is enough stone to sow
+ if( parentBoard[i] > m_gameInfo->leftToCup()){
+
+ count2++;
+ Node* tempNode = new Node(m_gameInfo);
+ QPair<bool,QList<int> > infoNode;
+
+ infoNode = m_gameController->logicalMoveController(parentBoard,i,currentNode->turn());
+
+ //setting node information
+ copyBoard(tempNode,infoNode.second);
+ tempNode->setTurn(infoNode.first);
+ tempNode->setDepth( currentNode->depth() + 1 );
+ tempNode->setMove(i);
+
+ //kDebug() << "Node Info:";
+ //kDebug() << tempNode->getBoard();
+ //kDebug() << "Turn: " << tempNode->turn() << " Move: " << tempNode->move();
+
+ nodes.append(tempNode);
+ }
+ }
+
+ }
+
+ //if(count1 > 0) kDebug() << "Count1: " << count1;
+ //if(count2 > 0) kDebug() << "Count2: " << count2;
+}
+
+bool MoveGenerator::isGameOver(QList<int> board){
+
+ for(int i = 0 ; i < 2*m_gameInfo->numCupsPerRow() ; i++)
+ if( board[i] > m_gameInfo->leftToCup() )
+ return false;
+ //kDebug() << "Game Is Over ...";
+ return true;
+}
+
+void MoveGenerator::copyBoard(Node* to,Node* from){
+ QList<int> fromBoard,toBoard;
+ fromBoard = from->getBoard();
+
+ for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++ )
+ toBoard.append(fromBoard[i]);
+ to->setBoard(toBoard);
+}
+
+void MoveGenerator::copyBoard(Node* to,QList<int>board){
+ QList<int> tempBoard;
+ for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++ ){
+ //kDebug() << "Index: " << i << " content: " << board[i];
+ tempBoard.append(board[i]);
+ }
+ to->setBoard(tempBoard);
+}
+
+void MoveGenerator::showBoardState(Node *node){
+ QList<int> board = node->getBoard();
+ // kDebug() << board;
+}
+
+//--------------------------------- Node Functions Below ------------------------------
+
+Node::Node(GameInfo* info){
+
+ m_gameInfo = info;
+ m_depth = 0;
+ m_humanTurn = false;
+ m_move = -1;
+
+ for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++)
+ m_boardState.append(0);
+}
+
+int Node::evaluationFunction(GameController* controller){
+
+ int cost = 0;
+// kDebug() << "In kalah of Computer: "
+// << m_boardState[1-controller->humanKalahIndex() + 2 * m_gameInfo->numCupsPerRow()]
+// << "depth: "<< m_depth;
+ cost = m_boardState[1-controller->humanKalahIndex() + 2 * m_gameInfo->numCupsPerRow()]
+ - m_boardState[controller->humanKalahIndex() + 2 * m_gameInfo->numCupsPerRow()];
+
+ //kDebug() << "returning: " << cost;
+ return cost;
+}
+
+void Node::setBoard(QList<int> board){
+
+ for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++)
+ m_boardState[i] = board[i];
+}
projects / mancala / blobdiff