calcitem / chaosclock Goto Github PK

1.0 1.0 1.0 332 KB

C++ implementation of the "Chaos Clock" game invented by ejsoon, related information: https://quanquan.space/viewtopic.php?t=852

Home Page: https://ejsoon.win/chaosclock/

C++ 56.13% Makefile 43.87%

chaosclock's Introduction

Hi there 👋

We are located in Canton, China 🌆

🔭 We are currently working part time on our open source.
💬 Ask us about Flutter and AI.
📫 You can reach us on Twitter

Open Source Projects

Github Stats

chaosclock's People

Contributors

Stargazers

Watchers

Forkers

ejmoog

chaosclock's Issues

代碼報錯，未找到原因

struct Position2
{
	uint64_t board = 0;
    vector<Position2 *> children; // 24 Bytes
};

Position2 getValue2(string pos_start)
{
    Position2 *new_position;
	cout << "why?: ";
    new_position->board = 12;
	cout << "not?: ";
return *new_position;
}

以上這段代碼報錯：
Segmentation fault (core dumped)

一直未能找到原因。

第250行的alloc.allocate(1)是否起作用？

Position *new_position = alloc.allocate(1);

這個我沒能理解，感覺不初始化也行？

【重大改進】改變了哈希map格式，使棋能走下去

之前的哈希查詢和賦值，都是對一個uint64賦值。其缺點是，棋走不下去。

例如第五頁的局面「9,10,8,1,4,7,11,6,5,3,12,2」，movelist 1 7 5 3之後就沒有選項了，只給一個評分。

現改為vector指針，即

// uint64_t *board_map = new uint64_t[1ll << 24];
vector<Position*>board_map(1ll << 24);

Position *getBoardMap(Position *pos)
void setBoardMap(Position *pos)
也作相應改動。之後再走「1 7 5 3 」，就可以接著走下去，而不是只給個評分。

代碼上傳地址。

将数据预取到高速缓存中以提高程序性能

gcc 中的 __builtin_prefetch 内置函数可以在代码中使用，用于将数据预取到高速缓存中，以提高程序性能。

预取是指在实际需要使用数据之前，将该数据从主存取到缓存中。这样，当程序需要使用该数据时，可以直接从高速缓存中读取，而不需要等待从主存中读取，从而提高了程序的效率。

使用 __builtin_prefetch 函数可以在代码中指定哪些数据需要预取，并在需要使用该数据之前进行预取操作。__builtin_prefetch 函数的语法如下：

void __builtin_prefetch (const void *addr, int rw, int locality);

其中，addr 表示需要预取的数据的地址，rw 表示访问模式，取值可以是 0（表示预取不会修改该地址的值）或者 1（表示预取会修改该地址的值），locality 表示预取的局部性，取值可以是 0（表示预取的数据可能不会使用）到 3（表示预取的数据会被频繁使用）。

以下是一个使用 __builtin_prefetch 函数的示例：

void foo(const int* data, int n) {
  for (int i = 0; i < n; i++) {
    __builtin_prefetch(&data[i+16], 0, 3);
    // ...
  }
}

上述代码中，__builtin_prefetch 函数将 data[i+16] 数据预取到缓存中，并设置局部性为 3，表示该数据会被频繁使用。这样，在 for 循环中需要使用 data[i+16] 数据时，该数据已经被预取到缓存中，可以直接从缓存中读取，提高了程序的性能。

需要注意的是，使用 __builtin_prefetch 函数可能会带来一些额外的开销，因此应该根据具体情况进行评估和测试，以确保使用 __builtin_prefetch 函数确实可以提高程序性能。

準備用位運算/二進制重寫一個

所有函數都要重寫。直接不需要「影子數據」了，一個uint64_t包含了：

board：6byte
player：1bit
value：3bit
lastmove：1byte

要學一下加減乘除與位運算的轉換。

目前的疑問是，當某棋子從某地方經過12點鐘的位置，那它停止的位置是(c_pos + c)%12，這個求模是否應轉換為位運算？或者用三元運算符？c_pos + c > 12 ? c_pos + c - 12 : c_pos + c;

是三元效率高，還是求模效率高？還是說還有另一種位運算？

什么情况下需要 sortChildren？

sortChildren這個函數似乎用處不大？所以现在先移除了。

之後把下面的幾個_children改成children。

這個是改變children滾的次序（以提高效率），但是假設我們是希望所有可能都走完的話，這個倒只是降低效率？

如后面优化之后，又需要排序了？

待查。

rollsum遞歸次數统计

除了ms之外，或許可以加上「rollsum遞歸次數」？如果有減少的話。當能夠排除重覆局面，遞歸次數就可以減少很多。

缩减内存占用

