-
Notifications
You must be signed in to change notification settings - Fork 10
Perft
Perft is a heuristic for testing a game engine's valid move generator, developed by chess programmers, by calculating how many possible board positions exist a certain number of turns in the future.
To calculate the "perft result" one walks (plays) the tree of every possible legal move to a certain ply (turn) depth and counts the number of leaf nodes (final positions). The results can then be compared against a pre-computed table to validate that the engine is generating the correct number of legal moves at each board position.
By definition, perft(0) = 1, since if you don't play any moves, you only have the same board position you started with.
Now, following the rules of Hive as implemented by Mzinga (see notes below), for a new game with no expansion pieces at the initial position, White has four options (place either a Beetle, a Grasshopper, a Spider, or an Ant).
Therefore with four possible board positions after one turn, perft(1) = 4.
After that first turn, Black can also respond with either a Beetle, a Grasshopper, a Spider, or an Ant, and can place their bug on any of the six available sides of White's first bug. So Black has (6 x 4) = 24 possible responses to White's first play. If we multiply the number of plays White could have played times the number of play Black could respond with, you get (4 x 24) = 96 possible board positions after two turns. Therefore perft(2) = 96.
After the first two turns, as Queens can come into play and pieces can not only be placed but also moved, calculating perft by hand becomes much more difficult.
All of these numbers were calculated using MzingaPerft v0.12.9 following the notes below.
Depth | Base | Base+M | Base+L | Base+P |
---|---|---|---|---|
0 | 1 | 1 | 1 | 1 |
1 | 4 | 5 | 5 | 5 |
2 | 96 | 150 | 150 | 150 |
3 | 1,440 | 2,610 | 2,610 | 2,610 |
4 | 21,600 | 45,414 | 45,414 | 45,414 |
5 | 516,240 | 1,252,800 | 1,252,800 | 1,255,932 |
6 | 12,219,480 | 34,233,432 | 34,233,672 | 34,395,984 |
7 | 181,641,900 | 527,164,524 | 529,630,188 | 532,753,872 |
8 | 2,657,392,800 | 8,000,790,798 | 8,072,006,754 | 8,134,286,034 |
9 | 99,376,027,356 | 341,738,424,810 | 345,842,146,422 | 346,017,781,674 |
Depth | Base+ML | Base+MP | Base+LP | Base+MLP |
---|---|---|---|---|
0 | 1 | 1 | 1 | 1 |
1 | 6 | 6 | 6 | 7 |
2 | 216 | 216 | 216 | 294 |
3 | 4,320 | 4,320 | 4,320 | 6,678 |
4 | 86,400 | 86,400 | 86,400 | 151,686 |
5 | 2,725,920 | 2,730,888 | 2,730,240 | 5,427,108 |
6 | 85,201,200 | 85,492,248 | 85,457,136 | 192,353,904 |
7 | 1,357,078,404 | 1,363,837,116 | 1,366,372,440 | 3,151,035,948 |
8 | 21,314,716,308 | 21,467,457,180 | 21,547,245,672 | 50,945,151,390 |
9 | 1,036,739,513,856 | 1,038,414,757,560 | 1,043,459,509,212 | 2,784,830,280,258 |
Note: Numbers in italics have not been independently verified.
Another important use for perft is to determine how quickly an engine can calculate the number of valid moves at any position. By timing how long it takes to calculate a perft result, one can do engine-to-engine performance comparisons, which is usually reported in thousands of nodes visited per second (KN/s), i.e. # of nodes / the time in milliseconds.
Results from MzingaPerft v0.12.9 on an AMD Ryzen 7 1700X (8 cores @ 3.40GHz) with 32GB RAM.
Depth | Base | Base+M | Base+L | Base+P |
---|---|---|---|---|
0 | 00:00:00.006 (0.2 KN/s) | 00:00:00.006 (0.2 KN/s) | 00:00:00.006 (0.2 KN/s) | 00:00:00.006 (0.2 KN/s) |
1 | 00:00:00.003 (1.3 KN/s) | 00:00:00.003 (1.7 KN/s) | 00:00:00.003 (1.7 KN/s) | 00:00:00.003 (1.7 KN/s) |
2 | 00:00:00.003 (32.0 KN/s) | 00:00:00.003 (50.0 KN/s) | 00:00:00.003 (50.0 KN/s) | 00:00:00.003 (50.0 KN/s) |
3 | 00:00:00.004 (360.0 KN/s) | 00:00:00.006 (435.0 KN/s) | 00:00:00.004 (652.5 KN/s) | 00:00:00.004 (652.5 KN/s) |
4 | 00:00:00.003 (7,200.0 KN/s) | 00:00:00.008 (5,676.8 KN/s) | 00:00:00.005 (9,082.8 KN/s) | 00:00:00.005 (9,082.8 KN/s) |
5 | 00:00:00.049 (10,535.5 KN/s) | 00:00:00.103 (12,163.1 KN/s) | 00:00:00.103 (12,163.1 KN/s) | 00:00:00.111 (11,314.7 KN/s) |
6 | 00:00:00.802 (15,236.3 KN/s) | 00:00:01.893 (18,084.2 KN/s) | 00:00:01.935 (17,691.8 KN/s) | 00:00:02.009 (17,120.9 KN/s) |
7 | 00:00:23.859 (7,613.1 KN/s) | 00:01:02.989 (8,369.2 KN/s) | 00:01:08.755 (7,703.2 KN/s) | 00:01:08.723 (7,752.2 KN/s) |
8 | 00:06:18.051 (7,029.2 KN/s) | 00:18:20.308 (7,271.4 KN/s) | 00:18:57.761 (7,094.6 KN/s) | 00:20:20.554 (6,664.4 KN/s) |
9 | 03:11:51.473 (8,632.8 KN/s) | 10:19:12.401 (9,198.3 KN/s) | 10:50:21.048 (8,863.0 KN/s) | 11:05:24.268 (8,666.9 KN/s) |
Depth | Base+ML | Base+MP | Base+LP | Base+MLP |
---|---|---|---|---|
0 | 00:00:00.006 (0.2 KN/s) | 00:00:00.006 (0.2 KN/s) | 00:00:00.006 (0.2 KN/s) | 00:00:00.006 (0.2 KN/s) |
1 | 00:00:00.003 (2.0 KN/s) | 00:00:00.003 (2.0 KN/s) | 00:00:00.003 (2.0 KN/s) | 00:00:00.003 (2.3 KN/s) |
2 | 00:00:00.004 (54.0 KN/s) | 00:00:00.004 (54.0 KN/s) | 00:00:00.004 (54.0 KN/s) | 00:00:00.004 (73.5 KN/s) |
3 | 00:00:00.004 (1,080.0 KN/s) | 00:00:00.004 (1,080.0 KN/s) | 00:00:00.004 (1,080.0 KN/s) | 00:00:00.004 (1,669.5 KN/s) |
4 | 00:00:00.009 (9,600.0 KN/s) | 00:00:00.010 (8,640.0 KN/s) | 00:00:00.009 (9,600.0 KN/s) | 00:00:00.014 (10,834.7 KN/s) |
5 | 00:00:00.206 (13,232.6 KN/s) | 00:00:00.212 (12,881.5 KN/s) | 00:00:00.196 (13,929.8 KN/s) | 00:00:00.325 (16,698.8 KN/s) |
6 | 00:00:04.349 (19,591.0 KN/s) | 00:00:04.535 (18,851.7 KN/s) | 00:00:04.489 (19,037.0 KN/s) | 00:00:09.716 (19,797.6 KN/s) |
7 | 00:02:40.616 (8,449.2 KN/s) | 00:02:49.430 (8,049.6 KN/s) | 00:02:54.094 (7,848.5 KN/s) | 00:06:25.217 (8,179.9 KN/s) |
8 | 00:48:21.657 (7,345.7 KN/s) | 00:51:03.763 (7,006.9 KN/s) | 00:51:32.991 (6,966.5 KN/s) | 01:57:58.621 (7,197.0 KN/s) |
9 | 30:58:20.189 (9,298.1 KN/s) | 32:36:48.907 (8,844.4 KN/s) | 32:34:13.669 (8,899.2 KN/s) | 85:38:11.591 (9,033.1 KN/s) |
Mzinga follows these rules when generating moves:
- The Queen Bee cannot be played on a player's first turn.
- If a player has multiple bugs of the same type in their hand, then only one is used to calculate the number of valid placements. I.e. if you have two ants in your hand, and five open positions to place a bug, you have five valid moves, not ten.
- A player can only Pass if there are no other legal moves, and then that Pass counts as one move for the purposes of calculating perft.
- When the game is over (one or both Queen Bees are surrounded), then the move generator should return 0 moves.
Mzinga Copyright © 2015-2023 Jon Thysell.
Hive Copyright © 2016 Gen42 Games.
Mzinga is in no way associated with or endorsed by Gen42 Games.
Getting Started
Mzinga's Projects
Other