vcs.maemo.org Git - mancala/blob - src/MoveGenerator.cpp

   1 /*
   2 Mancala - A Historical Board Game
   3 Copyright (C) 2009-2010 A.H.M.Mahfuzur Rahman 65mahfuz90@gmail.com
   4 Copyright (c) 2010 Reto Zingg g.d0b3rm4n@gmail.com
   5
   6 This program is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU General Public License as
   8 published by the Free Software Foundation; either version 2 of
   9 the License, or (at your option) any later version.
  10
  11 This program is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20
  21 #include "MoveGenerator.h"
  22
  23 // #include <kdebug.h>
  24
  25 #include "GameInfo.h"
  26 #include "GameController.h"
  27
  28
  29 MoveGenerator::MoveGenerator(int gameDifficulty,GameInfo *gameInfo,GameController *gameController){
  30
  31     m_gameDifficulty = gameDifficulty;
  32     m_gameInfo = gameInfo;
  33     m_gameController = gameController;
  34     m_gameDifficulty = 0;
  35
  36     //we need to use m_depthList[m_gameDifficulty];
  37     m_depthList[0] = 2;
  38     m_depthList[1] = 6;
  39     m_depthList[2] = 8;
  40
  41 }
  42
  43 int MoveGenerator::bestMove(QList<int> currentState,bool humanTurn){
  44
  45     // As we are calculating move only for computer player, humanTurn is currently
  46     // unused
  47     int cupIndex = -1,utility;   //The valid move we want to return
  48     int value = -1000;
  49
  50     //rootNode is a maximizer
  51     Node* rootNode = new Node(m_gameInfo);
  52     copyBoard(rootNode,currentState);
  53     rootNode->setTurn(false);
  54     showBoardState(rootNode);
  55     QList<Node*> m_possibleMoves;
  56     Node* node;
  57
  58     simulateMoves(rootNode,m_possibleMoves);
  59     //kDebug() << "Move simulation ended";
  60
  61     while(allEvaluations.count())
  62         allEvaluations.pop_back();
  63     while(allCupIndexes.count())
  64         allCupIndexes.pop_back();
  65
  66
  67     while(m_possibleMoves.count()){
  68
  69         node = m_possibleMoves.front();
  70
  71         //we have a bonus turn, so we maximize again
  72         if(rootNode->turn() == node->turn()){
  73 //            kDebug() << "Calling maxValue";
  74             allCupIndexes.append(node->move());
  75             utility = maxValue(node,-1000,1000);
  76             allEvaluations.append(utility);
  77             if(utility > value){
  78                 value = utility;
  79                 cupIndex = node->move();
  80             }
  81         }
  82         //we are making turn, so it is a minimizer
  83         else {
  84 //            kDebug() << "Calling minValue";
  85             allCupIndexes.append(node->move());
  86             utility = minValue(node,-1000,1000);
  87             allEvaluations.append(utility);
  88             if(utility > value){
  89                 value = utility;
  90                 cupIndex = node->move();
  91             }
  92         }
  93
  94         m_possibleMoves.pop_front();
  95     }
  96
  97     //kDebug() << "Evaluations: " << allEvaluations;
  98     // kDebug() << "Index: " << cupIndex << " value " << value ;
  99     return cupIndex;
 100 }
 101
 102 int MoveGenerator::maxValue(Node *parentNode,int alpha,int beta){
 103
 104     if(isGameOver( parentNode->getBoard() ) || parentNode->depth() == m_depthList[m_gameDifficulty])
 105         return parentNode->evaluationFunction(m_gameController);
 106
 107     int value = -1000,utility;
 108     //kDebug() << alpha << beta << parentNode->turn();
 109
 110     QList<Node*> m_possibleMoves;
 111     Node* node;
 112     simulateMoves(parentNode,m_possibleMoves);
 113
 114     while(m_possibleMoves.count()){
 115
 116         node = m_possibleMoves.front();
 117 //        kDebug() << "cost: " << node->evaluationFunction(m_gameController);
 118
 119         //we have a bonus turn, so we maximize again
 120         if(parentNode->turn() == node->turn()){
 121 //            kDebug() << "Calling maxValue";
 122             allCupIndexes.append(node->move());
 123             utility = maxValue(node,alpha,beta);
 124             allEvaluations.append(utility);
 125             if(utility > value){
 126                 value = utility;
 127             }
 128         }
 129         //we are making turn, so it is a minimizer
 130         else {
 131 //            kDebug() << "Calling minValue";
 132             allCupIndexes.append(node->move());
 133             utility = minValue(node,alpha,beta);
 134             allEvaluations.append(utility);
 135             if(utility > value){
 136                 value = utility;
 137             }
 138         }
 139
 140         if(value >= beta)
 141             return value;
 142         if(value > alpha)
 143             alpha = value;
 144
 145
 146         m_possibleMoves.pop_front();
 147     }
 148
 149     return value;
 150 }
 151
 152 int MoveGenerator::minValue(Node *parentNode,int alpha,int beta){
 153
 154     if(isGameOver(parentNode->getBoard()) || parentNode->depth() == m_depthList[m_gameDifficulty])
 155         return parentNode->evaluationFunction(m_gameController);
 156
 157     int value = 1000,utility;
 158     //kDebug() << alpha << beta << parentNode->turn();
 159
 160     QList<Node*> m_possibleMoves;
 161     Node* node;
 162     simulateMoves(parentNode,m_possibleMoves);
 163
 164
 165     while(m_possibleMoves.count()){
 166
 167         node = m_possibleMoves.front();
 168 //        kDebug() << "cost: " << node->evaluationFunction(m_gameController);
 169
 170         //we have a bonus turn, so we minimize again
 171         if(parentNode->turn() == node->turn()){
 172 //            kDebug() << "Calling minValue";
 173             allCupIndexes.append(node->move());
 174             utility = minValue(node,alpha,beta);
 175             allEvaluations.append(utility);
 176             if(utility < value){
 177                 value = utility;
 178             }
 179         }
 180         //we are making turn, so it is a maximizer
 181         else {
 182 //            kDebug() << "Calling maxValue";
 183             utility = maxValue(node,alpha,beta);
 184             allCupIndexes.append(node->move());
 185             allEvaluations.append(utility);
 186             if(utility < value){
 187                 value = utility;
 188             }
 189         }
 190
 191         if(value < beta)
 192             beta = value;
 193         if(value <= alpha)
 194             return value;
 195
 196
 197         m_possibleMoves.pop_front();
 198     }
 199
 200     return value;
 201
 202 }
 203
 204 void MoveGenerator::simulateMoves(Node* currentNode,QList<Node*> &nodes){
 205
 206     //    Node* tempNode;
 207     int count1,count2;
 208     QList<int> parentBoard = currentNode->getBoard();
 209     //    QPair<bool,QList<int> > infoNode;
 210
 211     //Computer turn
 212     if(currentNode->turn() == false){
 213         count1 = 0;
 214         for(int i = 0 ; i < m_gameInfo->numCupsPerRow() ; i++){
 215             //If there is enough stone to sow
 216             if( parentBoard[i] > m_gameInfo->leftToCup()){
 217
 218                 count1++;
 219                 Node* tempNode = new Node(m_gameInfo);
 220                 QPair<bool,QList<int> > infoNode;
 221
 222                 infoNode = m_gameController->logicalMoveController(parentBoard,i,currentNode->turn());
 223
 224                 //setting node information
 225                 copyBoard(tempNode,infoNode.second);
 226                 tempNode->setTurn(infoNode.first);
 227                 tempNode->setDepth( currentNode->depth() + 1 );
 228                 tempNode->setMove(i);
 229
 230                 //kDebug() << "Node Info:";
 231                 //kDebug() << tempNode->getBoard();
 232                 //kDebug() << "Turn: " << tempNode->turn() << " Move: " << tempNode->move();
 233
 234                 nodes.append(tempNode);
 235             }
 236         }
 237
 238     }
 239
 240     //Human Turn
 241     else{
 242         count2 = 0;
 243         for(int i = m_gameInfo->numCupsPerRow() ; i < 2*m_gameInfo->numCupsPerRow() ; i++){
 244             //If there is enough stone to sow
 245             if( parentBoard[i] > m_gameInfo->leftToCup()){
 246
 247                 count2++;
 248                 Node* tempNode = new Node(m_gameInfo);
 249                 QPair<bool,QList<int> > infoNode;
 250
 251                 infoNode = m_gameController->logicalMoveController(parentBoard,i,currentNode->turn());
 252
 253                 //setting node information
 254                 copyBoard(tempNode,infoNode.second);
 255                 tempNode->setTurn(infoNode.first);
 256                 tempNode->setDepth( currentNode->depth() + 1 );
 257                 tempNode->setMove(i);
 258
 259                 //kDebug() << "Node Info:";
 260                 //kDebug() << tempNode->getBoard();
 261                 //kDebug() << "Turn: " << tempNode->turn() << " Move: " << tempNode->move();
 262
 263                 nodes.append(tempNode);
 264             }
 265         }
 266
 267     }
 268
 269     //if(count1 > 0) kDebug() << "Count1: " << count1;
 270     //if(count2 > 0) kDebug() << "Count2: " << count2;
 271 }
 272
 273 bool MoveGenerator::isGameOver(QList<int> board){
 274
 275     for(int i = 0 ; i < 2*m_gameInfo->numCupsPerRow() ; i++)
 276         if( board[i] > m_gameInfo->leftToCup() )
 277             return false;
 278     //kDebug() << "Game Is Over ...";
 279     return true;
 280 }
 281
 282 void MoveGenerator::copyBoard(Node* to,Node* from){
 283     QList<int> fromBoard,toBoard;
 284     fromBoard = from->getBoard();
 285
 286     for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++ )
 287         toBoard.append(fromBoard[i]);
 288     to->setBoard(toBoard);
 289 }
 290
 291 void MoveGenerator::copyBoard(Node* to,QList<int>board){
 292     QList<int> tempBoard;
 293     for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++ ){
 294         //kDebug() << "Index: " << i << " content: " << board[i];
 295         tempBoard.append(board[i]);
 296     }
 297     to->setBoard(tempBoard);
 298 }
 299
 300 void MoveGenerator::showBoardState(Node *node){
 301     QList<int> board = node->getBoard();
 302     // kDebug() << board;
 303 }
 304
 305 //--------------------------------- Node Functions Below ------------------------------
 306
 307 Node::Node(GameInfo* info){
 308
 309     m_gameInfo = info;
 310     m_depth = 0;
 311     m_humanTurn = false;
 312     m_move = -1;
 313
 314     for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++)
 315         m_boardState.append(0);
 316 }
 317
 318 int Node::evaluationFunction(GameController* controller){
 319
 320     int cost = 0;
 321 //    kDebug() << "In kalah of Computer: "
 322 //    << m_boardState[1-controller->humanKalahIndex() + 2 * m_gameInfo->numCupsPerRow()]
 323 //    << "depth: "<< m_depth;
 324     cost = m_boardState[1-controller->humanKalahIndex() + 2 * m_gameInfo->numCupsPerRow()]
 325            - m_boardState[controller->humanKalahIndex() + 2 * m_gameInfo->numCupsPerRow()];
 326
 327     //kDebug() << "returning: " << cost;
 328     return cost;
 329 }
 330
 331 void Node::setBoard(QList<int> board){
 332
 333     for(int i = 0 ; i < 2 * m_gameInfo->numCupsPerRow() + 2 ; i++)
 334         m_boardState[i] = board[i];
 335 }