API tools faq
paste
JadonChan

Strategy.cpp

JadonChan
May 31st, 2024
76
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.33 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <unistd.h>
  3. #include <chrono>
  4. #include <ctime>
  5. #include "Point.h"
  6. #include "Strategy.h"
  7. #include <cmath>
  8. #include "Judge.h"
  9.  
  10. using namespace std;
  11.  
  12. /*
  13.     策略函数接口,该函数被对抗平台调用,每次传入当前状态,要求输出你的落子点,该落子点必须是一个符合游戏规则的落子点,不然对抗平台会直接认为你的程序有误
  14.    
  15.     input:
  16.         为了防止对对抗平台维护的数据造成更改，所有传入的参数均为const属性
  17.         M, N : 棋盘大小 M - 行数 N - 列数 均从0开始计， 左上角为坐标原点，行用x标记，列用y标记
  18.         top : 当前棋盘每一列列顶的实际位置. e.g. 第i列为空,则_top[i] == M, 第i列已满,则_top[i] == 0
  19.         _board : 棋盘的一维数组表示, 为了方便使用，在该函数刚开始处，我们已经将其转化为了二维数组board
  20.                 你只需直接使用board即可，左上角为坐标原点，数组从[0][0]开始计(不是[1][1])
  21.                 board[x][y]表示第x行、第y列的点(从0开始计)
  22.                 board[x][y] == 0/1/2 分别对应(x,y)处 无落子/有用户的子/有程序的子,不可落子点处的值也为0
  23.         lastX, lastY : 对方上一次落子的位置, 你可能不需要该参数，也可能需要的不仅仅是对方一步的
  24.                 落子位置，这时你可以在自己的程序中记录对方连续多步的落子位置，这完全取决于你自己的策略
  25.         noX, noY : 棋盘上的不可落子点(注:涫嫡饫锔?龅膖op已经替你处理了不可落子点，也就是说如果某一步
  26.                 所落的子的上面恰是不可落子点，那么UI工程中的代码就已经将该列的top值又进行了一次减一操作，
  27.                 所以在你的代码中也可以根本不使用noX和noY这两个参数，完全认为top数组就是当前每列的顶部即可,
  28.                 当然如果你想使用lastX,lastY参数，有可能就要同时考虑noX和noY了)
  29.         以上参数实际上包含了当前状态(M N _top _board)以及历史信息(lastX lastY),你要做的就是在这些信息下给出尽可能明智的落子点
  30.     output:
  31.         你的落子点Point
  32. */
  33.  
  34. int **myBoard;
  35. int *myTop;
  36. int numTop;
  37. int boardM;
  38. int boardN;
  39. bool myTurn;
  40. std::clock_t startTime;
  41.  
  42. class MonteCarloNode {
  43. public:
  44.     MonteCarloNode *bestChild();
  45.     MonteCarloNode() {
  46.         accessTime = 0;
  47.         winTime = 0;
  48.         numChildren = 0;
  49.         parent = nullptr;
  50.         point = Point(-1, -1);
  51.     }
  52.     MonteCarloNode(int numChildren, bool userTurn): numChildren(numChildren), userTurn(userTurn) {}
  53.     ~MonteCarloNode() { }
  54.     void expand();
  55.     void merge();
  56.     int search_for_optimal();
  57.     int accessTime = 0;
  58.     int winTime = 0;
  59.     int numChildren = 0;
  60.     bool userTurn = false;
  61.     bool isLeaf = false;
  62.     bool win = false;
  63.     MonteCarloNode *children[12] = {};
  64.     MonteCarloNode *parent = nullptr;      
  65.     Point point = Point(-1, -1);   
  66.     double value();
  67.     void update(bool win);
  68.     void updateAll(bool win);
  69. };
  70.  
  71. MonteCarloNode *root;
  72.  
  73. extern "C" Point *getPoint(const int M, const int N, const int *top, const int *_board,
  74.                            const int lastX, const int lastY, const int noX, const int noY)
  75. {
  76.     /*
  77.         不要更改这段代码
  78.     */
  79.     startTime = std::clock();  
  80.  
  81.     int x = -1, y = -1; //最终将你的落子点存到x,y中
  82.     int **board = new int *[M];
  83.     for (int i = 0; i < M; i++)
  84.     {
  85.         board[i] = new int[N];
  86.         for (int j = 0; j < N; j++)
  87.         {
  88.             board[i][j] = _board[i * N + j];
  89.         }
  90.     }
  91.  
  92.     /*
  93.         根据你自己的策略来返回落子点,也就是根据你的策略完成对x,y的赋值
  94.         该部分对参数使用没有限制，为了方便实现，你可以定义自己新的类、.h文件、.cpp文件
  95.     */
  96.     //Add your own code below
  97.  
  98.     //a naive example
  99.     // for (int i = N-1; i >= 0; i--) {
  100.     //  if (top[i] > 0) {
  101.     //      x = top[i] - 1;
  102.     //      y = i;
  103.     //      break;
  104.     //  }
  105.     // }
  106.  
  107.     boardM = M;
  108.     boardN = N;
  109.     myBoard = new int *[M];
  110.     for (int i = 0; i < M; i++) {
  111.         myBoard[i] = new int[N];
  112.     }
  113.     myTop = new int[N];
  114.     build(board, top);
  115.     // root->show(0, 1);
  116.     x = root->bestChild()->point.x;
  117.     y = root->bestChild()->point.y;
  118.     // delete root;
  119.  
  120.     /*
  121.         不要更改这段代码
  122.     */
  123.     clearArray(M, N, board);
  124.     return new Point(x, y);
  125. }
  126.  
  127. /*
  128.     getPoint函数返回的Point指针是在本so模块中声明的，为避免产生堆错误，应在外部调用本so中的
  129.     函数来释放空间，而不应该在外部直接delete
  130. */
  131. extern "C" void clearPoint(Point *p)
  132. {
  133.     delete p;
  134.     return;
  135. }
  136.  
  137. /*
  138.     清除top和board数组
  139. */
  140. void clearArray(int M, int N, int **board)
  141. {
  142.     for (int i = 0; i < M; i++)
  143.     {
  144.         delete[] board[i];
  145.     }
  146.     delete[] board;
  147. }
  148.  
  149. /*
  150.     添加你自己的辅助函数，你可以声明自己的类、函数，添加新的.h .cpp文件来辅助实现你的想法
  151. */
  152.  
  153.  
  154. double MonteCarloNode::value() {
  155.     int coef = userTurn ? 1 : -1;
  156.     return coef * winTime / double(accessTime + 1) + VALUEC * sqrt(log(parent->accessTime) / (accessTime + 1));
  157. }
  158.  
  159. MonteCarloNode *MonteCarloNode::bestChild() {
  160.     int bestIndex = 0;
  161.     double bestValue = -2;
  162.     for(int i = 0; i < numChildren; i++) {
  163.         if (children[i] && children[i]->value() > bestValue) {
  164.             bestValue = children[i]->value();
  165.             bestIndex = i;
  166.         }
  167.         if (!children[i]) {
  168.             return children[i];
  169.         }
  170.     }
  171.     return children[bestIndex];
  172. }
  173.  
  174. void step(int x, int y) {
  175.     myBoard[x][y] = CHESS(myTurn);
  176.     myTop[y]--;
  177.     if (myTop[y] == 0) {
  178.         numTop--;
  179.     }
  180.     myTurn = !myTurn;
  181. }
  182.  
  183. int topOfN(int n) {
  184.     int ret = -1;
  185.     for (int j = 0; j < boardN; j++) {
  186.         if (myTop[j] > 0) {
  187.             if (n == 0) {
  188.                 ret = j;
  189.             }
  190.             n--;
  191.         }
  192.     }
  193.     return ret;
  194. }
  195.  
  196. int check(int x, int y) {
  197.     if (!myTurn) {
  198.         if (userWin(x, y, boardM, boardN, myBoard)) {
  199.             return 1; // user win
  200.         }
  201.     }
  202.     else {
  203.         if (machineWin(x, y, boardM, boardN, myBoard)) {
  204.             return 2; // machine win
  205.         }
  206.     }
  207.     if (isTie(boardN, myTop)) {
  208.         return 3; // tie
  209.     }
  210.     return 0; // continue
  211. }
  212.  
  213. int randomPick() {
  214.     int i = rand() % numTop;
  215.     int order = topOfN(i);
  216.     step(myTop[order]-1, order);
  217.     return check(myTop[order], order);
  218. }
  219.  
  220. bool randomPlay() {
  221.     int result;    
  222.     while (!(result = randomPick()));
  223.     if (result == 1) {
  224.         return true;
  225.     }
  226.     else {
  227.         return false;
  228.     }
  229. }
  230.  
  231. void resetMyBoard(const int *const *board) {
  232.     for (int i = 0; i < boardM; i++)
  233.     {
  234.         for (int j = 0; j < boardN; j++)
  235.         {
  236.             myBoard[i][j] = board[i][j];
  237.         }
  238.     }
  239. }
  240.  
  241. void resetMyTop(const int *top) {
  242.     int n = 0;
  243.     for (int i = 0; i < boardN; i++) {
  244.         myTop[i] = top[i];
  245.         if (top[i] > 0) {
  246.             n++;
  247.         }
  248.     }
  249.     numTop = n;
  250. }
  251.  
  252. int numPath(const int *top) {
  253.     int ret = 0;
  254.     for (int i = 0; i < boardN; i++) {
  255.         if (top[i] > 0)
  256.             ret++;
  257.     }
  258.     return ret;
  259. }
  260.  
  261. void MonteCarloNode::update(bool win) {
  262.     accessTime++;
  263.     if (win) {
  264.         winTime++;
  265.     }
  266. }
  267.  
  268. void MonteCarloNode::updateAll(bool win) {
  269.     MonteCarloNode *node = this;
  270.     while(node) {
  271.         node->update(win);
  272.         node = node->parent;
  273.     }
  274. }
  275.  
  276. void MonteCarloNode::expand() {
  277.     int order = 0;
  278.     while (order < numChildren) {
  279.         if (!children[order]) {
  280.             break;
  281.         }
  282.         order++;
  283.     }
  284.     int y = topOfN(order);
  285.     int x = myTop[y] - 1;
  286.     step(x, y);
  287.     children[order] = new MonteCarloNode(numTop, myTurn);
  288.     children[order]->point = Point(x, y);
  289.     children[order]->parent = this;
  290.     int result = check(x, y);
  291.     if (result) {
  292.         updateAll(result == 1);
  293.         return;
  294.     }
  295.     bool win = randomPlay();
  296.     updateAll(win);
  297.     if (numTop == 0) {
  298.         children[order]->isLeaf = true;
  299.     }
  300. }
  301.  
  302. void MonteCarloNode::merge() {
  303.     int numWin = 0;
  304.     int numLeaf = 0;
  305.     for (int i = 0; i < numChildren; i++) {
  306.         if (children[i] && children[i]->isLeaf) {
  307.             numLeaf++;
  308.             if (children[i]->win) {
  309.                 numWin++;
  310.             }
  311.         }
  312.     }
  313.     if (numLeaf == numChildren && numWin == numChildren) {
  314.         win = true;
  315.         isLeaf = true;
  316.     }
  317.     else if (numLeaf == numChildren && numWin == 0) {
  318.         win = false;
  319.         isLeaf = true;
  320.     }
  321. }
  322.  
  323. void build(const int *const *board, const int *top) {
  324.     int numChildrenOfRoot = numPath(top);  
  325.     root = new MonteCarloNode(numChildrenOfRoot, myTurn);
  326.     MonteCarloNode *node;
  327.     while (true) {
  328.         std::clock_t now = std::clock();
  329.         if ((now - startTime) > 2.8 * CLOCKS_PER_SEC) {
  330.             break;
  331.         }
  332.         resetMyBoard(board);
  333.         resetMyTop(top);
  334.         node = root;
  335.         while (node->bestChild() && !node->isLeaf) {
  336.             node = node->bestChild();
  337.             if (node->point.x > 0 && node->point.y > 0) {
  338.                 step(node->point.x, node->point.y);
  339.             }
  340.         }
  341.         if (node->isLeaf) {
  342.             node->updateAll(node->win);
  343.         }
  344.         else {
  345.             node->expand();
  346.             node->merge();
  347.         }
  348.     }
  349. }
  350.  
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!