基于 chaosclock2-1.cpp 做了一个对象池，参见 00f4f80

使用对象池技术来避免频繁调用 new 分配内存，在程序开始时预先创建一些 Position 对象，放入一个池中，需要使用 Position 对象时，从池中获取一个空闲的对象，使用完毕后再将其归还到池中，以便下次重用。

使用对象池可以显著减少内存分配和回收的次数，提高程序的性能。同时，需要注意池的大小，以免占用过多内存，也要注意在使用完毕后及时归还对象，以便其他地方重用。

优化后，内存占用下降到有原来的 300 多 MB下降到 24MB。耗时从 1226ms 下降到 1024ms。

建议应用。

已經能算出第7頁的唯一共贏走法！

第7頁是混亂時鐘的一個非常複雜的局面，我也是研究了老半天才得出結論。

現在加了哈希校驗之後，算出來了唯一解法，跟我的結論一樣！

board: 2, 8, 11, 9, 4, 12, 10, 6, 5, 7, 1, 3,
player: 1
last_move: 0

roll_sum:6432834
max_depth:48
result_sum:632006

movelist:
roll->value: 3 ; player: 1 ; lastmove: 0 ; maxdeep: 48
; board: 2, 8, 11, 9, 4, 12, 10, 6, 5, 7, 1, 3,
this_depth: 0 ; available move:12
0: ->value: 4 ; player: 0 ; lastmove: 1 ; maxdeep: 48
1: ->value: 4 ; player: 0 ; lastmove: 2 ; maxdeep: 26
2: ->value: 4 ; player: 0 ; lastmove: 3 ; maxdeep: 16
3: ->value: 4 ; player: 0 ; lastmove: 4 ; maxdeep: 23
4: ->value: 4 ; player: 0 ; lastmove: 5 ; maxdeep: 29
5: ->value: 3 ; player: 0 ; lastmove: 6 ; maxdeep: 28
6: ->value: 4 ; player: 0 ; lastmove: 7 ; maxdeep: 35
7: ->value: 4 ; player: 0 ; lastmove: 8 ; maxdeep: 23
8: ->value: 4 ; player: 0 ; lastmove: 9 ; maxdeep: 9
9: ->value: 4 ; player: 0 ; lastmove: 10 ; maxdeep: 31
10: ->value: 4 ; player: 0 ; lastmove: 11 ; maxdeep: 26
11: ->value: 4 ; player: 0 ; lastmove: 12 ; maxdeep: 29

select one option:

由於github總是pull&push不行，所以我先傳到這裏。

第五頁測出bug，已想好對策

當前，我設定了一個「不能空轉」的機制，即當某個棋子（比如4，3,，8，9）走了三四步，就能回到起點，而且行走過程中都是踩空（吃不到其它棋子），這時我設定它不能走。

但這在棋理上是不對的，因為有時踩空是為了給別的棋子吃掉。

所以，代碼仍需完善。拿第五頁去測就知道了。

使用内存池以提升性能

e0e3e83 使用的是 C++20 标准库的内存池。

从 1014ms 下降到 987 ms, 不是很明显。

原因有待查明，可能是使用方法不当？

或者需要自己写一个内存池？

用 JavaScript 写 UI 交互如何

在JavaScript中调用C++库，可以使用WebAssembly技术。WebAssembly是一种新的低级字节码，可以在Web浏览器中运行，并且可以与JavaScript代码进行交互。下面是一个简单的示例：

1.首先，需要编译C++代码为WebAssembly格式。可以使用Emscripten编译器，它是一个将C/C++代码编译为WebAssembly的工具。例如，假设有一个名为"mylib.cpp"的C++库文件，可以使用以下命令将其编译为WebAssembly模块：

emcc mylib.cpp -s WASM=1 -o mylib.wasm

该命令将生成一个名为"mylib.wasm"的WebAssembly模块。

2.接下来，在JavaScript中加载WebAssembly模块，并将其实例化为一个对象。可以使用JavaScript的WebAssembly API来加载模块。例如，以下代码将加载"mylib.wasm"模块，并实例化它：

fetch('mylib.wasm')
  .then(response => response.arrayBuffer())
  .then(bytes => WebAssembly.instantiate(bytes))
  .then(results => {
    const mylib = results.instance.exports;
    // 可以调用C++函数了
    console.log(mylib.myFunction());
  });

上面的代码将加载WebAssembly模块，然后将其实例化为一个对象。该对象包含C++库中的所有导出函数。在此示例中，C++库中的一个名为"myFunction"的函数被调用，并在控制台上输出结果。

需要注意的是，由于WebAssembly是一种低级字节码，因此在JavaScript和C++之间进行交互可能会涉及到一些底层的概念，如内存地址和指针。因此，需要非常小心地处理这些细节，以确保正确地进行交互。

