WIP: Better hashmap - Githubissues

ErinvanderVeen / OOOO

the Overpowered non-Organic Othello Opponent

GNU Lesser General Public License v3.0

0 stars 0 forks source link

WIP: Better hashmap #60

Open emwestin opened 5 years ago

emwestin commented 5 years ago

Not ready for merging yet. Title will drop WIP when ready.

emwestin commented 5 years ago

Some rough numbers comparing master (1b52f5c92b234197d9d49f91e71bb0da267459e5) with this pull request:

Metric	Master (serial)	Pull request (serial)	Master (parallel)	Pull request (parallel)
Nodes/s	2M	3-5M	2M	3-6M
Pruning (%)	-	-	Max seen 66%	Max seen 70%

emwestin commented 5 years ago

Some statistics from running one game for each version with 10 seconds per move. Data from perf with a sampling of 1000hz.

Pull request (parallel)

Overhead	Symbol
35.68%	negamax
15.94%	do_move
13.27%	find_eval
9.36	mutex_lock
6.42	mutex_unlock

Master 1b52f5c (parallel)

Overhead	Symbol
22.45%	omp related
17.84%	find_eval
11.19%	omp related
10.42	omp related
10.17	omp related
7.48	negamax

ErinvanderVeen commented 5 years ago

Games/s: 0.30
AI wins: 69.44%
Draws: 1
AI:
    Start Depth: 1
    Average Reached Depth: 9
    Nodes/s: 191982.327972
    Branches: 740518133
    Branches explored: 318796455
    Branches pruned: 421721678
    Branch factor: 2.332338
    % Pruned: 56.949541
    Nodes evaluated: 317500374
    Unique nodes evaluated: 86733814
    % Unique nodes : 27.317705
HASHMAP:
    Total Hits: 242726437
    Total Misses: 163403426
    % Hit: 59.765720
    Total Collisions: 35340

ErinvanderVeen commented 5 years ago

SERIAL:

Games/s: 0.23
AI wins: 64.29%
Draws: 0
AI:
    Start Depth: 1
    Average Reached Depth: 7
    Nodes/s: 60053.519280
    Branches: 67198292
    Branches explored: 30629277
    Branches pruned: 36569015
    Branch factor: 2.190200
    % Pruned: 54.419560
    Nodes evaluated: 30681343
    Unique nodes evaluated: 8272733
    % Unique nodes : 26.963399
HASHMAP:
    Total Hits: 19726554
    Total Misses: 19229058
    % Hit: 50.638542
    Total Collisions: 0

ErinvanderVeen commented 5 years ago

PARALLEL:

Number of Threads: 2
Games/s: 0.23
AI wins: 78.57%
Draws: 1
AI:
    Start Depth: 1
    Average Reached Depth: 6
    Nodes/s: 155048.351329
    Branches: 79861751
    Branches explored: 37303941
    Branches pruned: 42557810
    Branch factor: 2.139022
    % Pruned: 53.289352
    Nodes evaluated: 37335643
    Unique nodes evaluated: 6041763
    % Unique nodes : 16.182293
HASHMAP:
    Total Hits: 24134618
    Total Misses: 22977160
    % Hit: 51.228417
    Total Collisions: 990398