Skip to content

Latest commit

 

History

History
108 lines (96 loc) · 3.64 KB

performance.md

File metadata and controls

108 lines (96 loc) · 3.64 KB
Raw

CPU hotspots

3x3 Windows.

  • Apply Action
    • Get Legal Moves
      • Board Get Captured Groups
        • Board Get Group At
          • Recursive Add Point
            • HashSet.Contains: Point.Equals

Solutions

  1. Pool groups.
  2. Pool boards.
  3. Pool games.
  4. DISABLE_GROUP_POINTS hypothesizes next hotspots.
  5. Store in super ko previous board state and move that will be made.
  6. Query has liberty before suicide.
  7. Do not calculate captures for legal moves.
  8. Cache legal moves. Copy when cloning game. Update after making a move.
  9. When making a move from AI, assume legal.
  10. Board: clone: group caches.
  11. Game: black capture advantage.
  12. When no legal move, cache loss for that player. Do not calc territory or score. if komi, other player keeps playing. captures modifies local komi delta. black wins ties.
  13. Minimal group data.
  14. Groups: Preallocate fixed length data.
  15. Groups: Merge groups.
  16. Liberties mask per group.
  17. Static: board size.
  18. Weight exploratory actions toward center position on the 3x3 or 5x5 board.
  19. Flyweight board data structure.
  20. when capturing, update legal moves. when playing reexamine legal moves.
  21. Super ko: Preallocate fixed length data, circular array of bitmasks.
  22. When applying action, reuses game instead of cloning game.
  23. Precompute bitmask of move.
  24. Bitmask 5x5 board into 25 bits of a 32-bit integer. Masks: Black, White.
  25. With each move, modify only necessary data.
  26. Localize memory access.
  27. Legal moves: modifies board with minimal data copying.
  28. Legal moves as mask.
  29. captures as bitmask.
  30. Index instead of point.
  31. Bitmask instead of groups.
  32. DISABLE_CALC_TERRITORY
  33. Cache boards.
  34. DISABLE_CAPTURES_DICTIONARY
  35. Pool actions.
  36. +30%: Cache boards of legal moves for reuse in make move.
  37. With the above disabled, 5x5 runs 1000 iterations in 200 ms in editor.
  38. class references array of values.
  39. profile struct vs class
  40. seal classes
  41. Custom HashSet comparison.
  42. MCTS: Collections without Linq. Get max element. Random choice.
  43. Thread.
  44. burst compiler.
  45. Job System.
  46. Pool game tree node.

Go Searcher 3x1 CPU Hotspots

  • 700 ms: Cloning 20000 Go State 5x5.
    • 500 ms: Cloning Go Game State 5x5.
      • 200 ms: Cloning arrays.
      • 50 ms: Constructing lists.
  • 400 ms: Apply Action 20000 times.
    • 380 ms: Go Game State 5x5 Move
      • 100 ms: Try Forbid Suicide At Index
        • 40 ms: Would Share Any Liberty
        • 20 ms: Would Capture Any
      • 100 ms: String concat.
      • 70 ms: Convert Move Mask.
      • 40 ms: Add Board To History

  1. On each move, log liberties, occupied.

  2. Merge groups after capture. See audit below.

  3. Diagnose cause of suicide:

         .....
     .xxxx
     .oooo
     oxxo.

  4. Correct so that will not play suicide.

  5. Displays cells on 3x1.

  6. Pool go game state 5x5.

  7. Pool go state 5x5.

  8. Select move from mask.

  9. Bias central move.

Merge groups after capture

White just captured. Expected one group. Got two groups.

    Audit:
    Board Diagram: 
    ooo
    o..
    o..
    Illegal Move Masks: 111/100/100, 111/100/100
    Turn Index: 0
    Player Index 0:
    Player Index 1:
    Group Liberty Mask: 000/010/010, Group Occupied Mask: 110/100/100
    Group Liberty Mask: 000/001/000, Group Occupied Mask: 001/000/000