Hello community, here is the log from the commit of package ksquares for openSUSE:Factory checked in at 2013-12-02 12:35:21 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/ksquares (Old) and /work/SRC/openSUSE:Factory/.ksquares.new (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ksquares" Changes: -------- --- /work/SRC/openSUSE:Factory/ksquares/ksquares.changes 2013-10-03 16:01:49.000000000 +0200 +++ /work/SRC/openSUSE:Factory/.ksquares.new/ksquares.changes 2013-12-02 12:35:23.000000000 +0100 @@ -1,0 +2,21 @@ +Sat Nov 16 18:30:30 UTC 2013 - [email protected] + +- Update to 4.11.90 + * KDE 4.12 Beta 2 release + * See http://www.kde.org/announcements/announce-4.12-beta2.php + +------------------------------------------------------------------- +Sun Nov 10 08:02:48 UTC 2013 - [email protected] + +- Update to 4.11.80 + * KDE 4.12 Beta 1 release + * See http://www.kde.org/announcements/announce-4.12-beta1.php + +------------------------------------------------------------------- +Sat Nov 2 15:48:46 UTC 2013 - [email protected] + +- Update to 4.11.3 + * KDE 4.11.3 bugfix release + * See http://www.kde.org/announcements/announce-4.11.3.php + +------------------------------------------------------------------- Old: ---- ksquares-4.11.2.tar.xz New: ---- ksquares-4.11.90.tar.xz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ ksquares.spec ++++++ --- /var/tmp/diff_new_pack.SwTNjb/_old 2013-12-02 12:35:24.000000000 +0100 +++ /var/tmp/diff_new_pack.SwTNjb/_new 2013-12-02 12:35:24.000000000 +0100 @@ -23,7 +23,7 @@ License: GPL-2.0+ Group: Amusements/Games/Action/Arcade Url: http://www.kde.org -Version: 4.11.2 +Version: 4.11.90 Release: 0 Source0: ksquares-%{version}.tar.xz BuildRoot: %{_tmppath}/%{name}-%{version}-build ++++++ ksquares-4.11.2.tar.xz -> ksquares-4.11.90.tar.xz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ksquares-4.11.2/src/aicontroller.cpp new/ksquares-4.11.90/src/aicontroller.cpp --- old/ksquares-4.11.2/src/aicontroller.cpp 2013-06-28 19:50:28.000000000 +0200 +++ new/ksquares-4.11.90/src/aicontroller.cpp 2013-10-16 23:02:04.000000000 +0200 @@ -12,6 +12,8 @@ #include <ctime> #include <kdebug.h> +#include <QSet> + #include "settings.h" aiController::aiController(int newPlayerId, const QList<bool> &newLines, const QList<int> &newSquareOwners, int newWidth, int newHeight) : squareOwners(newSquareOwners), playerId(newPlayerId), width(newWidth), height(newHeight) @@ -20,7 +22,7 @@ lines = new bool[linesSize]; for (int i = 0; i < linesSize; ++i) lines[i] = newLines[i]; srand( (unsigned)time( NULL ) ); - kDebug() << "AI: Starting AI..."; + kDebug() << "AI: Starting AI level" << Settings::difficulty(); } aiController::~aiController() @@ -75,6 +77,23 @@ } if(choiceList.size() != 0) { + if(Settings::difficulty() == 2) // to play good ai has to look into the future game + { + QList<int> openLines; // list of not yet drawn lines + for(int i = 0; i < linesSize; i++) + { + if(!lines[i]) + { + openLines.append(i); + } + } + QList<int> choices=chooseLeastDamaging(openLines); // run extended damage control + if(choices.size() > 0) + { + kDebug() << "AI: 4. Drawing line at index:" << choices.at(0); + return choices.at(0); + } + } float randomFloat = ((float) rand()/(RAND_MAX + 1.0))*(choiceList.size()-1); int randChoice = (short)(randomFloat)/1; kDebug() << "AI: 1. Drawing line at index:" << choiceList.at(randChoice); @@ -108,7 +127,7 @@ } } } - if(Settings::difficulty() == 1) //Hard(2/3) //do some damage control :) + if(Settings::difficulty() >= 1) //Hard(2/3) //do some damage control :) { QList<int> goodChoiceList = chooseLeastDamaging(choiceList); if(goodChoiceList.size() != 0) @@ -119,7 +138,7 @@ return goodChoiceList.at(randChoice); } } - QList<int> goodcChoiceList = chooseLeastDamaging(choiceList); + if(choiceList.size() != 0) { float randomFloat = ((float) rand()/(RAND_MAX + 1.0))*(choiceList.size()-1); @@ -160,31 +179,141 @@ { //kDebug() << "AI: Checking" << choiceList.size() << "possible moves"; QMap<int,int> linePointDamage; //this will be a list of how damaging a certain move will be. Key = damage of move, Value = index of line + QScopedArrayPointer<bool> linesCopy(new bool[linesSize]); //make temporary local copies of lists int sidesOfSquare[4]; - bool *linesCopy = new bool[linesSize]; //make temporary local copies of lists - for(int i=0; i<choiceList.size(); i++) //cycle through all the possible moves + + QMap<int, QSet<int> > chains; // this is a raw list of chains (which are sets of lines). key = random element of chain + QMap<int, QSet<int> > chainSet; // same thing as chains but with unique chains + QList<QList<int> > ownChains; // chains that ai will get in this run. those chains are taken in myLines. + QList<int> ownMoves; // contains lines of chain that the ai will take first (this will contain the returned move) + QScopedArrayPointer<bool> myLines(new bool[linesSize]); //make temporary local copies of lists + int ownLinesCnt = 0; // count of how many lines ai will take in this run + int ownSquaresCnt = 0; // count of how many squares ai will get in this run + + if (Settings::difficulty() > 1) + { + memcpy(myLines.data(), lines, linesSize); // lines --> myLines (complete own chains) --> linesCopy (analyze damage/chains for next runs) + bool chainFound; + // 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 + do // this loop completes all chains the opponent gave to ai + { + chainFound = false; + for(int curSquare = 0; curSquare < squareOwners.size(); curSquare++) // walk through squares and search for start of chain + { + QList<int> ownChain; // remember completed chain lines + int chainSquare = curSquare; + bool squareFound; + do { // this loop walks through a chain square by square + squareFound = false; + if(countBorderLines(sidesOfSquare, chainSquare, &(*myLines)) == 3) // found a square for ai + { + for(int sideOfSquare = 0; sideOfSquare <= 3; sideOfSquare++) + { + if(!myLines[sidesOfSquare[sideOfSquare]]) // found missing line of square + { + ownLinesCnt++; + + int nextSquareFound=-1; + QList<int> adjacentSquares = squaresFromLine(sidesOfSquare[sideOfSquare]); + for(int i = 0; i < adjacentSquares.size(); i++) + { + int chainSquareBorderCnt = countBorderLines(adjacentSquares.at(i), &(*myLines)); + if(chainSquare != adjacentSquares.at(i) && + chainSquareBorderCnt == 3) // check if a second square will be completed by this line + { + ownSquaresCnt++; // add extra square + } + if(chainSquareBorderCnt == 2) // look for next square in chain + { + nextSquareFound = adjacentSquares.at(i); + } + + } + myLines[sidesOfSquare[sideOfSquare]] = true; // complete line + if(nextSquareFound >= 0) + { + chainSquare = nextSquareFound; + } + ownChain.append(sidesOfSquare[sideOfSquare]); + } + } + squareFound = true; + chainFound = true; + ownSquaresCnt++; + } + } while(squareFound); + if(chainFound) + { + ownChains.append(ownChain); + break; + } + } + } while (chainFound); + //kDebug() << "ownChains:" << ownChains; + + // 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 + int minChain=-1; + int tmp=width*height*10; + for(int i = 0; i < ownChains.size(); i++) + { + if(tmp > ownChains.at(i).size()) + { + tmp = ownChains.at(i).size(); + minChain = i; + } + } + if(minChain >= 0) + { + ownMoves=ownChains.at(minChain); + } + //kDebug() << "ownMoves:" << ownMoves; + } + + for(int i = 0; i < choiceList.size(); i++) //cycle through all the possible moves { QList<int> squaresCopy = squareOwners; //make temporary local copies of lists - memcpy(linesCopy, lines, linesSize); //make temporary local copies of lists + QSet<int> chain; // set of lines that are given to opponent by move choiceList.at(i) + + if (Settings::difficulty() > 1) + { + memcpy(linesCopy.data(), myLines.data(), linesSize); //make temporary local copies of lists + if (linesCopy[choiceList.at(i)]) continue; // already covered. ai will get this line + } else { + memcpy(linesCopy.data(), lines, linesSize); //make temporary local copies of lists + } + linesCopy[choiceList.at(i)] = true; //we're going to try drawing a line here //now it would be the next player's turn so we're going to count how many squares they would be able to get. int count = 0; //this is how many points the next player will ge if you draw a line at choiceList.at(i) bool squareFound = false; + chain.insert(choiceList.at(i)); do { for(int currentSquare=0; currentSquare<squaresCopy.size(); currentSquare++) //cycle through the grid (by squares): { - if(countBorderLines(sidesOfSquare, currentSquare, linesCopy) == 3) //if we've found a square with three sides drawn: + if(countBorderLines(sidesOfSquare, currentSquare, &(*linesCopy)) == 3) //if we've found a square with three sides drawn: { count++; squareFound = true; //we found a square so we will look again for the next for(int sideOfSquare=0; sideOfSquare<=3; sideOfSquare++) //make the square complete in linesCopy { + if(Settings::difficulty() > 1 && !linesCopy[sidesOfSquare[sideOfSquare]]) + { + chain.insert(sidesOfSquare[sideOfSquare]); + QList<int> adjacentSquares = squaresFromLine(sidesOfSquare[sideOfSquare]); + for(int adjsq = 0; adjsq < adjacentSquares.size(); adjsq++) + { + if(currentSquare == adjacentSquares.at(adjsq)) continue; + if(countBorderLines(adjacentSquares.at(adjsq), &(*myLines)) == 3) + { // line will complete two squares + count++; + } + } + } linesCopy[sidesOfSquare[sideOfSquare]] = true; //draw at this squares - - } //now this square is completed by the second player. + } //now current square is completed by the second player. break; //since we found a square with 3 sides completed (now = 4), we break the 'for(currentSquare)' loop } else @@ -194,9 +323,166 @@ } } while(squareFound == true); //while we're still finding squares linePointDamage.insertMulti(count, choiceList.at(i)); //insert a pair with Key=count, Value=i + chains.insert(choiceList.at(i), chain); } - delete[] linesCopy; + //kDebug() << "linePointDamage:" << linePointDamage; + + if(Settings::difficulty() < 2) // middle ai won't analyze the game further + { + 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) + return bestMoves; + } + + //kDebug() << chains; + // remove double entries from chains to get chainSet + QMapIterator<int, QSet<int> > j(chains); + while(j.hasNext()) // walk through chains and add chain to chainSet (if not already contained) + { + j.next(); + bool newChain = true; + QSet<int> chainCheck = j.value(); // this is the chain we might add + QMapIterator<int, QSet<int> > chainSetIt(chainSet); + while(chainSetIt.hasNext()) // walk through chainSet and look for chainCheck + { + chainSetIt.next(); + QSet<int> chainSetI = chainSetIt.value(); + if(chainSetI == chainCheck) // found chainCheck in chainSet, don't add + { + newChain = false; + break; + } + } + if (newChain) // chainCheck not in chainSet + { + chainSet.insert(j.key(), chainCheck); + } + } + //kDebug() << "chainSet:" << chainSet; + + // analyze chains + // TODO: find loop chains to calculate sacrifices (loopChains are a subset of longChains) + int shortChains = 0; // chains <= 2 lines + int longChains = 0; // exploitable chains + QMapIterator<int, QSet<int> > chainSetIt(chainSet); + while(chainSetIt.hasNext()) + { + chainSetIt.next(); + QSet<int> chainSetI = chainSetIt.value(); + if (chainSetI.size() <= 3) + { + shortChains++; + } else + { + longChains++; + } + } + //kDebug() << "short chains:" << shortChains << ", long chains: " << longChains; + + if( + ( + (ownLinesCnt == 2) || // sacrifice 2 squares squares to opponent to get next chain. + (ownLinesCnt == 3 && ownSquaresCnt == 4) // this is for loop chains which require a sacrifice of 4 squares + ) + && + longChains > 0 // only do it if there is at least one chain to steal + && + safeMoves().size() == 0 // only do it in endgames + ) + { + kDebug() << "HAHA, our chance to do the evil thing!"; + int magicLine = -1; // line in own moves that is used to get the next chain (draw there to give 2/4 squares to opponent) + // formal definition of magicLine: line that when completed will leave at least one other line in own moves that completes two squares at once + // 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 + for(int i = 0; i < ownMoves.size(); i++) + { + memcpy(myLines.data(), lines, linesSize); // we want to look one line into the future game + myLines[ownMoves.at(i)] = true; // try ownMove i (one line in chain that ai will get) + for(int j = 0; j < ownMoves.size(); j++) // test other lines in own moves + { + if (i == j) continue; + int leftSquares = 0; // count squares that can be completed by other line (j) + QList<int> adjacentSquares = squaresFromLine(ownMoves.at(j)); + for(int k = 0; k < adjacentSquares.size(); k++) + { + if (countBorderLines(adjacentSquares.at(k), &(*myLines)) == 3) + { + leftSquares++; + } + } + if (leftSquares == 2) // we found a line that will yield another line in own moves that completes two squares + { + magicLine = i; + } + } + } + kDebug() << "Magic Line index:" << magicLine; + QList<int> bestMoves; + if(ownMoves.size() > 1) + { + int ownMove = 1; + if(magicLine >= 0 && magicLine < ownMoves.size()) + { + ownMove=magicLine; + } + 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 + return bestMoves; + } + } + + if(ownMoves.size() > 0) // complete own chain + { + QList<int> bestMoves; + bestMoves.append(ownMoves.at(0)); + return bestMoves; + } + + if(linePointDamage.begin().key() == 2) // opponent will get 2 squares + { + int handoutLine = -1; + QList<int> opponentChain; + QMapIterator<int, QSet<int> > chainSetIt(chainSet); + while(chainSetIt.hasNext()) + { + chainSetIt.next(); + QSet<int> chainSetI = chainSetIt.value(); + if(chainSetI.contains(linePointDamage.begin().value())) + { + opponentChain = chainSetI.values(); + } + } + for(int i = 0; i < opponentChain.size(); i++) + { + memcpy(myLines.data(), lines, linesSize); // we want to look one line into the future game + myLines[opponentChain.at(i)] = true; // try move in chain for opponent + for(int j = 0; j < opponentChain.size(); j++) // test other lines in chain + { + if (i == j) continue; + int badSquares = 0; // count squares with two open lines (those are dangerous) + QList<int> adjacentSquares = squaresFromLine(opponentChain.at(j)); + for(int k = 0; k < adjacentSquares.size(); k++) + { + if(countBorderLines(adjacentSquares.at(k), &(*myLines)) != 3) + { + badSquares++; + } + } + if(badSquares == 0) + { + handoutLine = i; + } + } + } + if(handoutLine >= 0) + { + //kDebug() << "Hard hearted handout at" << opponentChain.at(handoutLine); + QList<int> retMove; + retMove.append(opponentChain.at(handoutLine)); + return retMove; + } + } + + // fallback to middle ai move 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) return bestMoves; } diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ksquares-4.11.2/src/aicontroller.h new/ksquares-4.11.90/src/aicontroller.h --- old/ksquares-4.11.2/src/aicontroller.h 2013-06-28 19:50:28.000000000 +0200 +++ new/ksquares-4.11.90/src/aicontroller.h 2013-10-16 23:02:04.000000000 +0200 @@ -20,10 +20,12 @@ * When playing a game of squares there are a number of stages the game goes through: * @li The random line placement stage. Where players are just placing lines while trying to not complete the third side of any squares * @li Next players will try to only draw the third side of a square if it will only give the opponent the minimum amount of points - * @li Finally, the more advanced player will, at the end of a large run of squares leave a small area at the end, forcing the opponent to take only that small section, leaving another large area open to him. - * Currently, the first two points are implemented. + * @li The more advanced player will, at the end of a large run of squares leave a small area at the end, forcing the opponent to take only that small section, leaving another large area open to him. + * @li The even more advanced player will fight for control over the game. This means that he will count the chains forming in the last phase of the "random line" game phase and thus make sure that he will be the one who gets the first long chain. This works like a Nim game somehow. + * Currently, the first three points are implemented. * * @author Matt Williams <[email protected]> + * @author Tom Vincent Peters <[email protected]> */ class aiController diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ksquares-4.11.2/src/ksquares.desktop new/ksquares-4.11.90/src/ksquares.desktop --- old/ksquares-4.11.2/src/ksquares.desktop 2013-08-28 19:12:50.000000000 +0200 +++ new/ksquares-4.11.90/src/ksquares.desktop 2013-10-16 23:02:04.000000000 +0200 @@ -103,6 +103,7 @@ GenericName[sr@latin]=Spajajte tačke i osvajajte polja GenericName[sv]=Sammanbind punkter för att skapa fyrkanter GenericName[tr]=Noktaları Birleştirerek Kare Yap +GenericName[ug]=چېكىتلەرنى تۇتاشتۇرۇپ كۋادرات ياشاش GenericName[uk]=З'єднайте точки, щоб створити квадрати GenericName[x-test]=xxConnect the dots to create squaresxx GenericName[zh_CN]=通过点连接创建方形 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ksquares-4.11.2/src/ksquareswindow.cpp new/ksquares-4.11.90/src/ksquareswindow.cpp --- old/ksquares-4.11.2/src/ksquareswindow.cpp 2013-06-28 19:50:28.000000000 +0200 +++ new/ksquares-4.11.90/src/ksquareswindow.cpp 2013-10-16 23:02:04.000000000 +0200 @@ -70,6 +70,7 @@ KScoreDialog ksdialog(KScoreDialog::Name, this); ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Easy"), i18n("Easy"))); ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Medium"), i18n("Medium"))); + ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Hard"), i18n("Hard"))); ksdialog.exec(); } @@ -239,10 +240,17 @@ case 0: ksdialog.setConfigGroup(qMakePair(QByteArray("Easy"), i18n("Easy"))); ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Medium"), i18n("Medium"))); + ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Hard"), i18n("Hard"))); break; case 1: ksdialog.setConfigGroup(qMakePair(QByteArray("Medium"), i18n("Medium"))); ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Easy"), i18n("Easy"))); + ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Hard"), i18n("Hard"))); + break; + case 2: + ksdialog.setConfigGroup(qMakePair(QByteArray("Hard"), i18n("Hard"))); + ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Easy"), i18n("Easy"))); + ksdialog.addLocalizedConfigGroupName(qMakePair(QByteArray("Medium"), i18n("Medium"))); break; } KScoreDialog::FieldInfo scoreInfo; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ksquares-4.11.2/src/main.cpp new/ksquares-4.11.90/src/main.cpp --- old/ksquares-4.11.2/src/main.cpp 2013-06-28 19:50:28.000000000 +0200 +++ new/ksquares-4.11.90/src/main.cpp 2013-10-16 23:02:04.000000000 +0200 @@ -22,7 +22,7 @@ static const char description[] = I18N_NOOP("Take it in turns to draw lines.\nIf you complete a squares, you get another go."); -static const char version[] = "0.4"; +static const char version[] = "0.5"; int main(int argc, char **argv) { @@ -31,6 +31,7 @@ "http://games.kde.org/ksquares";); about.addAuthor( ki18n("Matt Williams"), ki18n("Original creator and maintainer"), "[email protected]", "http://milliams.com"; ); about.addCredit(ki18n("Fela Winkelmolen"), ki18n("Many patches and bugfixes")); + about.addCredit(ki18n("Tom Vincent Peters"), ki18n("Hard AI")); KCmdLineArgs::init(argc, argv, &about); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ksquares-4.11.2/src/prefs_ai.ui new/ksquares-4.11.90/src/prefs_ai.ui --- old/ksquares-4.11.2/src/prefs_ai.ui 2013-06-28 19:50:28.000000000 +0200 +++ new/ksquares-4.11.90/src/prefs_ai.ui 2013-10-16 23:02:04.000000000 +0200 @@ -59,6 +59,11 @@ <string>Medium</string> </property> </item> + <item> + <property name="text" > + <string>Hard</string> + </property> + </item> </widget> </item> <item row="0" column="0" > -- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
