Gobang

五子棋游戏的OpenGL重构版。

1.0

#include <vector>
#include <unordered_map>
#include <queue>
#include <string>

namespace Computer
{
    class AhoCorasick
    {
      public:
        AhoCorasick(const std::vector<std::string>& patterns);
        AhoCorasick();

        std::vector<int> search(const std::string& text);

        void LoadPatterns(const std::vector<std::string>& patterns);

      private:
        struct TrieNode
        {
            std::unordered_map<char, TrieNode*> children;
            TrieNode*                           failureLink;
            std::vector<int>                    output;
            TrieNode()
                : failureLink(nullptr)
            {
            }
        };

        TrieNode*                root;
        std::vector<std::string> patterns;

        void buildTrie();
        void buildFailureLinks();
    };

}  // namespace Computer


#include "AhoCorasick.h"
namespace Computer
{
    AhoCorasick::AhoCorasick(const std::vector<std::string>& patterns)
        : patterns(patterns)
    {
        root = new TrieNode();
        buildTrie();
        buildFailureLinks();
    }


    AhoCorasick::AhoCorasick()
    {
        root = new TrieNode();
    }

    void AhoCorasick::LoadPatterns(const std::vector<std::string>& patterns)
    {
        this->patterns = patterns;
        buildTrie();
        buildFailureLinks();
    }
    void AhoCorasick::buildTrie()
    {
        for (int i = 0; i < patterns.size(); ++i)
        {
            TrieNode* node = root;
            for (char c : patterns[i])
            {
                if (node->children.find(c) == node->children.end())
                {
                    node->children[c] = new TrieNode();
                }
                node = node->children[c];
            }
            node->output.push_back(i);
        }
    }

    void AhoCorasick::buildFailureLinks()
    {
        std::queue<TrieNode*> q;
        root->failureLink = root;

        for (auto& [key, node] : root->children)
        {
            node->failureLink = root;
            q.push(node);
        }

        while (!q.empty())
        {
            TrieNode* current = q.front();
            q.pop();

            for (auto& [key, child] : current->children)
            {
                TrieNode* failure = current->failureLink;
                while (failure != root && failure->children.find(key) == failure->children.end())
                {
                    failure = failure->failureLink;
                }
                if (failure->children.find(key) != failure->children.end())
                {
                    child->failureLink = failure->children[key];
                }
                else
                {
                    child->failureLink = root;
                }

                child->output.insert(child->output.end(), child->failureLink->output.begin(), child->failureLink->output.end());
                q.push(child);
            }
        }
    }

    std::vector<int> AhoCorasick::search(const std::string& text)
    {
        std::vector<int> result;
        TrieNode*        node = root;

        for (char c : text)
        {
            while (node != root && node->children.find(c) == node->children.end())
            {
                node = node->failureLink;
            }
            if (node->children.find(c) != node->children.end())
            {
                node = node->children[c];
            }
            else
            {
                node = root;
            }

            for (int patternIndex : node->output)
            {
                result.push_back(patternIndex);
            }
        }

        return result;
    }

}  // namespace Computer

#include "Chess.h"
#include "AhoCorasick.h"


namespace Computer
{
#define BOARD_WIDTH 15
#define UNKNOWN_SCORE (10000001)
#define HASH_ITEM_INDEX_MASK (0xffff)
#define MAX_SCORE (10000000)
#define MIN_SCORE (-10000000)

    struct Position
    {
        int x;
        int y;
        int score;
        Position()
        {
        }
        Position(int x, int y)
        {
            this->x = x;
            this->y = y;
            score   = 0;
        }
        Position(int x, int y, int score)
        {
            this->x     = x;
            this->y     = y;
            this->score = score;
        }
        bool operator<(const Position& pos) const
        {
            if (score != pos.score)
            {
                return score > pos.score;
            }
            if (x != pos.x)
            {
                return x < pos.x;
            }
            else
            {
                return y < pos.y;
            }
        }
    };