参考资料：https://developer.mozilla.org/en-US/docs/WebAssembly/C_to_wasm

实现哈希表之后的性能进一步优化

V3 版本已经实现哈希表，解决了性能的大头，那么接下来优化什么呢？

基于 8a00c04 进行 VS 性能分析，发现几乎 100% 的耗时都在 pos->children.clear(); 这个函数上。

因此，如果将内存的分配和释放进一步减少，那么效率预计将还会大幅提升。

测试用例更新

对于 https://ejsoon.win/chaosclock/4/ , 各个局面如下：

4,3,11,0,5,6,0,0,0,2,0,0;1;12 
4,3,11,0,5,6,12,0,0,2,0,0;0;11
4,3,7,11,5,6,12,0,0,2,0,0;1;6
4,3,7,11,5,10,12,0,0,2,0,0;0;7
4,3,1,11,5,10,12,7,0,2,0,0;1;4
8,3,1,11,5,10,12,7,4,2,0,0;0;3
8,6,1,11,5,10,12,7,4,2,3,0;1;5
8,6,1,11,9,10,12,7,4,2,3,5

4 己贏
3 共贏
2 同輸
1 己輸
0 無果

目前使用

4,3,7,11,5,10,12,0,0,2,0,0;0;7

其输出结果为：

roll_sum:679988
max_depth:20
result_sum:370647

Stage 1 took 1000 ms
board: 4, 3, 7, 11, 5, 10, 12, 0, 0, 2, 0, 0,
depth:0
player: 0
value:3
available move:6
  0: 2 (value: 4)
  1: 10 (value: 3)
  2: 11 (value: 4)
  3: 12 (value: 3)
  4: 6 (value: 3)
  5: 8 (value: 4)
Stage 2 took 0 ms

为用例。随着优化地进行，用例需要不断更新。

現在是第五層，那麼第一層的用時大概會是12111091250。

如果往上一層，是否已經可以在30s以內？

做一個跟pos同行的「影子數據」

輸出結果不需要是一個position，只需要lastmove跟value就可以了？

數據量仍有必要精簡，就是做一個跟pos同行的「影子數據」，如

struct pos_shadow {
    int lastmove;
    int player;
    pos_shadow *children;
}

當pos統計出子節點分數最高分而得到自己的分數時，就清空掉pos的children。
一個pos數據量還是挺大的，尤其有「pieces_data」等。

能算到初始局面了，接下來的任務

board: 8, 6, 1, 11, 9, 10, 12, 7, 4, 2, 3, 5,
player: 1
last_move: 0

roll_sum:8663873
max_depth:44
result_sum:816353
multi_board:22076284

ejsoon->value: 3 ; player: 1 ; lastmove: 0 ; maxdeep: 44
; board: 8, 6, 1, 11, 9, 10, 12, 7, 4, 2, 3, 5,
this_depth: 0 ; available move:12
0: ->value: 4 ; player: 0 ; lastmove: 1 ; maxdeep: 29
1: ->value: 4 ; player: 0 ; lastmove: 2 ; maxdeep: 39
2: ->value: 3 ; player: 0 ; lastmove: 3 ; maxdeep: 32
3: ->value: 3 ; player: 0 ; lastmove: 4 ; maxdeep: 42
4: ->value: 3 ; player: 0 ; lastmove: 5 ; maxdeep: 24
5: ->value: 4 ; player: 0 ; lastmove: 6 ; maxdeep: 24
6: ->value: 4 ; player: 0 ; lastmove: 7 ; maxdeep: 42
7: ->value: 3 ; player: 0 ; lastmove: 8 ; maxdeep: 44
8: ->value: 3 ; player: 0 ; lastmove: 9 ; maxdeep: 31
9: ->value: 3 ; player: 0 ; lastmove: 10 ; maxdeep: 36
10: ->value: 4 ; player: 0 ; lastmove: 11 ; maxdeep: 23
11: ->value: 4 ; player: 0 ; lastmove: 12 ; maxdeep: 43

select one option:

接下來的任務是：

（重要，難）若查到有重覆，則賦值那個節點的指針（而非現在只是賦值value）
（中等）判斷哈希是否真的沒有重覆。
（容易）main()中，按-2往上回退一步，按-1回退至開頭
（容易）自動生成隨機開局

同時，程序仍需要更多的測試。

ChatGPT 给出的解决思路

尝试将混乱时钟棋规喂给 ChatGPT，请其给出解决思路，输出如下，有点意思，初看感觉没有大的问题，细看才能发现。

我已经介绍了混乱时钟的棋规，下面请给出解决思路? 谢谢！

思路

下面提供一些思路和算法流程供参考。

