File indexing completed on 2022-09-27 13:19:28

0001 /*
0002     SPDX-FileCopyrightText: 2006 Matthew Williams <matt@milliams.com>
0003 
0004     SPDX-License-Identifier: GPL-2.0-or-later
0005 */
0006 
0007 #include "aicontroller.h"
0008 
0009 #include <ctime>
0010 #include <QDebug>
0011 
0012 #include <QSet>
0013 #include <QRandomGenerator>
0014 
0015 #include "settings.h"
0016 
0017 aiController::aiController(int newPlayerId, const QList<bool> &newLines, const QList<int> &newSquareOwners, int newWidth, int newHeight) : squareOwners(newSquareOwners), playerId(newPlayerId), width(newWidth), height(newHeight)
0018 {
0019     linesSize = newLines.count();
0020     lines = new bool[linesSize];
0021     for (int i = 0; i < linesSize; ++i) {
0022         lines[i] = newLines[i];
0023     }
0024     //qDebug() << "AI: Starting AI level" << Settings::difficulty();
0025 }
0026 
0027 aiController::~aiController()
0028 {
0029     delete[] lines;
0030 }
0031 
0032 QList<int> aiController::autoFill(int safeMovesLeft)
0033 {
0034     QList<int> fillLines;
0035 
0036     // add a random safe moves while there are safe moves left
0037     QList<int> next;
0038     ////qDebug() << safeMoves().isEmpty();
0039     while (!((next = safeMoves()).isEmpty())) {
0040         int nextLine = next[rand() % next.size()];
0041         lines[nextLine] = true;
0042         ////qDebug() << nextLine;
0043         fillLines << nextLine;
0044     }
0045 
0046     // safeMovesLeft times delete a line from fillLines
0047     for (int i = 0; i < safeMovesLeft; ++i) {
0048         if (fillLines.isEmpty()) {
0049             break;
0050         }
0051         int index = QRandomGenerator::global()->bounded(fillLines.size());
0052         fillLines.removeAt(index);
0053     }
0054 
0055     return fillLines;
0056 }
0057 
0058 int aiController::chooseLine() const
0059 {
0060     QList<int> choiceList;
0061     for (int i = 0; i < linesSize; i++) { //trying to get points. looking for squares with 3 lines
0062         if (!lines[i]) {
0063             QList<int> adjacentSquares = squaresFromLine(i);
0064             for (int j = 0; j < adjacentSquares.size(); j++) {
0065 
0066                 if (countBorderLines(adjacentSquares.at(j), lines) == 3) { //if 3 lines, draw there to get points!
0067                     choiceList.append(i);
0068                     ////qDebug() << "AI: 1. Adding" << i << "to choices";
0069                 }
0070             }
0071         }
0072     }
0073     if (!choiceList.isEmpty()) {
0074         if (Settings::difficulty() == 2) { // to play good ai has to look into the future game
0075             QList<int> openLines; // list of not yet drawn lines
0076             for (int i = 0; i < linesSize; i++) {
0077                 if (!lines[i]) {
0078                     openLines.append(i);
0079                 }
0080             }
0081             QList<int> choices = chooseLeastDamaging(openLines); // run extended damage control
0082             if (!choices.isEmpty()) {
0083                 //qDebug() << "AI: 4. Drawing line at index:" << choices.at(0);
0084                 return choices.at(0);
0085             }
0086         }
0087         float randomFloat = ((float) rand() / (RAND_MAX + 1.0)) * (choiceList.size() - 1);
0088         int randChoice = (short)(randomFloat) / 1;
0089         //qDebug() << "AI: 1. Drawing line at index:" << choiceList.at(randChoice);
0090         return choiceList.at(randChoice);
0091     }
0092 
0093     choiceList = safeMoves();
0094 
0095     if (choiceList.size() != 0) {
0096         float randomFloat = ((float) rand() / (RAND_MAX + 1.0)) * (choiceList.size() - 1);
0097         int randChoice = (short)(randomFloat) / 1;
0098         //qDebug() << "AI: 2. Drawing line at index:" << choiceList.at(randChoice);
0099         return choiceList.at(randChoice);
0100     }
0101 
0102     choiceList.clear();
0103     for (int i = 0; i < linesSize; i++) { //have to take what's left
0104         if (!lines[i]) {
0105             QList<int> adjacentSquares = squaresFromLine(i);
0106             for (int j = 0; j < adjacentSquares.size(); j++) {
0107 
0108                 if (countBorderLines(adjacentSquares.at(j), lines) == 2) { //if 2 lines (they're all that's left!)
0109                     choiceList.append(i);
0110                     ////qDebug() << "AI: 3. Adding" << i << "to choices";
0111                 }
0112             }
0113         }
0114     }
0115     if (Settings::difficulty() >= 1) { //Hard(2/3) //do some damage control :)
0116         QList<int> goodChoiceList = chooseLeastDamaging(choiceList);
0117         if (goodChoiceList.size() != 0) {
0118             float randomFloat = ((float) rand() / (RAND_MAX + 1.0)) * (goodChoiceList.size() - 1);
0119             int randChoice = (short)(randomFloat) / 1;
0120             //qDebug() << "AI: 3. Drawing line at index:" << goodChoiceList.at(randChoice);
0121             return goodChoiceList.at(randChoice);
0122         }
0123     }
0124 
0125     if (choiceList.size() != 0) {
0126         float randomFloat = ((float) rand() / (RAND_MAX + 1.0)) * (choiceList.size() - 1);
0127         int randChoice = (short)(randomFloat) / 1;
0128         //qDebug() << "AI: 3. Drawing line at index:" << choiceList.at(randChoice);
0129         return choiceList.at(randChoice);
0130     }
0131     return 0;
0132 }
0133 
0134 QList<int> aiController::safeMoves() const
0135 {
0136     QList<int> safeLines;
0137     for (int i = 0; i < linesSize; i++) { //finding totally safe moves. avoiding squares with 2 lines
0138         if (!lines[i]) {
0139             QList<int> adjacentSquares = squaresFromLine(i);
0140             int badCount = 0;
0141             for (int j = 0; j < adjacentSquares.size(); j++) {
0142                 if (countBorderLines(adjacentSquares.at(j), lines) == 2) { //don't want to make 3 lines around a square
0143                     badCount++;
0144                 }
0145             }
0146             if (badCount == 0) {
0147                 safeLines.append(i);
0148                 ////qDebug() << "AI: 2. Adding" << i << "to choices";
0149             }
0150         }
0151     }
0152     return safeLines;
0153 }
0154 
0155 QList<int> aiController::chooseLeastDamaging(const QList<int> &choiceList) const
0156 {
0157     ////qDebug() << "AI: Checking" << choiceList.size() << "possible moves";
0158     QMultiMap<int, int> linePointDamage; //this will be a list of how damaging a certain move will be. Key = damage of move, Value = index of line
0159     QScopedArrayPointer<bool> linesCopy(new bool[linesSize]); //make temporary local copies of lists
0160     int sidesOfSquare[4];
0161 
0162     QMap<int, QSet<int> > chains; // this is a raw list of chains (which are sets of lines). key = random element of chain
0163     QMap<int, QSet<int> > chainSet; // same thing as chains but with unique chains
0164     QList<QList<int> > ownChains; // chains that ai will get in this run. those chains are taken in myLines.
0165     QList<int> ownMoves; // contains lines of chain that the ai will take first (this will contain the returned move)
0166     QScopedArrayPointer<bool> myLines(new bool[linesSize]); //make temporary local copies of lists
0167     int ownLinesCnt = 0; // count of how many lines ai will take in this run
0168     int ownSquaresCnt = 0; // count of how many squares ai will get in this run
0169 
0170     if (Settings::difficulty() > 1) {
0171         memcpy(myLines.data(), lines, linesSize); // lines --> myLines (complete own chains) --> linesCopy (analyze damage/chains for next runs)
0172         bool chainFound;
0173         // since chooseLeastDamaging will be called early during the game if playing against hard ai, we need to finish open chains in linesCopy before computing the number of residual chains
0174         do { // this loop completes all chains the opponent gave to ai
0175             chainFound = false;
0176             for (int curSquare = 0; curSquare < squareOwners.size(); curSquare++) { // walk through squares and search for start of chain
0177                 QList<int> ownChain; // remember completed chain lines
0178                 int chainSquare = curSquare;
0179                 bool squareFound;
0180                 do { // this loop walks through a chain square by square
0181                     squareFound = false;
0182                     if (countBorderLines(sidesOfSquare, chainSquare, &(*myLines)) == 3) { // found a square for ai
0183                         for (int sideOfSquare = 0; sideOfSquare <= 3; sideOfSquare++) {
0184                             if (!myLines[sidesOfSquare[sideOfSquare]]) { // found missing line of square
0185                                 ownLinesCnt++;
0186 
0187                                 int nextSquareFound = -1;
0188                                 QList<int> adjacentSquares = squaresFromLine(sidesOfSquare[sideOfSquare]);
0189                                 for (int i = 0; i < adjacentSquares.size(); i++) {
0190                                     int chainSquareBorderCnt = countBorderLines(adjacentSquares.at(i), &(*myLines));
0191                                     if (chainSquare != adjacentSquares.at(i) &&
0192                                             chainSquareBorderCnt == 3) { // check if a second square will be completed by this line
0193                                         ownSquaresCnt++; // add extra square
0194                                     }
0195                                     if (chainSquareBorderCnt == 2) { // look for next square in chain
0196                                         nextSquareFound = adjacentSquares.at(i);
0197                                     }
0198 
0199                                 }
0200                                 myLines[sidesOfSquare[sideOfSquare]] = true; // complete line
0201                                 if (nextSquareFound >= 0) {
0202                                     chainSquare = nextSquareFound;
0203                                 }
0204                                 ownChain.append(sidesOfSquare[sideOfSquare]);
0205                             }
0206                         }
0207                         squareFound = true;
0208                         chainFound = true;
0209                         ownSquaresCnt++;
0210                     }
0211                 } while (squareFound);
0212                 if (chainFound) {
0213                     ownChains.append(ownChain);
0214                     break;
0215                 }
0216             }
0217         } while (chainFound);
0218         ////qDebug() << "ownChains:" << ownChains;
0219 
0220         // complete the shortest chain first if there is more than one chain. this is needed to stop alternating between two chains because that works against the hard ai move which takes the next chain by sacrificing 2/4 squares. when alternating between two chains it's possible that there are 3 remaining open lines in both chains combined which triggers the evil move too late because the chains were completed in the wrong order
0221         int minChain = -1;
0222         int tmp = width * height * 10;
0223         for (int i = 0; i < ownChains.size(); i++) {
0224             if (tmp > ownChains.at(i).size()) {
0225                 tmp = ownChains.at(i).size();
0226                 minChain = i;
0227             }
0228         }
0229         if (minChain >= 0) {
0230             ownMoves = ownChains.at(minChain);
0231         }
0232         ////qDebug() << "ownMoves:" << ownMoves;
0233     }
0234 
0235     for (int i = 0; i < choiceList.size(); i++) { //cycle through all the possible moves
0236         QList<int> squaresCopy = squareOwners;  //make temporary local copies of lists
0237         QSet<int> chain; // set of lines that are given to opponent by move choiceList.at(i)
0238 
0239         if (Settings::difficulty() > 1) {
0240             memcpy(linesCopy.data(), myLines.data(), linesSize);    //make temporary local copies of lists
0241             if (linesCopy[choiceList.at(i)]) {
0242                 continue;    // already covered. ai will get this line
0243             }
0244         } else {
0245             memcpy(linesCopy.data(), lines, linesSize); //make temporary local copies of lists
0246         }
0247 
0248         linesCopy[choiceList.at(i)] = true; //we're going to try drawing a line here
0249 
0250         //now it would be the next player's turn so we're going to count how many squares they would be able to get.
0251         int count = 0;  //this is how many points the next player will ge if you draw a line at choiceList.at(i)
0252         bool squareFound = false;
0253         chain.insert(choiceList.at(i));
0254         do {
0255             for (int currentSquare = 0; currentSquare < squaresCopy.size(); currentSquare++) { //cycle through the grid (by squares):
0256                 if (countBorderLines(sidesOfSquare, currentSquare, &(*linesCopy)) == 3) { //if we've found a square with three sides drawn:
0257                     count++;
0258                     squareFound = true; //we found a square so we will look again for the next
0259 
0260                     for (int sideOfSquare = 0; sideOfSquare <= 3; sideOfSquare++) { //make the square complete in linesCopy
0261                         if (Settings::difficulty() > 1 && !linesCopy[sidesOfSquare[sideOfSquare]]) {
0262                             chain.insert(sidesOfSquare[sideOfSquare]);
0263                             QList<int> adjacentSquares = squaresFromLine(sidesOfSquare[sideOfSquare]);
0264                             for (int adjsq = 0; adjsq < adjacentSquares.size(); adjsq++) {
0265                                 if (currentSquare == adjacentSquares.at(adjsq)) {
0266                                     continue;
0267                                 }
0268                                 if (countBorderLines(adjacentSquares.at(adjsq), &(*myLines)) == 3) {
0269                                     // line will complete two squares
0270                                     count++;
0271                                 }
0272                             }
0273                         }
0274                         linesCopy[sidesOfSquare[sideOfSquare]] = true;  //draw at this squares
0275                     }   //now current square is completed by the second player.
0276                     break;  //since we found a square with 3 sides completed (now = 4), we break the 'for(currentSquare)' loop
0277                 } else {
0278                     squareFound = false;    //we couldn't find a square this time round so we'll try the next 'i'
0279                 }
0280             }
0281         } while (squareFound == true);  //while we're still finding squares
0282         linePointDamage.insert(count, choiceList.at(i));   //insert a pair with Key=count, Value=i
0283         chains.insert(choiceList.at(i), chain);
0284     }
0285 
0286     ////qDebug() << "linePointDamage:" << linePointDamage;
0287 
0288     if (Settings::difficulty() < 2) { // middle ai won't analyze the game further
0289         QList<int> bestMoves = linePointDamage.values(linePointDamage.begin().key());   //this is a list of the indices of the lines that are the least damaging. linePointDamage.begin() returns the 1st pair in the QMap, sorted in ascending order by Key (damage of move)
0290         return bestMoves;
0291     }
0292 
0293     ////qDebug() << chains;
0294     // remove double entries from chains to get chainSet
0295     QMapIterator<int, QSet<int> > j(chains);
0296     while (j.hasNext()) { // walk through chains and add chain to chainSet (if not already contained)
0297         j.next();
0298         bool newChain = true;
0299         QSet<int> chainCheck = j.value(); // this is the chain we might add
0300         QMapIterator<int, QSet<int> > chainSetIt(chainSet);
0301         while (chainSetIt.hasNext()) { // walk through chainSet and look for chainCheck
0302             chainSetIt.next();
0303             QSet<int> chainSetI = chainSetIt.value();
0304             if (chainSetI == chainCheck) { // found chainCheck in chainSet, don't add
0305                 newChain = false;
0306                 break;
0307             }
0308         }
0309         if (newChain) { // chainCheck not in chainSet
0310             chainSet.insert(j.key(), chainCheck);
0311         }
0312     }
0313     ////qDebug() << "chainSet:" << chainSet;
0314 
0315     // analyze chains
0316     // TODO: find loop chains to calculate sacrifices (loopChains are a subset of longChains)
0317     int shortChains = 0; // chains <= 2 lines
0318     int longChains = 0; // exploitable chains
0319     QMapIterator<int, QSet<int> > chainSetIt(chainSet);
0320     while (chainSetIt.hasNext()) {
0321         chainSetIt.next();
0322         QSet<int> chainSetI = chainSetIt.value();
0323         if (chainSetI.size() <= 3) {
0324             shortChains++;
0325         } else {
0326             longChains++;
0327         }
0328     }
0329     ////qDebug() << "short chains:" << shortChains << ", long chains: " << longChains;
0330 
0331     if (
0332         (
0333             (ownLinesCnt == 2) || // sacrifice 2 squares squares to opponent to get next chain.
0334             (ownLinesCnt == 3 && ownSquaresCnt == 4) // this is for loop chains which require a sacrifice of 4 squares
0335         )
0336         &&
0337         longChains > 0 // only do it if there is at least one chain to steal
0338         &&
0339         safeMoves().size() == 0 // only do it in endgames
0340     ) {
0341         //qDebug() << "HAHA, our chance to do the evil thing!";
0342         int magicLine = -1; // line in own moves that is used to get the next chain (draw there to give 2/4 squares to opponent)
0343         // formal definition of magicLine: line that when completed will leave at least one other line in own moves that completes two squares at once
0344         // the opposite of magic line will be used in the hard hearted handout to make sure that the opponent won't be able to do the evil move
0345         for (int i = 0; i < ownMoves.size(); i++) {
0346             memcpy(myLines.data(), lines, linesSize); // we want to look one line into the future game
0347             myLines[ownMoves.at(i)] = true; // try ownMove i (one line in chain that ai will get)
0348             for (int j = 0; j < ownMoves.size(); j++) { // test other lines in own moves
0349                 if (i == j) {
0350                     continue;
0351                 }
0352                 int leftSquares = 0; // count squares that can be completed by other line (j)
0353                 QList<int> adjacentSquares = squaresFromLine(ownMoves.at(j));
0354                 for (int k = 0; k < adjacentSquares.size(); k++) {
0355                     if (countBorderLines(adjacentSquares.at(k), &(*myLines)) == 3) {
0356                         leftSquares++;
0357                     }
0358                 }
0359                 if (leftSquares == 2) { // we found a line that will yield another line in own moves that completes two squares
0360                     magicLine = i;
0361                 }
0362             }
0363         }
0364         //qDebug() << "Magic Line index:" << magicLine;
0365         QList<int> bestMoves;
0366         if (ownMoves.size() > 1) {
0367             int ownMove = 1;
0368             if (magicLine >= 0 && magicLine < ownMoves.size()) {
0369                 ownMove = magicLine;
0370             }
0371             bestMoves.append(ownMoves.at(ownMove)); // choose the second line found! in case of 2 squares for ai this will choose the line at the end of the chain. in case of 4 squares this will be the line in the middle, leaving two lines that complete two squares each. FIX: 1 doesn't work in some cases because the algorithm doesn't detect chains by spatial connectedness. ie if there are two ends of a chain the search algorithm can jump between those two ends, messing up the order in ownMoves list. solution is magicLine
0372             return bestMoves;
0373         }
0374     }
0375 
0376     if (ownMoves.size() > 0) { // complete own chain
0377         QList<int> bestMoves;
0378         bestMoves.append(ownMoves.at(0));
0379         return bestMoves;
0380     }
0381 
0382     if (linePointDamage.begin().key() == 2) { // opponent will get 2 squares
0383         int handoutLine = -1;
0384         QList<int> opponentChain;
0385         QMapIterator<int, QSet<int> > chainSetIt(chainSet);
0386         while (chainSetIt.hasNext()) {
0387             chainSetIt.next();
0388             QSet<int> chainSetI = chainSetIt.value();
0389             if (chainSetI.contains(linePointDamage.begin().value())) {
0390                 opponentChain = chainSetI.values();
0391             }
0392         }
0393         for (int i = 0; i < opponentChain.size(); i++) {
0394             memcpy(myLines.data(), lines, linesSize); // we want to look one line into the future game
0395             myLines[opponentChain.at(i)] = true; // try move in chain for opponent
0396             for (int j = 0; j < opponentChain.size(); j++) { // test other lines in chain
0397                 if (i == j) {
0398                     continue;
0399                 }
0400                 int badSquares = 0; // count squares with two open lines (those are dangerous)
0401                 QList<int> adjacentSquares = squaresFromLine(opponentChain.at(j));
0402                 for (int k = 0; k < adjacentSquares.size(); k++) {
0403                     if (countBorderLines(adjacentSquares.at(k), &(*myLines)) != 3) {
0404                         badSquares++;
0405                     }
0406                 }
0407                 if (badSquares == 0) {
0408                     handoutLine = i;
0409                 }
0410             }
0411         }
0412         if (handoutLine >= 0) {
0413             ////qDebug() << "Hard hearted handout at" << opponentChain.at(handoutLine);
0414             QList<int> retMove;
0415             retMove.append(opponentChain.at(handoutLine));
0416             return retMove;
0417         }
0418     }
0419 
0420     // fallback to middle ai move
0421     QList<int> bestMoves = linePointDamage.values(linePointDamage.begin().key());   //this is a list of the indices of the lines that are the least damaging. linePointDamage.begin() returns the 1st pair in the QMap, sorted in ascending order by Key (damage of move)
0422     return bestMoves;
0423 }
0424 
0425 int aiController::countBorderLines(int *sidesOfSquare, int squareIndex, const bool *linesList) const
0426 {
0427     int count = 0;
0428 
0429     linesFromSquare(sidesOfSquare, squareIndex);
0430 
0431     //TODO: replace this with a QList 'count' type function?
0432     if (linesList[sidesOfSquare[0]] == true) {
0433         count++;
0434     }
0435     if (linesList[sidesOfSquare[1]] == true) {
0436         count++;
0437     }
0438     if (linesList[sidesOfSquare[2]] == true) {
0439         count++;
0440     }
0441     if (linesList[sidesOfSquare[3]] == true) {
0442         count++;
0443     }
0444     ////qDebug() << "AI: Square" << squareIndex << "is bordered by" << count << "lines";
0445     return count;
0446 }
0447 
0448 int aiController::countBorderLines(int squareIndex, const bool *linesList) const
0449 {
0450     int tempLineList[4];
0451     return countBorderLines(tempLineList, squareIndex, linesList);
0452 }
0453 
0454 QList<int> aiController::squaresFromLine(int lineIndex) const
0455 {
0456     ////qDebug() << "Line:" << lineIndex;
0457     QList<int> squareList;
0458     if (lineDirection(lineIndex) == KSquares::HORIZONTAL) {
0459         squareList.append(lineIndex - ((width + 1) * (lineIndex / ((width * 2) + 1))));
0460         squareList.append(squareList.at(0) - width);
0461         if (squareList.at(1) < 0) {
0462             squareList.removeAt(1);
0463         }
0464         if (squareList.at(0) >= (width * height)) {
0465             squareList.removeAt(0);
0466         }
0467 
0468     } else if (lineDirection(lineIndex) == KSquares::VERTICAL) {
0469         squareList.append(lineIndex - ((lineIndex / ((width * 2) + 1))*width + (lineIndex / ((width * 2) + 1)) + width));
0470         squareList.append(squareList.at(0) - 1);
0471         if (lineIndex % ((2 * width) + 1) == width) {
0472             squareList.removeAt(1);
0473         }
0474         if (lineIndex % ((2 * width) + 1) == 2 * width) {
0475             squareList.removeAt(0);
0476         }
0477     }
0478     ////qDebug() << "Size:" << squareList.size();
0479     ////qDebug() << "squares:" << squareList.at(0) << " " << squareList.at(1);
0480     return squareList;
0481 }
0482 
0483 void aiController::linesFromSquare(int *linesFromSquare, int squareIndex) const
0484 {
0485     int index1 = (squareIndex / width) * ((2 * width) + 1) + (squareIndex % width);
0486     int index2 = index1 + width;
0487     int index3 = index2 + 1;
0488     int index4 = index3 + width;
0489     linesFromSquare[0] = index1;
0490     linesFromSquare[1] = index2;
0491     linesFromSquare[2] = index3;
0492     linesFromSquare[3] = index4;
0493 }
0494 
0495 KSquares::Direction aiController::lineDirection(int lineIndex) const
0496 {
0497     int index2 = lineIndex % ((2 * width) + 1);
0498     KSquares::Direction dir;
0499     if (index2 < width) {
0500         dir = KSquares::HORIZONTAL;
0501     } else {
0502         dir = KSquares::VERTICAL;
0503     }
0504 
0505     return dir;
0506 }