    struct Pattern
    {
        std::string pattern;
        int         score;
    };


    enum class First
    {
        Empty = 0,
        Human,
        Computer
    };

    class ComputerPlayer
    {
      public:
        ComputerPlayer();
        ~ComputerPlayer();

        void       Init();
        ChessColor CheckWinner();
        void       Withdraw();

        Chess NextStep(Position pos);
        Chess NextStep(int x, int y);
        void  RePlay(First fisrt);
        Chess GetLastChess();

        void SetLevel();
        int  evaluatePoint(ChessColor board[BOARD_WIDTH][BOARD_WIDTH], Chess chess);

      private:
        std::vector<Pattern> m_Patterns;

        ChessColor         m_ChessBoard[15][15];
        std::vector<Chess> m_ChessVector;

        AhoCorasick m_AhoCorasick;
    };
}  // namespace Computer



#include "ComputerPlayer.h"
#include "Chess.h"
#include <algorithm>

namespace Computer
{



    ComputerPlayer::ComputerPlayer()
    {
        m_Patterns = {
            { "11111", 50000 }, { "011110", 4320 }, { "011100", 720 }, { "001110", 720 }, { "011010", 720 }, { "010110", 720 },
            { "11110", 720 },   { "01111", 720 },   { "11011", 720 },  { "10111", 720 },  { "11101", 720 },  { "001100", 120 },
            { "001010", 120 },  { "010100", 120 },  { "000100", 20 },  { "001000", 20 },
        };
        std::vector<std::string> patternStrs;
        for (size_t i = 0; i < m_Patterns.size(); i++)
        {
            patternStrs.push_back(m_Patterns[i].pattern);
        }
        m_AhoCorasick = AhoCorasick(patternStrs);
    }


    ComputerPlayer::~ComputerPlayer()
    {
    }

    ChessColor ComputerPlayer::CheckWinner()
    {
        return ChessColor();
    }

    void ComputerPlayer::Withdraw()
    {
    }
    Chess ComputerPlayer::NextStep(Position pos)
    {
        return Chess(0, 0, ChessColor::None, 0);
    }
    Chess ComputerPlayer::NextStep(int x, int y)
    {
        m_ChessBoard[x][y] = ChessColor::Black;
        m_ChessVector.push_back(Chess(x, y, ChessColor::Black, 0));

        Chess bestChess(-1, -1, ChessColor::None, 0);
        int   maxScore = 0;
        for (int i = 0; i < 14; ++i)
        {
            for (int j = 0; j < 14; ++j)
            {
                if (m_ChessBoard[i][j] == ChessColor::None)
                {
                    int score = evaluatePoint(m_ChessBoard, Chess(i, j, ChessColor::White, 0));
                    if (score > maxScore)
                    {
                        maxScore  = score;
                        bestChess = Chess(i, j, ChessColor::White, 0);
                    }
                }
            }
        }

        m_ChessBoard[bestChess.GetX()][bestChess.GetY()] = ChessColor::White;
        m_ChessVector.push_back(bestChess);

        return bestChess;
    }
    void ComputerPlayer::RePlay(First fisrt)
    {
    }
    Chess ComputerPlayer::GetLastChess()
    {
        return m_ChessVector.back();
    }

    void ComputerPlayer::SetLevel()
    {
    }

