「益智遊戲」和「抽象弈棋」
回复
头像
ejsoon
一枝独秀一枝独秀
帖子: 6548
注册时间: 2022年 11月 18日 17:36
联系:

Re: 一個新的遊戲創意

帖子 ejsoon »

改進與修復

以下是本程式「是否有在用增量運算」的分析結果:

沒有使用的關鍵增量運算

對於使用者所說的「只對本回合新增兩顆棋子做局部更新」,在最耗時的部分,程式沒有完成這種增量化。

1. 每個搜尋節點重新生成所有單子

每次 generateLegalTurns(state) 都重新呼叫:

generateLegalSinglePlacements(state, state.mover)

而它會:

掃過盤上所有對方棋子;
掃過尚可用的棋種;
正反面各一次;
目標邊 4 種;
自己貼合邊 4 種;
對每個候選呼叫 validatePlacementGeometry();
再用 isValidGhost() 對整個盤面逐一做幾何衝突檢查。

沒有「父節點候選集 + 新增兩子影響範圍」的更新機制,也沒有按照盤面狀態保存生成結果的 transposition cache。

2. 兩子組合是重新兩兩枚舉

generateLegalTurns() 對所有單子做:
js

for (let i = 0; i < singles.length; i++) {
for (let j = i + 1; j < singles.length; j++) {

這是平方級配對。每一對還可能進行:

twoGhostsCompatible(first, second);
formsTriGolden(first, second);
validateTurnOnState(state, move);
adjudicateSearchTurn(state, move)。

這不是局部增量。

3. 計分是全盤重新掃描

adjudicateSearchTurn(state, placedPieces) 裡有:
const allPieces = state.boardPieces.concat(placedPieces);

for (const dinger of allPieces) {
for (const victim of allPieces) {

即使本回合只新增一或兩顆棋,它仍對所有棋子對做接觸、頂點、邊與樹距離判斷,而不是只檢查「新棋與舊棋」及「新棋彼此」。

此外,每個可能的頂鑫關係還會呼叫:

getTreeDistance(dinger, victim, allPieces, idMap)

這也不是沿父狀態保存的可增量圖/距離結果。

死活/共活判斷同樣重算

hasArbitrationDefence(state) 會直接:

return generateArbitrationDefenceTurns(state).length > 0;

而 generateArbitrationDefenceTurns() 不是「找到第一組共活便停止」,而是收集全部共活回合後才回傳陣列。對 MCTS 而言,實際只需要知道是否存在至少一組,卻仍付出了生成所有組合、去重、完整驗證的成本。

結論

目前的情況是:

有 SAT 快取;
沒有候選走法的真正增量更新;
沒有計分/連接圖/樹距離的真正增量更新;
沒有局面轉置快取;
沒有把「是否有至少一組共活」做早停。

所以答案是:目前並非使用者設想的那種「只根據新增兩子局部更新活法」的增量運算。

分析結束。

根據以上分析,在MCTS和minimax搜尋中,把所有的「活法、共活、單連、雙接、計分」等都做成增量運算。

其中generateLegalTurns和generateArbitrationDefenceTurns在功能上是重覆的,應新建一個增量運算的函式,仍然通過增量的方式把所有的「共活」算完,不僅用於判定是否存在「共活」,還能把所有的「共活」用於接下來的MCTS或minimax增量運算。

回答要求:

不要使當前正確的遊戲流程發生改變。明確給出所要修改的地方和所要替換的代碼。

代码: 全选

改進與修復

以下是本程式「是否有在用增量運算」的分析結果:

沒有使用的關鍵增量運算

對於使用者所說的「只對本回合新增兩顆棋子做局部更新」,在最耗時的部分,程式沒有完成這種增量化。

1. 每個搜尋節點重新生成所有單子

每次 generateLegalTurns(state) 都重新呼叫:

generateLegalSinglePlacements(state, state.mover)

而它會:

    掃過盤上所有對方棋子;
    掃過尚可用的棋種;
    正反面各一次;
    目標邊 4 種;
    自己貼合邊 4 種;
    對每個候選呼叫 validatePlacementGeometry();
    再用 isValidGhost() 對整個盤面逐一做幾何衝突檢查。

沒有「父節點候選集 + 新增兩子影響範圍」的更新機制,也沒有按照盤面狀態保存生成結果的 transposition cache。

2. 兩子組合是重新兩兩枚舉

generateLegalTurns() 對所有單子做:
js

for (let i = 0; i < singles.length; i++) {
  for (let j = i + 1; j < singles.length; j++) {

這是平方級配對。每一對還可能進行:

    twoGhostsCompatible(first, second);
    formsTriGolden(first, second);
    validateTurnOnState(state, move);
    adjudicateSearchTurn(state, move)。

這不是局部增量。

3. 計分是全盤重新掃描

adjudicateSearchTurn(state, placedPieces) 裡有:
const allPieces = state.boardPieces.concat(placedPieces);

for (const dinger of allPieces) {
  for (const victim of allPieces) {

即使本回合只新增一或兩顆棋,它仍對所有棋子對做接觸、頂點、邊與樹距離判斷,而不是只檢查「新棋與舊棋」及「新棋彼此」。

此外,每個可能的頂鑫關係還會呼叫:

getTreeDistance(dinger, victim, allPieces, idMap)

這也不是沿父狀態保存的可增量圖/距離結果。

死活/共活判斷同樣重算

hasArbitrationDefence(state) 會直接:

return generateArbitrationDefenceTurns(state).length > 0;

而 generateArbitrationDefenceTurns() 不是「找到第一組共活便停止」,而是收集全部共活回合後才回傳陣列。對 MCTS 而言,實際只需要知道是否存在至少一組,卻仍付出了生成所有組合、去重、完整驗證的成本。

結論

目前的情況是:

    有 SAT 快取;
    沒有候選走法的真正增量更新;
    沒有計分/連接圖/樹距離的真正增量更新;
    沒有局面轉置快取;
    沒有把「是否有至少一組共活」做早停。

所以答案是:目前並非使用者設想的那種「只根據新增兩子局部更新活法」的增量運算。

分析結束。

根據以上分析,在MCTS和minimax搜尋中,把所有的「活法、共活、單連、雙接、計分」等都做成增量運算。

其中generateLegalTurns和generateArbitrationDefenceTurns在功能上是重覆的,應新建一個增量運算的函式,仍然通過增量的方式把所有的「共活」算完,不僅用於判定是否存在「共活」,還能把所有的「共活」用於接下來的MCTS或minimax增量運算。

回答要求:

不要使當前正確的遊戲流程發生改變。明確給出所要修改的地方和所要替換的代碼。
trigolden_game263.html

https://gpt.quanquan.space/share/ykjdPU ... yO3dszd6L0
https://ejsoon.vip/
弈趣極光:享受思維樂趣
回复
  • 相似主题
    回复总数
    阅读次数
    最新帖子

在线用户

正浏览此版面之用户: 没有注册用户 和 2 访客