DFS for AI Game State Search using too much memory

Question

I'm doing a CS course, and currently taking a AI class. We have to solve the 15 puzzle using various algorithms, like DFS, BFS, A* etc.

Currently we have implemented pretty much everything, but we are having memory problems with the DFS.

I have locked the DFS so that when he first reaches a depth of 1 million, it stops. It shouldn't really use that much memory from my calculations, should be around 100 MB total, yet, it says it is using almost 1GB. I have tried to find a lot of solutions to this, but I just cannot understand what is going on.

Game.cpp

#include "Game.h"
#include "Util.h"
using namespace std;

vector<vector<unsigned char>> mat;
static vector<pair<signed char, signed char>> directions = {make_pair(-1, 0), make_pair(1, 0), make_pair(0, 1), make_pair(0, -1)};

pair<unsigned char, unsigned char> blankPosition;
int depth;
string path;
static int nodeCount = 0;

// Creates a new game
Game::Game()
{
    depth = 0;
    path = "";
    mat.resize(WIDTH);
    for (int row = 0; row < WIDTH; row++)
    {
        mat[row].resize(WIDTH);
        for (int col = 0; col < WIDTH; col++)
        {
            scanf("%hhu", &mat[row][col]);
            path += to_string(mat[row][col]) + ' ';
            if (mat[row][col] == 0)
                blankPosition = make_pair(row, col);
        }
    }
}

Game::Game(vector<vector<unsigned char>> mat, pair<unsigned char, unsigned char> blankPosition, int depth)
{
    this->mat = mat;
    this->blankPosition = blankPosition;
    this->path = Util::MatrixToString(mat);
    this->depth = depth;
}

vector<Game> Game::CreateChildren()
{
    vector<Game> games;
    for (auto x : directions)
    {
        if (x.first + blankPosition.first > 3 || x.first + blankPosition.first < 0)
            continue;
        if (x.second + blankPosition.second > 3 || x.second + blankPosition.second < 0)
            continue;

        vector<vector<unsigned char>> matTemp = mat;
        swap(matTemp[x.first + blankPosition.first][x.second + blankPosition.second], matTemp[blankPosition.first][blankPosition.second]);

        pair<int, int> newGameBlankPosition = make_pair(x.first + blankPosition.first, x.second + blankPosition.second);
        Game g = Game(matTemp, newGameBlankPosition, depth + 1);
        games.push_back(g);
    }
    return games;
}

void Game::PrintGame()
{
    for (int row = 0; row < WIDTH; row++)
    {
        for (int col = 0; col < WIDTH; col++)
        {
            if (mat[row][col] < 10)
            {
                cout << ' ' << static_cast<int>(mat[row][col]) << ' ';
            }
            else
            {
                cout << static_cast<int>(mat[row][col]) << ' ';
            }
        }

        cout << '\n';
    }
    cout << "--\n";
}

// Compares two games to see if theyre equal
// Passed by reference for efficiency
bool Game::operator==(Game *rhs)
{
    for (int row = 0; row < WIDTH; row++)
    {
        for (int col = 0; col < WIDTH; col++)
        {
            if (mat[row][col] != rhs->mat[row][col])
                return false;
        }
    }
    return true;
}

Game.h

#pragma once
#include <bits/stdc++.h>
using namespace std;

class Game
{
public:
    vector<vector<unsigned char>> mat;
    pair<unsigned char, unsigned char> blankPosition;
    string path;
    int depth;

    Game(); // Takes input from the standard input ONLY
    Game(vector<vector<unsigned char>> mat, pair<unsigned char, unsigned char> blankPosition, int depth);
    void PrintGame();
    vector<Game> CreateChildren();
    bool operator==(Game *rhs);
};

Util.cpp

#include "Util.h"
using namespace std;

int Util::manhattan_distance(pair<unsigned char, unsigned char> &point1, pair<unsigned char, unsigned char> &point2)
{
    return abs(point1.first - point2.first + point1.second - point2.second);
}

// Converts a matrix into an array.
void Util::convert_to_array(vector<vector<unsigned char>> &inMatrix, vector<unsigned char> &outArray)
{
    int pos = 0;
    for (int row = 0; row < WIDTH; row++)
    {
        for (int col = 0; col < WIDTH; col++)
        {
            outArray.push_back(inMatrix[row][col]);
        }
    }
}

// Converts a matrix into a string
string Util::MatrixToString(vector<vector<unsigned char>> &inMatrix)
{
    string result = "";
    for (int row = 0; row < WIDTH; row++)
    {
        for (int col = 0; col < WIDTH; col++)
        {
            result += to_string(inMatrix[row][col]) + ' ';
        }
    }
    return result;
}

void Util::print_path(string &path, int &depth)
{
    int pos = 0;
    for (int curDepth = 0; curDepth <= depth; curDepth++)
    {
        for (int row = 0; row < WIDTH; row++)
        {
            for (int col = 0; col < WIDTH; col++)
            {
                if (isdigit(path[pos]) && isdigit(path[pos + 1]))
                {
                    cout << path[pos] << path[pos + 1] << ' ';
                    pos += 2;
                }
                else if (isdigit(path[pos]))
                {
                    cout << ' ' << path[pos] << ' ';
                    pos++;
                }
                else
                {
                    pos++;
                    col--;
                }
            }
            cout << '\n';
        }
        cout << "============\n";
    }
}

