aicontroller.cpp

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2006 by Matthew Williams    <matt@milliams.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.                                   *
 ***************************************************************************/

#include "aicontroller.h"

#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)
{
    linesSize = newLines.count();
    lines = new bool[linesSize];
    for (int i = 0; i < linesSize; ++i) lines[i] = newLines[i];
    srand( (unsigned)time( NULL ) );
    kDebug() << "AI: Starting AI level" << Settings::difficulty();
}

aiController::~aiController()
{
    delete[] lines;
}

QList<int> aiController::autoFill(int safeMovesLeft)
{
    QList<int> fillLines;
    
    // add a random safe moves while there are safe moves left
    QList<int> next;
    //kDebug() << safeMoves().isEmpty();
    while( !( (next = safeMoves()).isEmpty() ) )
    {
        int nextLine = next[rand() % next.size()];
        lines[nextLine] = true;
        //kDebug() << nextLine;
        fillLines << nextLine;
    }
    
    // safeMovesLeft times delete a line from fillLines
    for (int i = 0; i<safeMovesLeft; ++i)
    {
        if (fillLines.isEmpty()) break;
        int index = rand() % fillLines.size();
        fillLines.removeAt(index);
    }
    
    return fillLines;
}

int aiController::chooseLine() const
{
    QList<int> choiceList;
    for(int i=0; i<linesSize; i++)  //trying to get points. looking for squares with 3 lines
    {
        if(!lines[i])
        {
            QList<int> adjacentSquares = squaresFromLine(i);
            for(int j=0; j<adjacentSquares.size(); j++)
            {
                
                if(countBorderLines(adjacentSquares.at(j), lines) == 3) //if 3 lines, draw there to get points!
                {
                    choiceList.append(i);
                    //kDebug() << "AI: 1. Adding" << i << "to choices";
                }
            }
        }
    }
    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);
        return choiceList.at(randChoice);
    }
    
    choiceList = safeMoves();
    
    if(choiceList.size() != 0)
    {
        float randomFloat = ((float) rand()/(RAND_MAX + 1.0))*(choiceList.size()-1);
        int randChoice = (short)(randomFloat)/1;
        kDebug() << "AI: 2. Drawing line at index:" << choiceList.at(randChoice);
        return choiceList.at(randChoice);
    }
    
    choiceList.clear();
    for(int i=0; i<linesSize; i++)  //have to take what's left
    {
        if(!lines[i])
        {
            QList<int> adjacentSquares = squaresFromLine(i);
            for(int j=0; j<adjacentSquares.size(); j++)
            {
                
                if(countBorderLines(adjacentSquares.at(j), lines) == 2) //if 2 lines (they're all that's left!)
                {
                    choiceList.append(i);
                    //kDebug() << "AI: 3. Adding" << i << "to choices";
                }
            }
        }
    }
    if(Settings::difficulty() >= 1) //Hard(2/3) //do some damage control :)
    {
        QList<int> goodChoiceList = chooseLeastDamaging(choiceList);
        if(goodChoiceList.size() != 0)
        {
            float randomFloat = ((float) rand()/(RAND_MAX + 1.0))*(goodChoiceList.size()-1);
            int randChoice = (short)(randomFloat)/1;
            kDebug() << "AI: 3. Drawing line at index:" << goodChoiceList.at(randChoice);
            return goodChoiceList.at(randChoice);
        }
    }

    if(choiceList.size() != 0)
    {
        float randomFloat = ((float) rand()/(RAND_MAX + 1.0))*(choiceList.size()-1);
        int randChoice = (short)(randomFloat)/1;
        kDebug() << "AI: 3. Drawing line at index:" << choiceList.at(randChoice);
        return choiceList.at(randChoice);
    }
        return 0;
}

QList<int> aiController::safeMoves() const
{
    QList<int> safeLines;
    for(int i=0; i<linesSize; i++)  //finding totally safe moves. avoiding squares with 2 lines
    {
        if(!lines[i])
        {
            QList<int> adjacentSquares = squaresFromLine(i);
            int badCount = 0;
            for(int j=0; j<adjacentSquares.size(); j++)
            {
                if(countBorderLines(adjacentSquares.at(j), lines) == 2) //don't want to make 3 lines around a square
                {
                    badCount++;
                }
            }
            if(badCount == 0)
            {
                safeLines.append(i);
                //kDebug() << "AI: 2. Adding" << i << "to choices";
            }
        }
    }
    return safeLines;
}

QList<int> aiController::chooseLeastDamaging(const QList<int> &choiceList) const
{
    //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];
    
    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
        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:
                {
                    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 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
                {
                    squareFound = false;    //we couldn't find a square this time round so we'll try the next 'i'
                }
            }
        } 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);
    }
    
    //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;
}

int aiController::countBorderLines(int *sidesOfSquare, int squareIndex, const bool *linesList) const
{
    int count = 0;
    
    linesFromSquare(sidesOfSquare, squareIndex);
    
    //TODO: replace this with a QList 'count' type function?
    if(linesList[sidesOfSquare[0]] == true)
        count++;
    if(linesList[sidesOfSquare[1]] == true)
        count++;
    if(linesList[sidesOfSquare[2]] == true)
        count++;
    if(linesList[sidesOfSquare[3]] == true)
        count++;
    //kDebug() << "AI: Square" << squareIndex << "is bordered by" << count << "lines";
    return count;
}

int aiController::countBorderLines(int squareIndex, const bool *linesList) const
{
    int tempLineList[4];
    return countBorderLines(tempLineList, squareIndex, linesList);
}

QList<int> aiController::squaresFromLine(int lineIndex) const
{
    //kDebug() << "Line:" << lineIndex;
    QList<int> squareList;
    if (lineDirection(lineIndex) == KSquares::HORIZONTAL)
    {
        squareList.append(lineIndex - ( (width+1) * (lineIndex/((width*2)+1)) ));
        squareList.append(squareList.at(0) - width);
        if(squareList.at(1) < 0)
            squareList.removeAt(1);
        if(squareList.at(0) >= (width*height))
            squareList.removeAt(0);
            
    }
    else if (lineDirection(lineIndex) == KSquares::VERTICAL)
    {
        squareList.append(lineIndex - ( (lineIndex/((width*2)+1))*width + (lineIndex/((width*2)+1)) + width ));
        squareList.append(squareList.at(0) - 1);
        if(lineIndex%((2*width)+1) == width)
            squareList.removeAt(1);
        if(lineIndex%((2*width)+1) == 2*width)
            squareList.removeAt(0);
    }
    //kDebug() << "Size:" << squareList.size();
    //kDebug() << "squares:" << squareList.at(0) << " " << squareList.at(1);
    return squareList;
}

void aiController::linesFromSquare(int *linesFromSquare, int squareIndex) const
{
    int index1 = (squareIndex/width) * ((2*width) + 1) + (squareIndex%width);
    int index2 = index1 + width;
    int index3 = index2 + 1;
    int index4 = index3 + width;
    linesFromSquare[0] = index1;
    linesFromSquare[1] = index2;
    linesFromSquare[2] = index3;
    linesFromSquare[3] = index4;
}

KSquares::Direction aiController::lineDirection(int lineIndex) const
{
    int index2 = lineIndex % ((2*width) + 1);
    KSquares::Direction dir;
    if(index2 < width)
        dir = KSquares::HORIZONTAL;
    else
        dir = KSquares::VERTICAL;
    
    return dir;
}