    int ComputerPlayer::evaluatePoint(ChessColor board[BOARD_WIDTH][BOARD_WIDTH], Chess chess)
    {
        int          pointScore;
        unsigned int i, j;

        pointScore = 0;

        std::string blackPatternStr[4];
        std::string whitePatternStr[4];

        for (i = std::max(0, (int)chess.GetX() - 5); i < (unsigned int)std::min(BOARD_WIDTH, (int)chess.GetX() + 6); ++i)
        {

            if (i != (int)chess.GetX())
            {
                blackPatternStr[0].push_back(board[i][chess.GetY()] == chess.GetColor()   ? '1'
                                             : board[i][chess.GetY()] == ChessColor::None ? '0'
                                                                                          : '2');
                whitePatternStr[0].push_back(board[i][chess.GetY()] == chess.GetColor()   ? '2'
                                             : board[i][chess.GetY()] == ChessColor::None ? '0'
                                                                                          : '1');
            }
            else
            {
                blackPatternStr[0].push_back('1');
                whitePatternStr[0].push_back('1');
            }
        }
        for (i = std::max(0, (int)chess.GetX() - 5); i < (unsigned int)std::min(BOARD_WIDTH, (int)chess.GetY() + 6); ++i)
        {
            if (i != (int)chess.GetY())
            {
                blackPatternStr[1].push_back(board[chess.GetX()][i] == chess.GetColor()   ? '1'
                                             : board[chess.GetX()][i] == ChessColor::None ? '0'
                                                                                          : '2');
                whitePatternStr[1].push_back(board[chess.GetX()][i] == chess.GetColor()   ? '2'
                                             : board[chess.GetX()][i] == ChessColor::None ? '0'
                                                                                          : '1');
            }
            else
            {
                blackPatternStr[1].push_back('1');
                whitePatternStr[1].push_back('1');
            }
        }
        for (i = (int)chess.GetX() - std::min(std::min((int)chess.GetX(), (int)chess.GetY()), 5),
            j  = (int)chess.GetY() - std::min(std::min((int)chess.GetX(), (int)chess.GetY()), 5);
             i < (unsigned int)std::min(BOARD_WIDTH, (int)chess.GetX() + 6) && j < (unsigned int)std::min(BOARD_WIDTH, (int)chess.GetY() + 6);
             i++, j++)
        {
            if (i != (int)chess.GetX())
            {
                blackPatternStr[2].push_back(board[i][j] == chess.GetColor() ? '1' : board[i][j] == ChessColor::None ? '0' : '2');
                whitePatternStr[2].push_back(board[i][j] == chess.GetColor() ? '2' : board[i][j] == ChessColor::None ? '0' : '1');
            }
            else
            {
                blackPatternStr[2].push_back('1');
                whitePatternStr[2].push_back('1');
            }
        }
        for (i = chess.GetX() + std::min(std::min((int)chess.GetY(), BOARD_WIDTH - 1 - (int)chess.GetX()), 5),
            j  = chess.GetY() - std::min(std::min((int)chess.GetY(), BOARD_WIDTH - 1 - (int)chess.GetX()), 5);
             i >= (unsigned int)std::max(0, (int)chess.GetX() - 5) && i < BOARD_WIDTH &&
             j < (unsigned int)std::min(BOARD_WIDTH, (int)chess.GetY() + 6);
             i--, j++)
        {
            if (i != chess.GetX())
            {
                blackPatternStr[3].push_back(board[i][j] == chess.GetColor() ? '1' : board[i][j] == ChessColor::None ? '0' : '2');
                whitePatternStr[3].push_back(board[i][j] == chess.GetColor() ? '2' : board[i][j] == ChessColor::None ? '0' : '1');
            }
            else
            {
                blackPatternStr[3].push_back('1');
                whitePatternStr[3].push_back('1');
            }
        }

        for (i = 0; i < 4; i++)
        {
            std::vector<int> tmp = m_AhoCorasick.search(blackPatternStr[i]);
            for (j = 0; j < tmp.size(); j++)
            {
                pointScore += m_Patterns[tmp[j]].score;
            }

            tmp = m_AhoCorasick.search(whitePatternStr[i]);
            for (j = 0; j < tmp.size(); j++)
            {
                pointScore += m_Patterns[tmp[j]].score;
            }
        }

        return pointScore;
    }

    void ComputerPlayer::Init()
    {
        for (auto& row : m_ChessBoard)
            for (auto& chess : row)
                chess = ChessColor::None;

        m_ChessVector.clear();
    }
}  // namespace Computer