[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: [kdots] /: Decision Tree into the separate class. AI is more
From: Minh Ngo <nlminhtl () gmail ! com>
Date: 2015-04-01 17:42:13
Message-ID: E1YdMeb-0005Mx-HO () scm ! kde ! org
[Download RAW message or body]
Git commit 549d14f092274b8116de15a4146b2ae9eb28501b by Minh Ngo.
Committed on 01/04/2015 at 17:41.
Pushed by minhngo into branch 'master'.
Decision Tree into the separate class. AI is more
advanced now.
M +1 -1 CMakeLists.txt
M +2 -0 plugins/simpleai/CMakeLists.txt
A +301 -0 plugins/simpleai/decisiontree.cpp [License: BSD]
C +54 -22 plugins/simpleai/decisiontree.hpp [from: polygonfinder.hpp - 050% similarity]
M +17 -234 plugins/simpleai/rival.cpp
M +0 -18 plugins/simpleai/rival.hpp
M +11 -2 polygonfinder.cpp
M +3 -3 polygonfinder.hpp
http://commits.kde.org/kdots/549d14f092274b8116de15a4146b2ae9eb28501b
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 0fb03a9..c02d239 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -118,7 +118,7 @@ KDE4_ADD_UI_FILES(SRCS ${FORMS})
KDE4_ADD_KCFG_FILES(SRCS kdots.kcfgc)
INSTALL(FILES kdots.kcfg DESTINATION ${KCFG_INSTALL_DIR})
-SET(KDOTS_VERSION "0.5.2")
+SET(KDOTS_VERSION "0.5.3")
SET(KDOTS_SOVERSION "1")
CONFIGURE_FILE(config.hpp.in config.hpp)
diff --git a/plugins/simpleai/CMakeLists.txt b/plugins/simpleai/CMakeLists.txt
index bf7510d..9ec1125 100644
--- a/plugins/simpleai/CMakeLists.txt
+++ b/plugins/simpleai/CMakeLists.txt
@@ -18,12 +18,14 @@ SET(SIMPLEAI_HEADERS
prioritymap.hpp
rival.hpp
plugin.hpp
+ decisiontree.hpp
)
SET(SIMPLEAI_SRCS
prioritymap.cpp
rival.cpp
plugin.cpp
+ decisiontree.cpp
)
kde4_add_plugin(kdots_simpleai SHARED
diff --git a/plugins/simpleai/decisiontree.cpp b/plugins/simpleai/decisiontree.cpp
new file mode 100644
index 0000000..0164b67
--- /dev/null
+++ b/plugins/simpleai/decisiontree.cpp
@@ -0,0 +1,301 @@
+/*
+ * KDots
+ * Copyright (c) 2011, 2012, 2014, 2015 Minh Ngo <minh@fedoraproject.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES(INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include "decisiontree.hpp"
+
+#include <graph.hpp>
+#include <stepqueue.hpp>
+#include <polygonfinder.hpp>
+
+#include <QRect>
+
+#include <stack>
+
+namespace KDots
+{
+namespace simpleai
+{
+ NodeInfo::NodeInfo()
+ : m_parent(-1)
+ , m_layer(0)
+ , m_bestChildGrade(0)
+ , m_capturedPointsCount(0)
+ , m_point{-1, -1}
+ {
+ }
+
+ DecisionTree::DecisionTree(const Graph& graph, const QRect& bbox,
+ int numPointsOnBoard, int depth, Owner ai)
+ : m_graph(graph)
+ , m_bbox(bbox)
+ , m_numPointsOnBoard(numPointsOnBoard)
+ , m_maxNumPoints(graph.width() * graph.height())
+ , m_depth(depth)
+ , m_ai(ai)
+ {
+ kDebug() << "Bounding box:" << bbox.width() << bbox.height();
+ }
+
+ void DecisionTree::calculateDecisions(std::vector<Point>& points, VectorF& grades)
+ {
+ m_nodes = {NodeInfo()};
+
+ // For DFS
+ std::stack<std::size_t> tasks;
+ tasks.push(0);
+
+ while (!tasks.empty())
+ {
+ const int parentNodeID = tasks.top();
+ tasks.pop();
+
+ TPreviousPoints previousPoints;
+
+ findPreviousPoints(parentNodeID, previousPoints);
+
+ std::vector<VectorB> allowedPoints(m_bbox.width(), VectorB(m_bbox.height(), false));
+ buildAllowedPointsMap(previousPoints, allowedPoints);
+
+ const std::size_t layerStart = m_nodes.size();
+
+ const int parentLayer = m_nodes[parentNodeID].m_layer;
+ const int currentLayer = parentLayer + 1;
+ const bool isHumanLayer = parentLayer % 2 == 1;
+
+ const Owner layerOwner = isHumanLayer ? StepQueue::other(m_ai) : m_ai;
+
+ const std::vector<Point>& ownerPrevPoints = isHumanLayer
+ ? previousPoints.m_human
+ : previousPoints.m_ai;
+
+ for (int x = 0; x < m_bbox.width(); ++x)
+ {
+ for (int y = 0; y < m_bbox.height(); ++y)
+ {
+ if (!allowedPoints[x][y])
+ continue;
+
+ m_nodes.emplace_back();
+
+ NodeInfo& newNode = m_nodes[m_nodes.size() - 1];
+ newNode.m_layer = currentLayer;
+ newNode.m_parent = parentNodeID;
+ newNode.m_bestChildGrade = 0;
+
+ const Point point(x + m_bbox.left(), y + m_bbox.top());
+ newNode.m_point = point;
+
+ PolygonFinder finder(m_graph, layerOwner, ownerPrevPoints);
+
+ const PolyList& polygons = finder(point);
+
+ newNode.m_capturedPointsCount = findCapturedPoints(previousPoints,
+ layerOwner,
+ polygons);
+
+ NodeInfo& parentNode = m_nodes[parentNodeID];
+ // If it's a human layer we choose the worse case
+ if (parentNode.m_bestChildGrade > newNode.m_capturedPointsCount)
+ m_nodes.pop_back();
+ else
+ parentNode.m_bestChildGrade = newNode.m_capturedPointsCount;
+ }
+ }
+
+ // Not found any elements for this layer
+ if (layerStart == m_nodes.size())
+ continue;
+
+ // Invert grades for human layers
+ if (isHumanLayer)
+ m_nodes[parentNodeID].m_bestChildGrade *= -1;
+
+ m_leafs.reserve(m_leafs.size() + m_nodes.size() - layerStart);
+
+ // Last layer
+ if (currentLayer == m_depth || (m_numPointsOnBoard + currentLayer == m_maxNumPoints))
+ {
+ for (std::size_t i = layerStart; i < m_nodes.size(); ++i)
+ m_leafs.push_back(i);
+
+ continue;
+ }
+
+ for (std::size_t i = layerStart; i < m_nodes.size(); ++i)
+ {
+ if (m_nodes[i].m_capturedPointsCount == 0)
+ tasks.push(i);
+ else
+ m_leafs.push_back(i);
+ }
+ }
+
+ // Update all weights starting from leafs
+
+ int bestGrade = 0;
+ int prevParentID = -1;
+ for (const int id : m_leafs)
+ {
+ const NodeInfo& node = m_nodes[id];
+ if (node.m_parent != prevParentID)
+ {
+ if (prevParentID != -1)
+ m_nodes[prevParentID].m_bestChildGrade += bestGrade;
+
+ bestGrade = node.m_bestChildGrade;
+ prevParentID = node.m_parent;
+ continue;
+ }
+
+ if (prevParentID % 2 == 0) // Current is max/ai layer
+ {
+ if (bestGrade < node.m_bestChildGrade)
+ bestGrade = node.m_bestChildGrade;
+ }
+ else // Current is min/human layer
+ {
+ if (bestGrade > node.m_bestChildGrade)
+ bestGrade = node.m_bestChildGrade;
+ }
+ }
+
+ kDebug() << "Decision Tree Final Size:" << m_nodes.size();
+
+ // Decisions are positioned in the first layer
+ // TODO: reserve
+ for (int i = 1; m_nodes[i].m_parent == 0; ++i)
+ {
+ points.push_back(m_nodes[i].m_point);
+ grades.push_back(m_nodes[i].m_bestChildGrade);
+ }
+ }
+
+ void DecisionTree::findPreviousPoints(int lastPointID,
+ TPreviousPoints& previousPoints) const
+ {
+ const NodeInfo *lastNode = &m_nodes[lastPointID];
+
+ while(lastNode->m_point.m_x != -1)
+ {
+ if (lastNode->m_layer % 2 == 1)
+ previousPoints.m_ai.push_back(lastNode->m_point);
+ else
+ previousPoints.m_human.push_back(lastNode->m_point);
+
+ lastNode = &m_nodes[lastNode->m_parent];
+ }
+ }
+
+ namespace
+ {
+ bool isNotIn(const std::vector<Point>& v, const Point& point)
+ {
+ for (const Point& p : v)
+ if (p == point)
+ return false;
+
+ return true;
+ }
+ }
+
+ int DecisionTree::findCapturedPoints(const TPreviousPoints& previousPoints,
+ Owner currentOwner,
+ const PolyList& polygons) const
+ {
+ if (polygons.empty())
+ return 0;
+
+ int numPoints = 0;
+
+ const std::vector<Point>& opponentPrevPoints = currentOwner == m_ai
+ ? previousPoints.m_human
+ : previousPoints.m_ai;
+
+ for (int x = m_bbox.left(); x <= m_bbox.right(); ++x)
+ {
+ for (int y = m_bbox.top(); y <= m_bbox.bottom(); ++y)
+ {
+ const Point point(x, y);
+
+ // We can capture only noncaptured points
+ if (m_graph[point].isCaptured())
+ continue;
+
+ const Owner pointOwner = m_graph[point].owner();
+
+ // We can capture only oponent's points
+ if (pointOwner == currentOwner)
+ continue;
+
+ if (pointOwner == Owner::NONE && isNotIn(opponentPrevPoints, point))
+ continue;
+
+ for (const Polygon_ptr& polygon : polygons)
+ {
+ if (polygon->contains(point))
+ {
+ ++numPoints;
+ break;
+ }
+ }
+ }
+ }
+
+ return numPoints;
+ }
+
+ namespace
+ {
+ bool isNotPreviousPoint(const TPreviousPoints& previousPoints, const Point& point)
+ {
+ for (const Point& pai : previousPoints.m_ai)
+ if (pai == point)
+ return false;
+
+ for (const Point& phuman : previousPoints.m_human)
+ if (phuman == point)
+ return false;
+
+ return true;
+ }
+ }
+
+ void DecisionTree::buildAllowedPointsMap(const TPreviousPoints& previousPoints,
+ std::vector<VectorB>& allowedPoints) const
+ {
+ for (int x = 0; x < m_bbox.width(); ++x)
+ {
+ for (int y = 0; y < m_bbox.height(); ++y)
+ {
+ const Point point(x + m_bbox.left(), y + m_bbox.top());
+
+ allowedPoints[x][y] = isNotPreviousPoint(previousPoints, point)
+ && m_graph[point].owner() == Owner::NONE
+ && !m_graph[point].isCaptured();
+ }
+ }
+ }
+}
+}
\ No newline at end of file
diff --git a/polygonfinder.hpp b/plugins/simpleai/decisiontree.hpp
similarity index 50%
copy from polygonfinder.hpp
copy to plugins/simpleai/decisiontree.hpp
index 79e67f2..395ba24 100644
--- a/polygonfinder.hpp
+++ b/plugins/simpleai/decisiontree.hpp
@@ -24,36 +24,68 @@
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#pragma once
-#include <memory>
-#include <list>
-#include <unordered_set>
-#include "polygon.hpp"
-#include "constants.hpp"
+#include <point.hpp>
+#include <polygon.hpp>
+#include <constants.hpp>
+
+class QRect;
namespace KDots
{
- struct Graph;
+class Graph;
+namespace simpleai
+{
+ struct NodeInfo
+ {
+ NodeInfo();
+
+ int m_parent; // Index from the vector
+ int m_layer;
+ int m_bestChildGrade;
+ int m_capturedPointsCount;
- class KDOTS_EXPORT PolygonFinder final
+ Point m_point;
+ };
+
+ struct TPreviousPoints
+ {
+ std::vector<Point> m_ai;
+ std::vector<Point> m_human;
+ };
+
+ typedef std::vector<float> VectorF;
+
+ class DecisionTree
{
public:
- PolygonFinder(const Graph& graph, Owner owner,
- const std::unordered_set<Point>& additionalPoints = std::unordered_set<Point>());
-
- // O(n)
- const PolyList& operator()(const Point& point);
-
+ DecisionTree(const Graph& graph, const QRect& bbox,
+ int numPointsOnBoard, int depth, Owner ai);
+
+ void calculateDecisions(std::vector<Point>& points, VectorF& grades);
+
private:
- void findPolygons(const Point& point);
-
+ void findPreviousPoints(int lastPointID,
+ TPreviousPoints& previousPoints) const;
+
+ int findCapturedPoints(const TPreviousPoints& previousPoints,
+ Owner current,
+ const PolyList& polygons) const;
+
+ typedef std::vector<bool> VectorB;
+ // Returns allowed points to place (not to capture)
+ void buildAllowedPointsMap(const TPreviousPoints& previousPoints,
+ std::vector<VectorB>& allowedPoints) const;
+
private:
const Graph& m_graph;
- Owner m_current;
- std::vector<std::vector<bool>> m_stepMap;
- const std::unordered_set<Point> m_additionalPoints;
-
- std::vector<Point> m_cache;
- PolyList m_polygons;
- Point m_first;
+ const QRect& m_bbox;
+ const int m_numPointsOnBoard;
+ const int m_maxNumPoints;
+ const int m_depth;
+ Owner m_ai;
+
+ std::vector<NodeInfo> m_nodes;
+ std::vector<int> m_leafs;
};
+}
}
\ No newline at end of file
diff --git a/plugins/simpleai/rival.cpp b/plugins/simpleai/rival.cpp
index 6400204..700ff29 100644
--- a/plugins/simpleai/rival.cpp
+++ b/plugins/simpleai/rival.cpp
@@ -25,6 +25,7 @@
*/
#include "rival.hpp"
#include "prioritymap.hpp"
+#include "decisiontree.hpp"
#include <boardmodel.hpp>
#include <constants.hpp>
@@ -34,6 +35,7 @@
#include <stepqueue.hpp>
#include <stack>
+#include <ctime>
#include <KDebug>
#include <KgDifficulty>
@@ -46,8 +48,8 @@ namespace KDots
{
const std::map<KgDifficultyLevel::StandardLevel, int> DIFFICULTY_TO_DEPTH = {
{KgDifficultyLevel::Easy, 2},
- {KgDifficultyLevel::Medium, 4},
- {KgDifficultyLevel::Hard, 6}
+ {KgDifficultyLevel::Medium, 3},
+ {KgDifficultyLevel::Hard, 4}
};
}
@@ -153,11 +155,9 @@ namespace KDots
return maxPriority;
};
- kDebug() << "BB size:" << bb.width() << bb.height();
std::vector<VectorF> importanceMatrix(bb.width(), VectorF(bb.height()));
const QPoint& offsetPoint = bb.topLeft();
- kDebug() << "Offset:" << offsetPoint;
for (int x = 0; x < bb.width(); ++x)
{
for (int y = 0; y < bb.height(); ++y)
@@ -165,12 +165,7 @@ namespace KDots
if (graph[x + offsetPoint.x()][y + offsetPoint.y()].owner() != Owner::NONE)
importanceMatrix[x][y] = -std::numeric_limits<float>::infinity();
else
- {
importanceMatrix[x][y] = cellPriority({offsetPoint.x() + x, offsetPoint.y() + y});
- kDebug() << "(" << (offsetPoint.x() + x)
- << "," << (offsetPoint.y() + y)
- << ")" << importanceMatrix[x][y];
- }
}
}
@@ -216,78 +211,6 @@ namespace KDots
return QRect(QPoint(min_x, min_y), QPoint(max_x, max_y));
}
- void Rival::findCapturedPoints(const QRect& bbox,
- const std::vector<VectorB>& allowedPoints,
- const PolyList& polygons,
- std::unordered_set<Point>& capturedPoints) const
- {
- if (polygons.empty())
- return;
-
- for (int x = bbox.left(); x <= bbox.right(); ++x)
- {
- for (int y = bbox.top(); y <= bbox.bottom(); ++y)
- {
- if (!allowedPoints[x - bbox.left()][y - bbox.top()])
- continue;
-
- const Point point(x, y);
- for (const Polygon_ptr& polygon : polygons)
- {
- if (polygon->contains(point))
- {
- capturedPoints.insert(point);
- break;
- }
- }
- }
- }
- }
-
- struct NodeInfo
- {
- int m_parent; // Index from the vector
- int m_layer;
- int m_bestChildGrade;
- int m_capturedPointsCount;
-
- Point m_point;
- std::unordered_set<Point> m_capturedPoints;
- };
-
- void Rival::findPreviousPoints(const std::vector<NodeInfo>& decisionTree,
- int lastPointID,
- std::unordered_set<Point>& previousPoints,
- std::unordered_set<Point>& capturedPoints) const
- {
- const NodeInfo *lastNode = &decisionTree[lastPointID];
- //kDebug() << "Last node: {" << lastNode->m_point.m_x << "," << lastNode->m_point.m_y << "}";
- while (lastNode->m_point.m_x != -1)
- {
- previousPoints.insert(lastNode->m_point);
- const std::unordered_set<Point>& lastCapturedPoints = lastNode->m_capturedPoints;
- capturedPoints.insert(lastCapturedPoints.begin(), lastCapturedPoints.end());
- lastNode = &decisionTree[lastNode->m_parent];
- }
- }
-
- void Rival::buildAllowedPointsMap(const QRect& bbox,
- const std::unordered_set<Point>& previousPoints,
- std::vector<VectorB>& allowedPoints) const
- {
- const Graph& graph = m_board->graph();
- for (int x = 0; x < bbox.width(); ++x)
- {
- for (int y = 0; y < bbox.height(); ++y)
- {
- const Point point(x + bbox.left(), y + bbox.top());
- allowedPoints[x][y] = !previousPoints.count(point)
- && graph[point].owner() == Owner::NONE
- && !graph[point].isCaptured();
- }
- }
- }
-
void Rival::addPoint(bool random)
{
if (random)
@@ -298,150 +221,30 @@ namespace KDots
const QRect bbox(getBoundingBox());
- // For other elements importance is 0
- const auto importanceMatrix(getImportanceMatrix(bbox));
-
- std::vector<NodeInfo> decisionTree(1);
-
- {
- NodeInfo& baseNode = decisionTree.back();
- baseNode.m_parent = -1;
- baseNode.m_bestChildGrade = 0;
- baseNode.m_layer = 0;
-
- baseNode.m_capturedPointsCount = 0;
-
- baseNode.m_point = {-1, -1};
- }
-
- std::stack<std::size_t> tasks;
- tasks.push(0);
-
const Graph& graph = m_board->graph();
-
- const int begin = time(0);
- while (!tasks.empty())
- {
- const int parentNodeID = tasks.top();
- tasks.pop();
-
- std::unordered_set<Point> previousPoints;
- std::unordered_set<Point> capturedPoints;
-
- findPreviousPoints(decisionTree, parentNodeID,
- previousPoints, capturedPoints);
-
- std::vector<VectorB> allowedPoints(bbox.width(), VectorB(bbox.height(), false));
- buildAllowedPointsMap(bbox, previousPoints, allowedPoints);
-
- const std::size_t layerStart = decisionTree.size();
-
- for (int x = 0; x < bbox.width(); ++x)
- {
- for (int y = 0; y < bbox.height(); ++y)
- {
- if (!allowedPoints[x][y])
- continue;
-
- decisionTree.emplace_back();
-
- const int newNodeID = decisionTree.size() - 1;
- NodeInfo& newNode = decisionTree[newNodeID];
- NodeInfo& parentNode = decisionTree[parentNodeID];
-
- newNode.m_layer = parentNode.m_layer + 1;
- newNode.m_parent = parentNodeID;
- newNode.m_bestChildGrade = 0;
-
- const Point point(x + bbox.left(), y + bbox.top());
- newNode.m_point = point;
-
- PolygonFinder finder(graph,
- parentNode.m_layer % 2 == 0 ? m_ai : m_human,
- previousPoints);
-
- const PolyList& polygons = finder(point);
-
- findCapturedPoints(bbox,
- allowedPoints,
- polygons,
- newNode.m_capturedPoints);
-
- newNode.m_capturedPointsCount = newNode.m_capturedPoints.size();
- if (parentNode.m_bestChildGrade > newNode.m_capturedPointsCount)
- decisionTree.pop_back();
- else
- parentNode.m_bestChildGrade = newNode.m_capturedPointsCount;
- }
- }
-
- if (layerStart == decisionTree.size())
- continue;
-
- NodeInfo& parentNode = decisionTree[parentNodeID];
-
- if (parentNode.m_layer % 2 == 1) // Human layer
- // Invert grades for human layers
- decisionTree[parentNodeID].m_bestChildGrade *= -1;
-
- // Last layer
- if (parentNode.m_layer + 1 == m_depth)
- continue;
-
- for (std::size_t i = layerStart; i < decisionTree.size(); ++i)
- {
- if (decisionTree[i].m_capturedPointsCount == parentNode.m_bestChildGrade)
- tasks.push(i);
- }
- }
-
- int bestGrade = 0;
- int prevParentID = -1;
- for (auto it = decisionTree.rbegin(), end = --decisionTree.rend(); it != end; ++it)
- {
- if (it->m_parent != prevParentID)
- {
- if (prevParentID != -1)
- decisionTree[prevParentID].m_bestChildGrade += bestGrade;
-
- bestGrade = it->m_bestChildGrade;
- prevParentID = it->m_parent;
- continue;
- }
-
- if (prevParentID % 2 == 0) // Current is max/ai layer
- {
- if (bestGrade < it->m_bestChildGrade)
- bestGrade = it->m_bestChildGrade;
- }
- else // Current is min/human layer
- {
- if (bestGrade > it->m_bestChildGrade)
- bestGrade = it->m_bestChildGrade;
- }
- }
-
- kDebug() << "Best grade (Decision tree): " << bestGrade;
- kDebug() << "Decision Tree Final Size:" << decisionTree.size();
-
+
+ const int pointsOnBoard = m_board->stepQueue().getAllPoints().size();
+
+ DecisionTree tree(graph, bbox, pointsOnBoard, m_depth, m_ai);
+
std::vector<Point> decisions;
std::vector<float> decisionGrades;
- for (int i = 1; decisionTree[i].m_parent == 0; ++i)
+
{
- decisions.push_back(decisionTree[i].m_point);
- decisionGrades.push_back(decisionTree[i].m_bestChildGrade * m_k2);
- kDebug() << decisionTree[i].m_point.m_x << ", " << decisionTree[i].m_point.m_y
- << ":" << decisionTree[i].m_bestChildGrade * m_k2;
+ const int begin = std::time(0);
+ tree.calculateDecisions(decisions, decisionGrades);
+ kDebug() << "Decision making time:" << (std::time(0) - begin);
}
-
+
kDebug() << "Number of decisions founded:" << decisions.size();
if (!decisions.empty())
{
+ const auto importanceMatrix(getImportanceMatrix(bbox));
for (std::size_t i = 0; i < decisions.size(); ++i)
{
const Point& p = decisions[i];
-
+ decisionGrades[i] *= m_k2;
decisionGrades[i] += m_k1 * importanceMatrix[p.m_x - bbox.left()][p.m_y - bbox.top()];
}
@@ -449,28 +252,8 @@ namespace KDots
std::max_element(decisionGrades.begin(),
decisionGrades.end()));
emit needAddPoint(decisions[pointID]);
-
- kDebug() << "Decision making time:" << (time(0) - begin);
- }
- else // Last points, doesn't matter a lot so :)
- {
- kDebug() << "Empty decisions";
- kDebug() << bbox.left() << bbox.right();
- kDebug() << bbox.top() << bbox.bottom();
- for (int x = bbox.left(); x <= bbox.right(); ++x)
- {
- for (int y = bbox.top(); y <= bbox.bottom(); ++y)
- {
- const Point point(x, y);
- if (graph[point].owner() == Owner::NONE && !graph[point].isCaptured())
- {
- kDebug() << "Add point:" << point.m_x << point.m_y;
- emit needAddPoint(point);
- return;
- }
- }
- }
}
+ // Else -> End of the game
}
void Rival::setBoardModel(BoardModel *board)
diff --git a/plugins/simpleai/rival.hpp b/plugins/simpleai/rival.hpp
index 9fa2d6a..7c85b77 100644
--- a/plugins/simpleai/rival.hpp
+++ b/plugins/simpleai/rival.hpp
@@ -28,7 +28,6 @@
#include <polygon.hpp>
-#include <unordered_set>
#include <QRect>
namespace KDots
@@ -60,26 +59,9 @@ namespace KDots
QRect getBoundingBox() const;
typedef std::vector<float> VectorF;
- typedef std::vector<bool> VectorB;
// Complexity O(n)
std::vector<VectorF> getImportanceMatrix(const QRect& bb) const;
- void buildAllowedPointsMap(const QRect& bbox,
- const std::unordered_set<Point>& previousPoints,
- std::vector<VectorB>& allowedPoints) const;
-
- // Complexity O(n)
- void findCapturedPoints(const QRect& bbox,
- const std::vector<VectorB>& allowerdPoints,
- const PolyList& polygons,
- std::unordered_set<Point>& capturedPoints) const;
-
- // Complexity O(1)
- void findPreviousPoints(const std::vector<NodeInfo>& decisionTree,
- int lastPointID,
- std::unordered_set<Point>& previousPoints,
- std::unordered_set<Point>& capturedPoints) const;
-
signals:
void needCreateBoard(const GameConfig& config);
void needDestroy();
diff --git a/polygonfinder.cpp b/polygonfinder.cpp
index 7ab766c..5a14262 100644
--- a/polygonfinder.cpp
+++ b/polygonfinder.cpp
@@ -32,7 +32,7 @@
namespace KDots
{
PolygonFinder::PolygonFinder(const Graph& graph, Owner owner,
- const std::unordered_set<Point>& additionalPoints)
+ const std::vector<Point>& additionalPoints)
: m_graph(graph)
, m_current(owner)
, m_stepMap(graph.width(), std::vector<bool>(graph.height(), false))
@@ -72,6 +72,15 @@ namespace KDots
return m_polygons;
}
+
+ bool PolygonFinder::isAdditionalPoint(const Point& point) const
+ {
+ for (const Point& pi : m_additionalPoints)
+ if (pi == point)
+ return true;
+
+ return false;
+ }
namespace
{
@@ -110,7 +119,7 @@ namespace KDots
const GraphPoint& graphPoint = m_graph[newPoint];
- if (!m_additionalPoints.count(newPoint) && newPoint != m_first
+ if (!isAdditionalPoint(newPoint) && newPoint != m_first
&& (graphPoint.isCaptured() || graphPoint.owner() != m_current))
continue;
diff --git a/polygonfinder.hpp b/polygonfinder.hpp
index 79e67f2..3af8266 100644
--- a/polygonfinder.hpp
+++ b/polygonfinder.hpp
@@ -33,24 +33,24 @@
namespace KDots
{
struct Graph;
-
class KDOTS_EXPORT PolygonFinder final
{
public:
PolygonFinder(const Graph& graph, Owner owner,
- const std::unordered_set<Point>& additionalPoints = std::unordered_set<Point>());
+ const std::vector<Point>& additionalPoints = {});
// O(n)
const PolyList& operator()(const Point& point);
private:
void findPolygons(const Point& point);
+ bool isAdditionalPoint(const Point& point) const;
private:
const Graph& m_graph;
Owner m_current;
std::vector<std::vector<bool>> m_stepMap;
- const std::unordered_set<Point> m_additionalPoints;
+ const std::vector<Point>& m_additionalPoints;
std::vector<Point> m_cache;
PolyList m_polygons;
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic