Regression: legal-move generation still dominates search, so hard never gets past depth 3
维护者通常 1 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 5/5
- 预计耗时
- 一周以上
- 新手友好度
- 38/100
- Issue 类型
- 缺陷
- 描述清晰度
- 描述清楚
- 活跃度
- 活跃
- 技术栈
- javascript
- 领域
- backend, performance
调研方向
Start with js/rules.js at legalMovesFrom, allLegalMoves and allLegalCaptures, then read the search and quiescence call sites in js/ai.js. Run npm test and use the provided Node benchmark steps to compare move generation with evaluation. Done means all acceptance criteria pass, including the generator cross-checks and the hard depth 4 timing target.
由索引模型根据 Issue 内容生成。
描述
Summary
#86 was closed, but legal-move generation is still the main cost of the engine search. It costs about 40 times as much as evaluation. As a result, the "hard" level never finishes a search deeper than its base depth of 3, and its maxDepth: 8 cannot be reached.
Where
js/rules.js:243-270(legalMovesFrom)js/rules.js:302-360(allLegalMoves,allLegalCaptures)js/ai.js:16(hard: { depth: 3, timeMs: 1000, maxDepth: 8 })js/ai.js:118,js/ai.js:201(search and quiescence call sites)
Details
For every piece, legalMovesFrom tests all 64 target squares with isPseudoLegalMove and isPathObstructed. For each candidate move it copies the whole board (applyMove) and runs isInCheck. The search calls this at every interior node, and quiescence calls allLegalCaptures, which also runs one applyMove per capture.
Measured in Node on a middlegame position:
| Operation | Cost |
|---|---|
allLegalMoves |
685 µs per call |
allLegalCaptures |
173 µs per call |
evaluatePosition |
17.5 µs per call |
| Depth-3 search | 1.1 s, 10.7k nodes |
| Depth-4 search | 16.9 s, 115k nodes |
Impact
hard is allowed about 1 s, or at most 3 s on the clock (searchBudget), so iterative deepening never completes depth 4. The worker then spends the rest of its allowance on a depth-4 search that is thrown away. Hard plays at its fixed depth, and every computer move and every hint keeps a core busy for the full allowance. On phones, depth 3 alone takes longer than the 1 s allowance. The same constant also makes review scoring (see the issue on review steps) and the no-worker fallback slow.
Steps to reproduce
- Time
searchPositionat depth 3 and depth 4 on a middlegame position, usingrules.jsandai.jsin Node or in a jest test. - Compare the cost of
allLegalMoveswith the cost ofevaluatePosition.
Suggested fix
- Generate pseudo-legal moves from piece offsets and sliding rays instead of scanning all 64 squares.
- Check legality only where it can fail: king moves, pinned pieces (one ray scan from the king), en passant, and positions in check.
- Or defer the legality test until the search actually plays a move, and count a node with no legal child as mate or stalemate.
- Make and unmake moves on one board (or a flat 64-entry array) instead of copying it for each move.
- Then add move ordering (MVV-LVA, killer moves).
Keep the public functions in rules.js as wrappers so callers and tests don't change. The existing generator cross-check tests ("quick generators agree") act as a perft-style safety net.
Acceptance criteria
-
allLegalMovesis at least 5 times faster on the benchmark position. - Hard completes depth 4 within its 1 s allowance on desktop.
- All rules tests and generator cross-checks pass unchanged.
Getting started
- Relevant files:
js/rules.js,js/ai.js,tests/unit/rules.test.js,tests/unit/ai-strength.test.js - How to run tests:
npm test
Regression of #86.
Filed by repo-audit/full-audit at 01c6a35. Severity: medium. Effort: M. audit-key: performance|js/rules.js|legalMovesFrom
- 主要语言
- JavaScript
- 星标
- 4
- 派生
- 2
- 平均合并
- 22 小时 16 分钟
- 30 天内合并 PR
- 9
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue,再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库,在一个分支上完成修改。
- 提交 Pull Request,并在描述里引用这个 Issue 编号。
TMHSDigital/Static_Chess 的其他 Issue
-
enhancement help wanted severity: low
难度 4/5 3-5 天 新手友好度 55/100
TMHSDigital/Static_Chess#184 ·
维护者通常 1 天内回复
-
enhancement help wanted severity: low
难度 4/5 3-5 天 新手友好度 58/100
TMHSDigital/Static_Chess#182 ·
维护者通常 1 天内回复
-
help wanted severity: medium tech-debt
难度 4/5 3-5 天 新手友好度 45/100
TMHSDigital/Static_Chess#173 ·
维护者通常 1 天内回复
-
severity: medium tech-debt
难度 5/5 一周以上 新手友好度 35/100
TMHSDigital/Static_Chess#171 ·
维护者通常 1 天内回复
-
enhancement help wanted severity: low
难度 4/5 3-5 天 新手友好度 61/100
TMHSDigital/Static_Chess#161 ·
维护者通常 1 天内回复
查看 TMHSDigital/Static_Chess 的全部 Issue
相似的 Issue
-
priority: low server testing
难度 1/5 1 小时以内 新手友好度 88/100
blamechris/chroxy#9277 ·
维护者通常 1 天内回复
-
[MCP]: page snapshots in .playwright-mcp/ are not git-ignored (.playwright-cli/ is, since #42318)未关闭
难度 2/5 1-3 小时 新手友好度 62/100
microsoft/playwright#44289 ·
维护者通常 1 天内回复
-
Bug
难度 2/5 1-3 小时 新手友好度 75/100
Ionaru/easy-markdown-editor#657 ·
-
难度 2/5 1-3 小时 新手友好度 66/100
TMHSDigital/Free-Game-Dev-Assets#320 ·
维护者通常 1 天内回复
-
area:webapp bug finding
难度 2/5 1-3 小时 新手友好度 72/100
维护者通常 1 天内回复