int Util::count_transpositions(Game &initialState, Game &finalState)
{ // isto corre em n^2 (talvez dê para fazer melhor..)
    // a lógica é contar o número de swaps que têm de ser feitos (temos de pensar porque é que isto funciona (se funcionar))
    vector<unsigned char> configuration1(WIDTH * WIDTH);
    vector<unsigned char> configuration2(WIDTH * WIDTH);
    convert_to_array(initialState.mat, configuration1);
    convert_to_array(finalState.mat, configuration2);

    int transpositions = 0;
    for (int i = 0; i < WIDTH * WIDTH; ++i)
    { // mudar width * width
        if (configuration1[i] == configuration2[i])
            continue;
        for (int j = i; j < WIDTH * WIDTH; ++j)
        {
            if (configuration1[i] != configuration2[j])
                continue;
            swap(configuration2[i], configuration2[j]);
            ++transpositions;
            break;
        }
    }
    return transpositions;
}

bool Util::check_solvability(Game &initialState, Game &finalState)
{
    int manDist = manhattan_distance(initialState.blankPosition, finalState.blankPosition);
    int trans = count_transpositions(initialState, finalState);

    return (manDist + trans) % 2 == 0;
}

int Util::CountInversions(Game &game)
{
    vector<unsigned char> arr;
    convert_to_array(game.mat, arr);

    int inversions = 0;
    for (int i = 0; i < WIDTH * WIDTH; i++)
    {
        for (int j = i + 1; j < WIDTH * WIDTH; j++)
        {
            if (arr[i] > arr[j] && arr[j] != 0)
                inversions++;
        }
    }

    return inversions;
}

bool Util::CheckSolvability(Game &initialState, Game &finalState)
{
    int invI = CountInversions(initialState);
    int invF = CountInversions(finalState);

    bool condI = ((invI % 2 == 0) == (initialState.blankPosition.first % 2 == 1));
    bool condF = ((invF % 2 == 0) == (finalState.blankPosition.first % 2 == 1));

    return (condI == condF);
}

Util.h

#pragma once
#include <bits/stdc++.h>
#include "Game.h"

using namespace std;
#define WIDTH 4

namespace Util
{
    // Calculates the manhattan distance between two points
    int manhattan_distance(pair<unsigned char, unsigned char> &point1, pair<unsigned char, unsigned char> &point2);

    // Converts a matrix into an array.
    void convert_to_array(vector<vector<unsigned char>> &inMatrix, vector<unsigned char> &outArray);

    // Checks if an initialState can be transformed into a finalState
    bool check_solvability(Game &initialState, Game &finalState);

    int count_transpositions(Game &initialState, Game &finalState);

    string MatrixToString(vector<vector<unsigned char>> &inMatrix);

    void print_path(string &path, int &depth);

    int CountInversions(Game &game);

    bool CheckSolvability(Game &initialState, Game &finalState);

}

Main.cpp

#include "Game.h"
#include "Util.h"
#pragma GCC optimize("Ofast")

using namespace std;

// g++ -Wall -o main main.cpp && ./main
Game initial;
Game final;

void PrintSolution(stack<Game> visitedStack, int nodes)
{
    int size = visitedStack.size();
    int depth = visitedStack.top().depth;
    while (!visitedStack.empty())
    {
        visitedStack.top().PrintGame();
        visitedStack.pop();
    }

    cout << "Caminho Encontrado!\n";
    // Do the thing here
    cout << "Depth: " << depth << '\n';
    // cout << "Explored: " << nodes << '\n';
    return;
}
int nodeCount = 0;
bool DFS(int DEPTH)
{
    stack<Game> iterativeStack;
    stack<Game> visitedStack;
    unordered_set<string> visited;

    iterativeStack.push(initial);
    visitedStack.push(initial);
    int previousDepth = -1;

    while (!iterativeStack.empty())
    {
        Game currentGame = iterativeStack.top();
        iterativeStack.pop();

        if (currentGame.depth <= previousDepth)
        {
            for (int i = 0; i < previousDepth - currentGame.depth + 1; i++)
            {
                // TODO: Apagar o node
                nodeCount--;
                visited.erase(visitedStack.top().path);
                visitedStack.pop();
            }
        }

        visited.insert(currentGame.path);
        visitedStack.push(currentGame);

        previousDepth = currentGame.depth;

        vector<Game> games;

        if (currentGame.depth < DEPTH)
            games = currentGame.CreateChildren();
        else
            return false;

        for (Game child : games)
        {
            if (visited.find(child.path) != visited.end())
            {
                continue;
            }
            nodeCount++;
            if (child.path == final.path)
            {
                visited.clear();

                iterativeStack.empty();
                visitedStack.push(child);
                PrintSolution(visitedStack, 3);
                return true;
            }
            iterativeStack.push(child);
        }
    }

    return false;
}
int main()
{
    if (!Util::CheckSolvability(initial, final))
    {
        cout << "Impossivel :( \n";
        return -1;
    }

    DFS(1000000);

    return 0;
}

The code is a bit messy, because we have been trying to fix it, so somethings are not as clear as they will be. I'm sorry if this is a bad way to show the code, but I didn't know if I could paste links to it.

Anyway, when I run the program using this input:

1 2 3 4 5 6 8 12 13 9 0 7 14 11 10 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0

and this command: /usr/bin/time -v ./out < input1, it says that the "Maximum resident set size (kbytes):" is 828360, which is around 800MB, around 10times what it should be using.

Previously, the Game.cpp class was using all Integers, and it was using around 800MB, after I implemented it using unsigned chars, it was still using the same amount, which I find very weird. Shouldn't it use way less memory?