src/AI/KBlocksAIPlayer.cpp

0001 /***************************************************************************
0002 *   KBlocks, a falling blocks game by KDE                                 *
0003 *   SPDX-FileCopyrightText: 2010 University Freiburg <squall.leonhart.cai@gmail.com> *
0004 *                                                                          *
0005 *   SPDX-License-Identifier: GPL-2.0-or-later
0006 ***************************************************************************/
0007 #include "KBlocksAIPlayer.h"
0008
0009 #include "KBlocksAIEvaluation.h"
0010 #include "KBlocksAIFeature.h"
0011 #include "KBlocksAIPlannerExtend.h"
0012 #include "KBlocksAILog.h"
0013
0014 #include "kblocks_ai_debug.h"
0015
0016 #include <utility>
0017 #include <vector>
0018
0019 typedef std::pair<KBlocksPiece, double> Result;
0020 typedef std::vector<Result> Result_Sequence;
0021
0022 #define MAX_UTILITY     // choose the goal with the highest utility
0023 //#  PLANNER  ######################################
0024 #define TWO_PIECE_PLANNER
0025 //#  SITUATION TREE  ################################
0026 #define SITUATION_MULTI_NARROW
0027 #define SITUATION_CRITIC_HEIGHT
0028 #define SITUATION_TERIS
0029 //#define SITUATION_SECTION_ANALYSIS
0030 //#define SITUATION_DEEP_NARROW
0031 //#define SITUATION_TALL_BLOCKS
0032
0033 //#  EVALUATION FEATURE  ############################
0034 //#define DIFFERENCE_EVALUATION
0035 //#define SECOND_EVALUATION
0036
0037 //#  EXTRA EVALUATION   #############################
0038 //#define SPECIAL_EVALUATION
0039 #ifdef SPECIAL_EVALUATION
0040 #define NBS_EVALUATION
0041 #endif
0042
0043 KBlocksAIPlayer::KBlocksAIPlayer(const string &name)
0044 {
0045     mAIName = name;
0046
0047     mAIStarted = false;
0048     mAIPaused = false;
0049
0050     mpAIField = nullptr;
0051     mpCurPiece = nullptr;
0052     mpNextPiece = nullptr;
0053
0054     mpPlanner = nullptr;
0055     mNextCount = 0;
0056
0057     mpEvaluatorFinal = nullptr;
0058     mpEvaluatorFirst = nullptr;
0059     mpEvaluatorPre = nullptr;
0060
0061     mBestPosition = 0;
0062     mBestRotation = 0;
0063 }
0064
0065 KBlocksAIPlayer::~KBlocksAIPlayer()
0066 {
0067     if (mAIStarted) {
0068         delete mpPlanner;
0069         delete mpNextPiece;
0070         delete mpCurPiece;
0071         delete mpAIField;
0072     }
0073 }
0074
0075 void KBlocksAIPlayer::startGame(SingleGameInterface *p)
0076 {
0077     if (mAIStarted) {
0078         return;
0079     }
0080
0081     mAIStarted = true;
0082     mpGame = p;
0083
0084     mpAIField = new KBlocksField(mpGame->getField());
0085     mpCurPiece = new KBlocksPiece(mpGame->getPiece(0));
0086     mpNextPiece = new KBlocksPiece(mpGame->getPiece(1));
0087
0088     mpPlanner = new KBlocksAIPlannerExtend(mpAIField);
0089 }
0090
0091 void KBlocksAIPlayer::stopGame()
0092 {
0093     if (!mAIStarted) {
0094         return;
0095     }
0096
0097     delete mpPlanner;
0098     mpPlanner = nullptr;
0099
0100     delete mpNextPiece;
0101     mpNextPiece = nullptr;
0102     delete mpCurPiece;
0103     mpCurPiece = nullptr;
0104     delete mpAIField;
0105     mpAIField = nullptr;
0106
0107     mpGame = nullptr;
0108     mAIStarted = false;
0109 }
0110
0111 void KBlocksAIPlayer::pauseGame(bool flag)
0112 {
0113     mAIPaused = flag;
0114 }
0115
0116 void KBlocksAIPlayer::think(GamePlayer_ActionList *actionList)
0117 {
0118     if ((!mAIStarted) || (mAIPaused)) {
0119         return;
0120     }
0121
0122     // Phase I   - State Update
0123     update();
0124     // Phase II  - Planning
0125     planning();
0126     // Phase III - Situation Analysis
0127     situationAdaption();
0128     // Phase IV  - States Evaluation
0129     generateGoalAction();
0130
0131     // set up action list
0132     if (mBestRotation > 0) {
0133         for (int i = 0; i < mBestRotation; i++) {
0134             actionList->push_back(PlayerAction_Rotate_CW);
0135         }
0136     } else {
0137         mBestRotation = -mBestRotation;
0138         for (int i = 0; i < mBestRotation; i++) {
0139             actionList->push_back(PlayerAction_Rotate_CCW);
0140         }
0141     }
0142
0143     if (mBestPosition > 0) {
0144         for (int i = 0; i < mBestPosition; i++) {
0145             actionList->push_back(PlayerAction_Move_Right);
0146         }
0147     } else {
0148         mBestPosition = -mBestPosition;
0149         for (int i = 0; i < mBestPosition; i++) {
0150             actionList->push_back(PlayerAction_Move_Left);
0151         }
0152     }
0153
0154     actionList->push_back(PlayerAction_Push_Down);
0155 }
0156
0157 string KBlocksAIPlayer::getName()
0158 {
0159     return mAIName;
0160 }
0161
0162 /******************************************************************
0163 * THINK -  DECIDE - CATCH
0164 *****************************************************************/
0165 /* Phase I   - State Update     ----------------------------------*/
0166 void KBlocksAIPlayer::update()
0167 {
0168     mpAIField->copy(mpGame->getField());
0169     mpCurPiece->copy(mpGame->getPiece(0));
0170     mpNextPiece->copy(mpGame->getPiece(1));
0171 }
0172
0173 /* Phase II  - Planning         ----------------------------------*/
0174 void KBlocksAIPlayer::planning()
0175 {
0176     if (!mpPlanner) {
0177         qCWarning(KBlocksAI) << "No planner set for AI evaluation!";
0178         return;
0179     }
0180 #ifdef TWO_PIECE_PLANNER
0181     AIPlanner_PieceValue_Sequence mPieceSequence = AIPlanner_PieceValue_Sequence(0);
0182     mPieceSequence.push_back(KBlocks_PieceType_Detail(mpCurPiece->toValue()));
0183     mPieceSequence.push_back(KBlocks_PieceType_Detail(mpNextPiece->toValue()));
0184     KBlocksAIPlannerExtend *extendedPlanner = dynamic_cast<KBlocksAIPlannerExtend *>(mpPlanner);
0185     if (extendedPlanner != nullptr) {
0186         mNextCount = extendedPlanner->process(mPieceSequence);
0187     }
0188 #else
0189     KBlocks_PieceType_Detail type = KBlocks_PieceType_Detail(mpCurPiece->toValue());
0190     mNextCount = mpPlanner->process(type);
0191 #endif
0192 }
0193
0194 /* Phase III - Situation Analysis               -------------------*/
0195 void KBlocksAIPlayer::situationAdaption()
0196 {
0197 #ifndef SPECIAL_EVALUATION
0198     if (false) {
0199     }
0200 #ifdef SITUATION_MULTI_NARROW
0201     else if (getDecisionFeature(DF_PEEKS_COUNT, mpAIField)) {
0202         mpEvaluatorFinal = WellsFillerEvaluation::instance();
0203     }
0204 #endif
0205 #ifdef SITUATION_CRITIC_HEIGHT
0206     else if (getDecisionFeature(DF_HEIGHT_MAX, mpAIField)) {
0207         mpEvaluatorFinal = HeightKillerEvaluation::instance();
0208     }
0209 #endif
0210 #ifdef SITUATION_SECTION_ANALYSIS
0211     else if (getDecisionFeature(DF_LAYER_SCAN, mpAIField)) {
0212         mpEvaluatorFinal = HalfBaseEvaluation::instance();
0213     }
0214 #endif
0215 #ifdef SITUATION_DEEP_NARROW
0216     else if (getDecisionFeature(DF_DEEP_NARROW, mpAIField)) {
0217         mpEvaluatorFinal = DeepNarrowRemoverEvaluation::instance();
0218     }
0219 #endif
0220 #ifdef SITUATION_TALL_BLOCKS
0221     else if (getDecisionFeature(DF_BLOCK_SCAN, mpAIField)) {
0222         mpEvaluatorFinal = BlockRemoverEvaluation::instance();
0223     }
0224 #endif
0225 #ifdef SITUATION_TERIS
0226     else if (getDecisionFeature(DF_CREATING_TETRIS, mpAIField)) {
0227         if (getDecisionFeature(DF_REMOVE_TETRIS, mpAIField)) {
0228             mpEvaluatorFinal = TetrisEliminationEvaluation::instance();
0229         } else {
0230             mpEvaluatorFinal = TetrisPreparingEvaluation::instance();
0231         }
0232     }
0233 #endif
0234     else {
0235         mpEvaluatorFinal = BaseEvaluation::instance();
0236     }
0237
0238 #ifdef DIFFERENCE_EVALUATION_
0239     mpEvaluatorPre  = mpEvaluatorFinal;
0240 #endif
0241
0242 #ifdef SECOND_EVALUATION
0243     mpEvaluatorFirst = BaseEvaluation::instance();
0244 #endif
0245
0246 #else
0247 #ifdef NBS_EVALUATION
0248     mpEvaluatorFirst = 0;
0249     mpEvaluatorPre   = 0;
0250     mpEvaluatorFinal = NBSEvaluation::instance();
0251 #endif
0252 #endif
0253     //println(mpEvaluatorFinal->evaluationName());
0254 }
0255
0256 /* Phase IV  - States Evaluation                -------------------*/
0257 void KBlocksAIPlayer::generateGoalAction()
0258 {
0259     double current_value = 0;
0260     if (mpEvaluatorPre != nullptr) {
0261         current_value = mpEvaluatorPre->evaluate(mpAIField);
0262     }
0263
0264     double best_value = 0;
0265     Result_Sequence result = Result_Sequence(0);
0266     std::vector<int> best_goals = std::vector<int>(0);
0267
0268     mBestRotation = 0;
0269     mBestPosition = 0;
0270
0271     // FIRST STEP - ANALYZE FINAL BOARD_STATE
0272     if (mpEvaluatorFinal != nullptr) {
0273         bool firstValue = true;
0274
0275         for (int i = 0; i < mNextCount; i++) {
0276             KBlocksField *field = new KBlocksField(mpAIField->getWidth(), mpAIField->getHeight());
0277             mpPlanner->getNextBoardStatus(i, field);
0278
0279             if (!field) {
0280                 continue;
0281             }
0282
0283             KBlocksPiece *piece = new KBlocksPiece();
0284             mpPlanner->getNextPieceState(i, piece);
0285
0286             double value = 0;
0287 #ifndef SPECIAL_EVALUATION
0288             value = mpEvaluatorFinal->evaluate(field) - current_value;
0289 #else
0290 #ifdef NBS_EVALUATION
0291             SpecialEvaluationInterface *evaluator =
0292                 dynamic_cast<SpecialEvaluationInterface *>(mpEvaluatorFinal);
0293             evaluator->setCurrentPiece(piece);
0294             value = evaluator->evaluate(field);
0295 #endif
0296 #endif
0297             result.push_back(Result(KBlocksPiece(piece), value));
0298 #ifdef MAX_UTILITY
0299             bool better = (best_value < value);
0300 #else
0301             bool better = (best_value > value);
0302 #endif
0303             if (better || firstValue) {
0304                 best_goals.clear();
0305                 best_value = value;
0306                 firstValue = false;
0307             }
0308
0309             // alternative found
0310             if (best_value == value) {
0311                 best_goals.push_back(i);
0312             }
0313
0314             delete piece;
0315             if (field) {
0316                 delete field;
0317             }
0318         }
0319     }
0320
0321     // NO SOLUTION FOUND
0322     if (best_goals.empty()) {
0323         return ;
0324     }
0325
0326     //SECOND STEP
0327 #ifdef TWO_PIECE_PLANNER
0328 #ifdef SECOND_EVALUATION
0329     if (mpEvaluatorFirst != 0) {
0330         std::vector<int> _best_goals = std::vector<int>(0);
0331         double _best_value = 0;
0332         double firstValue = true;
0333
0334         KBlocksAIPlannerExtend *_planner = (dynamic_cast<KBlocksAIPlannerExtend *>(mpPlanner));
0335
0336         //    double _current_value = current_value;
0337         for (int i = 0; i < best_goals.size(); i++) {
0338             int index = best_goals[i];
0339
0340             KBlocksField *field = new KBlocksField();
0341
0342             _planner->getNextBoardStatus(index, field, true);
0343
0344             if (!field) {
0345                 continue;
0346             }
0347
0348             double value = mpEvaluatorFirst->evaluate(field);
0349 #ifdef MAX_UTILITY
0350             bool better = (_best_value < value);
0351 #else
0352             bool better = (_best_value > value);
0353 #endif
0354             if (better || firstValue) {
0355                 _best_goals.clear();
0356                 _best_value = value;
0357                 firstValue = false;
0358                 better = true;
0359             }
0360
0361             // alternative found
0362             if (better || (_best_value == value)) {
0363                 _best_goals.push_back(index);
0364             }
0365
0366             if (field) {
0367                 delete field;
0368             }
0369         }
0370         best_goals = std::vector<int>(_best_goals);
0371     }
0372 #endif
0373 #endif
0374
0375 #ifdef INITLIST
0376     int goal_index = best_goals[0];
0377 #else
0378     int goal_index = best_goals[rand() % best_goals.size()];
0379 #endif
0380
0381     KBlocksPiece *goal_piece = &(result[goal_index].first);
0382
0383     mBestRotation = goal_piece->getRotation() - mpCurPiece->getRotation();
0384     mBestPosition = goal_piece->getPosX() - mpCurPiece->getPosX();
0385 }