Ik heb het met een graaf gedaan:
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| /* Codecup 2021 Zuniq competition program
*
* The program uses the board as a graph
*
* Vertices are the grid cells + "outside-the-board-border" cells
* Edges are the walls (perpendicular)
*
* Example: board grid of 4 x 3
*
* vertical edges horizontal edges
* (horizontal walls): (vertical walls):
*
* 1 2 3 4 1 2 3 4
*
* v0 v1 v2 v0 v1 v2
* A . | . | . | . A . . . .
* |e0 |e1 |e2 e9 e11 e13 e15
* v3 v4 v5 v6 v7 v3---v4---v5---v6---v7
* B . | . | . | . B . . . .
* |e3 |e4 |e5 e10 e12 e14 e16
* v8 v9 v10 v11 v12 v8---v9--v10--v11--v12
* C . | . | . | . C . . . .
* |e6 |e7 |e8
* v13 v14 v15 v13 v14 v15
*
* edge e0 is wall: A1h, e1: A2h, etc.
* edge e9 is wall: A1v, e10: B1v, etc.
*
* NOTE: The competition uses a 6 x 6 grid which has (5 * 6) + (6 * 5) = 60 walls (or perpendicular edges)
* lookup tables and structs are mostly uint64_t cramped with bit shifted values
* |
Achteraf zou 1 vertex voor alle "outside-the-board"-cells misschien makkelijker zijn, maar goed...
Daarbij zijn alle border edges: bridge-edges (of cut-edges).
Met zetten van muren (of in mijn geval weghalen van edges) controleer ik of er muren bijkomen die het veld in stukken kan knippen, of stukken afsluiten.
https://iq.opengenus.org/find-all-bridges-in-graph
Verder tel ik van elke edge (muur) hoeveel vertices (vakjes) er aan beide zijden zitten.
Dat inderdaad ook allemaal in 64bit.
Als een muur iets afsluit, heb ik alle andere "afsluit" edges met diezelfde waarde in een 64bit zitten, die worden dan ongeldig.
De hash
Voor het berekenen van een hashwaarde gebruik ik de zobrist hash methode
Wikipedia: Zobrist hashing
Elke edge (muur) is een zobrist, een voor de speler toggle, voor elke grootte (25) gesloten vak en een even/oneven "loose" toggle
Elke zet maakt die muur een fixed-state edge
Zoals PinjoTweaker ook al deed: muren in een gebied die zeker-te-weten-helemaal-nooit-meer geldig worden, krijgen ook de status fixed-state muur.
En de muren van al die losse afgebroken stukjes veld zijn vaak ook fixed-state met alleen dus een even/oneven aantal zetten toggle.
De hash bereken ik dan door steeds de nieuwe fixed-state edges en player / loose toggle te hashen (rolling hash)
De mcts tree:
Ik heb de tree zo gemaakt dat de edges daarvan mcts-"edgenodes" worden en de nodes mcts-"hashnodes"
De structuur blijft dan node->edge->node->edge->node
De edgenodes zijn je zetten en bevatten de zet en stats (lokaal), de hashnodes zijn je nodes en bevatten ook stats (overall), maar zitten in een hashtabel
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| - EN WEER TREE TRANSPOSITION IDEE
____ move
| | #sim
32 bytes|node| #win EIGENLIJK IS DIT DE EDGE
(25) |____| *next_sibling
| *zobrist_node
|
_____V_____ hash
| | #sim
| zobrist | #win
48byte| hash | *first child
(45) | node | *last child
| | unexplored_moves
|___________| winner, player, child_count,
/ \ child_game_over_count, child_expansion_count
/ \
/ \
__/_ ____ _\__
| | | | | |
|node|->|node|->|node|
}____| }____| }____| |
Allemaal heel mooi en aardig:
Met 2 miljoen edgenodes en een hashtable van 999983 (priem) hashnodes had ik al meer dan genoeg nodes voor het spel op de competitie server. (grofweg 115MB)
Hierbij zit ook Garbage Collection die gegarandeerd alleen oude / onnodige hashes en nodes laat overschrijven (eerdere en/of andere moves)
Het board
Het board zelf gebruikt bij mij iets meer dan 2kB, die moet ik bij elke zet opnieuw berekenen. Dat verklaart dus mijn "laag" aantal simruns/sec (29K) bij leeg bord.
Die grootte komt grotendeels, omdat ik van alle 60 muren 2x (beide zijden) een "graaf" heb met muren die via de vakjes nog bereikt kunnen worden (120x struct(64bit + nog wat chars) = 16bytes * 120= 1920 bytes)
Dat zou ook dynamisch moeten kunnen, omdat er per zet steeds minder overblijven.
Dat zou ik dan voor de betere zetten / tot bepaalde diepte nog in een of andere cache achtige structuur kunnen stouwen (nog ongeveer 140MB over) Volgens mij heb ik daar iets van Boreus over gelezen met wat in c++ een map heet?
Hmm, goed idee! Dat kan ik voor de volgende testcompetie... Oh wait...
-edit- wacht eens even, ik heb dat eigenlijk al gemaakt voor de mcts hashnodes (Open addressing variant). Waarom valt dat kwartje nu pas!?
Het spel: tijden, victory claim, agressiviteit
Als ik begin, gebruikte ik
0.9 + 0.08 * round seconde tijd
Tot round / depth 13 sla ik alle randmuren over als het mijn beurt was (in de mcts-tree) Dat is natte vinger pruning geweest.
Bij stat >= 50% op of na round 19, claim ik de winst. (3 x misgegokt)
Meestal vind die zelf de endstate tussen ronde 25 en 31. (107 - 104), meestal 29 (105)
Als ik als laatste begin, gebruikte ik
0.07 * round seconde voor de eerste 9 zetten (18 rounds) en
5.5 - 0.25 * (round - 20) voor de 2de helft.
Bij stat >= 62% winst op of na round 20 -> victory claim (1x misgegokt)
Daar is de endstate tussen round 24 - 32, meestal round 30 (105)
De c waarde bij de mcts-tree heb ik op
0.5 + child_game_over_count / child_count gezet. Het idee was om sneller breed te gaan als de hashnode (overall) slechter blijkt. Maar dat was bijna altijd te laat om nog effect te hebben.
Lang verhaal kort: ik heb weer enorm veel geleerd!
Met een extra hashtable met board positions, had ik mogelijk tijdwinst kunnen halen.
Met halverwege al 100000-en runs moet dat wel sneller zijn, dan steeds elke keer bij alle zetten het board bij te werken. Dat wordt dan eens uitzoeken welke hashtable variant ook bij een hoge load factor nog presteert
Wikipedia: Hash table
Gecombineerd met de tip van PinjoTweaker: bij expansion nog niet in de cache, maar pas bij de eerste keer dat de zet bij een selection wordt gekozen (2de simulatie)
[
Voor 22% gewijzigd door
Vaan Banaan op 24-01-2021 14:11
]
/u/22274/banaan60x60.png?f=community)
:fill(white):strip_exif()/f/image/MzJXnHNqIIauPUGCZwGn5AIL.png?f=user_large)
:fill(white):strip_exif()/f/image/KmTpSwWmczIfuKQluiG1qp5u.png)
:fill(white):strip_exif()/f/image/ajgdSrmCwj4lm7ZAiHJJWV8F.png)
:fill(white):strip_exif()/f/image/R6oQyDmtAV1P4bkOWlUVZ8VG.png)
:fill(white):strip_exif()/f/image/Kp3RduXsZcfTRw54Ul70uwE5.png)
:strip_exif()/u/68919/logoblad.gif?f=community)
:strip_icc():strip_exif()/u/58343/Turtle.jpg?f=community)
:fill(white):strip_exif()/f/image/RZzpMPp64Ci5IuQenFqyPUMh.png?f=user_large)
) en weer maar 1 als ik als laatste moest.
