Regression: legal-move generation still dominates search, so hard never gets past depth 3

Đang mở
#168 1 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
38/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
javascript
Lĩnh vực
backend, performance

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

help wanted performance severity: medium

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

  1. Time searchPosition at depth 3 and depth 4 on a middlegame position, using rules.js and ai.js in Node or in a jest test.
  2. Compare the cost of allLegalMoves with the cost of evaluatePosition.

Suggested fix

  1. Generate pseudo-legal moves from piece offsets and sliding rays instead of scanning all 64 squares.
  2. Check legality only where it can fail: king moves, pinned pieces (one ray scan from the king), en passant, and positions in check.
  3. Or defer the legality test until the search actually plays a move, and count a node with no legal child as mate or stalemate.
  4. Make and unmake moves on one board (or a flat 64-entry array) instead of copying it for each move.
  5. 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

  • allLegalMoves is 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

Ngôn ngữ chính
JavaScript
Star
4
Fork
2
Merge trung bình
22 giờ 16 phút
Pull request đã merge (30 ngày)
9

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của TMHSDigital/Static_Chess

Tất cả issue của TMHSDigital/Static_Chess

Issue tương tự

Thêm issue về JavaScript

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.