「益智遊戲」和「抽象弈棋」
回复
头像
ejsoon
一枝独秀一枝独秀
帖子: 6551
注册时间: 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/
弈趣極光:享受思維樂趣
头像
ejsoon
一枝独秀一枝独秀
帖子: 6551
注册时间: 2022年 11月 18日 17:36
联系:

Re: 一個新的遊戲創意

帖子 ejsoon »

修復和改進
當MCTS搜尋時,未能實時顯示時間和搜尋量。

為什麼在改成增量運算之後,運算量反而不如之前?

檢查代碼,看是否存在錯誤以及有哪些可以修復和改進的地方。

回答要求:

不要影響當前正確的流程,明確給出所要修改的地方和所要替換的代碼。

trigolden_game264.html

https://gpt.quanquan.space/share/3KpfXW ... _DUErSvumw
附件
trigolden_game264.html.7z
(47.92 KiB) 已下载 6 次
https://ejsoon.vip/
弈趣極光:享受思維樂趣
头像
ejsoon
一枝独秀一枝独秀
帖子: 6551
注册时间: 2022年 11月 18日 17:36
联系:

Re: 一個新的遊戲創意

帖子 ejsoon »

AI好像重回巔峰。

trigolden_game2641.html
附件
trigolden_game2641.html.7z
(48.76 KiB) 已下载 3 次
https://ejsoon.vip/
弈趣極光:享受思維樂趣
头像
ejsoon
一枝独秀一枝独秀
帖子: 6551
注册时间: 2022年 11月 18日 17:36
联系:

Re: 一個新的遊戲創意

帖子 ejsoon »

目前的程式對規則的支援是錯誤的,某些地方應能下的不給下,如第二張圖所示。第三張圖是以前程式,是對的。

規則上只不允許懸空的端點跟場上已有棋子的端點重合,而現在貼上去的邊的兩個端點都不是懸空的端點,那就是可以跟其它棋子的端點重合的。

查找原因並修復。

代码: 全选

測到bug,本應能放現在不能放了
1274 5411 3213 5121 4222 2242 2343 4174 6471 5191 1392 22103 21104 32133 14134 31141 44144 23162 62163 3434 1431 64211 43213 24231 63232 12172 23173 24264 64261 64281 12283 22222 51221 54321 23202 42352 54351 51251 32373 51301 32302 63403 53292 51431 22432 32442 32443 14471 34474 31491 32492 34394 62393 3454 546 3312 1213 3121 4424 3353 4151 1373 3474 5392 1491 51101 13102 22122 62123 61151 13153 53163 63162 61181 13182 64211 14214 61191 11194 1343 3444 12272 4134
图片

图片

代码: 全选

function ghostConflictsWithPiece(ghost, piece) {
  const collision = checkSATCollision(getSAT(ghost), getSAT(piece));

  if (collision === 'separated') return false;
  if (collision === 'overlap') return true;

  // 禁止任何邊貼合/部分邊重合。
  for (let edgeA = 0; edgeA < 4; edgeA++) {
    for (let edgeB = 0; edgeB < 4; edgeB++) {
      if (
        segmentsOverlapAsEdges(
          ghost.vertices[edgeA],
          ghost.vertices[(edgeA + 1) % 4],
          piece.vertices[edgeB],
          piece.vertices[(edgeB + 1) % 4]
        )
      ) {
        return true;
      }
    }
  }

  /*
   * 規則只禁止「懸空端點」和場上既有棋子的端點重合。
   *
   * ghost.myEdge 是此棋貼合到目標棋子的邊;
   * 該邊的兩端不是懸空端點,故即使與其他既有棋子的端點重合,
   * 也必須保留為合法活法。
   */
  const attachedVertices = new Set([
    ghost.myEdge,
    (ghost.myEdge + 1) % 4
  ]);

  for (let vertexIndex = 0; vertexIndex < 4; vertexIndex++) {
    // 貼合邊的端點不是懸空端點:允許重合。
    if (attachedVertices.has(vertexIndex)) continue;

    for (const pieceVertex of piece.vertices) {
      if (pointsEqual(ghost.vertices[vertexIndex], pieceVertex)) {
        return true;
      }
    }
  }

  return false;
}
附件
trigolden_game2642.html.7z
(48.93 KiB) 尚未被下载
https://ejsoon.vip/
弈趣極光:享受思維樂趣
回复
  • 相似主题
    回复总数
    阅读次数
    最新帖子

在线用户

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