游戏状态表示

首先，我们需要设计一种数据结构来表示游戏状态，可以使用一个长度为12的数组来表示环形队列，数组中的每个元素是一个数字，表示当前位置上的棋子编号。用一个布尔型变量来表示上一步是否有棋子被移动。用两个数组来表示白色和黑色手中棋子，每个元素是一个数字，表示手中棋子的编号。用两个整型变量来表示甲方和乙方的得分。

搜索算法

深度优先搜索算法是一种广泛使用的搜索算法，其基本**是从初始状态开始，逐步扩展状态空间，直到找到目标状态。在本问题中，我们可以将搜索空间定义为所有可能的游戏状态，然后使用深度优先遍历算法在这个状态空间中搜索最优解。

具体地，搜索算法的基本框架如下：

（1）从初始状态开始，设置当前状态为根节点。

（2）对当前状态进行评估，如果当前状态为终止状态，则返回对应的得分值；否则进入下一步。

（3）对当前状态进行扩展，生成其所有可能的子状态，即通过移动棋子、摆子或者放弃行动机会，生成新的游戏状态。

（4）对每个子状态递归调用搜索函数，更新当前状态的得分值，即根据当前状态和子状态的关系，更新甲方和乙方的得分值，并将子状态的得分值加入当前状态的得分值。

（5）返回当前状态的得分值。

（6）比较所有子状态的得分值，选择最优的子状态作为下一步的状态。

（7）重复（2）至（6），直到找到最优解。

在搜索算法的实现中，需要注意以下几点：

（1）为了避免重复计算，可以使用哈希表来记录已经搜索过的状态。

（2）为了加速搜索过程，可以使用剪枝算法来减少搜索空间。例如，如果某个状态已经不能得到最优解，则可以停止对该状态进行扩展；如果某个状态已经超过了最优解的得分，则可以停止对该状态进行扩展。

（3）为了提高代码的可读性和可维护性，可以将搜索算法和状态表示分别封装成类或函数，并提供必要的接口。

总结

深度优先搜索算法是一种适用于各种搜索问题的通用算法，其优点是可以找到最优解，但其缺点是可能会陷入死循环或者搜索空间过大而无法找到最优解。在本问题中，深度优先搜索算法可以找到最优解，但需要注意搜索空间的大小和剪枝算法的应用，否则会导致搜索时间过长或者内存溢出等问题。另外，在实现搜索算法时，需要考虑到游戏规则的复杂性和算法的可读性和可维护性，选择合适的数据结构和算法实现方式，从而达到更好的代码设计和性能优化效果。

我已经介绍了混乱时钟的棋规，下面请给出程序结构和思路！

程序结构

本程序可以分为四个部分：

定义数据结构和全局变量：包括环形队列、手中数组、得分和标志变量等。
搜索函数：使用深度优先搜索算法进行游戏状态搜索和得分计算。
移动函数：根据游戏规则进行棋子的移动和手中棋子的摆放。
主函数：负责游戏初始化和搜索调用等功能。

思路

定义数据结构和全局变量。
搜索函数：

搜索函数的基本思路如下：

（1）检查当前状态是否为终止状态，即所有白色棋子都放到了白色空位或所有黑色棋子都放到了黑色空位，或者达到了连续多步未移动棋子的上限。

（2）对当前状态进行评估，即根据游戏规则计算甲方和乙方的得分。

（3）对当前状态进行扩展，即通过移动棋子、放回手中棋子或者放弃行动机会，生成新的游戏状态。

（4）对每个子状态递归调用搜索函数，更新当前状态的得分值，并将子状态的得分值加入当前状态的得分值。

（5）返回当前状态的得分值。

移动函数：

移动函数负责根据游戏规则进行棋子的移动和手中棋子的放置。

主函数：

主函数负责游戏初始化和搜索调用等功能。

最后需要注意的是，本程序只提供了一个大致的框架和思路，具体实现还需要根据实际需求进行调整和优化。同时，需要仔细考虑游戏规则和边界条件，以确保程序的正确性和可靠性。

優化之後速度確實快，但出現問題

用第五頁的局面：

9,10,8,1,4,7,11,6,5,3,12,2

當player1走完1之後，應該輪到p0，這裏出現兩個走法，其中4是落子，只能由player1才能落4。同時行動結束也沒有切換player。

可拿之前我的版本來作對比，我也看一下是哪裏的問題。

問下以下代碼為何出錯？

#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

struct Position
{
	uint64_t board = 0;
	vector<Position *> children; // 24 Bytes
};

vector<Position *> board_map[28];

int main()
{
	Position *ccc = new Position();
	ccc->board = 122332ll;
	board_map[7] = ccc;
    return 0;
}

想給一個指針數組賦值。