Quoting Brian Sheppard <[email protected]>:
Can you clarify: does Valkyria always do its tree search in iterations where
the tree is deleted between iterations, and the length of the iterations
increases exponentially between iterations?
No, I only do the iterations for long searches for 9x9 games on Little
Golem. See:
http://www.littlegolem.net/jsp/info/player.jsp?plid=22065
since the games are slow and can have the Valkyria searching a
position for up to 1 Billion playouts. I could do even more by
restarting the search manually and just use the hash table.
On CGOS the search is pretty standard MCTS, but all nodes are stored
in a permanent hash table with 4 million entries. So when a position
comes up often the single search will reuse entries of old searches,
but entries that were not searched deeply are quickly overwritten.
Maybe I will try out iterative deepening on CGOS. I once used in a KGS
tournament but had very bad results because all the new things i tried
made Valkyria weaker. And I then thought the iterative deepening was a
major problem.
I have changed the algorithm since then but I still thinks it is crude
and unlikely to be effective for search with time limits.
If so, then I am curious: how does that differ from periodically resetting
the W/L counters at a node?
If you would just reset the W/L counters I think the program would end
up doing garbage collect of almost all nodes in the tree anyway before
they are researched since I search most positions on Little Golem
games for about 12 hours. The hit rates in researching the trees are
quite low compared to the number of nodes visited.
All nodes remain in memory, it is only the links that are changed. So
it is not costly to delete the tree. And when a node is deleted the
best move is stored in the hash table if it has been search enough
times and has a win rate higher than a threshold.
Valkyria garbage collects about 20% of all nodes every time it runs
out of memory. It then removes the nodes with the oldest visit
timestamps. This only rarely happens for games played on CGOS when a
series of ponder hits leads to keep most of the tree after each
opponent move. Garbage collection is not super complicated but one has
to be careful of transpositions. The Valkyria tree is not a pure tree,
because a node can have several parents if more than one sequence
leads to a position.
Best
Magnus
In Pebbles I was just saving moves when nodes were recycled.
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of [email protected]
Sent: Friday, July 08, 2011 3:09 AM
To: [email protected]
Subject: Re: [Computer-go] Congratulations to Zen!
I tried Valkyria with the iterative deepening on this position and
with the help of the best move hash table it basically solves it.
After 1001 playouts win rate is 24.6%
At iteration 6 and total 36857 playouts win rate drops to 4.8% and
when I stopped search win rate was 0.2%.
It searched doing 2400 playouts per second.
This means that playouts has trouble evaluating this initially
although it is clear the position is one sided.
Only winning moves are stored in the hash table (since the losing side
will search many moves in lost positions anyway I do not see any
benefit of storing best losing moves in the table so there is a win
rate threshold for that).
Remember that for each iteration the tree is deleted so this is a
really nice demonstration that the hash table works well when a
position is researched and it is a hard one for the playouts.
.
..0.. <e9/246/528> Hits: 0 1001/1001 Misses: 601
..1.. <e9/281/965> Hits: 38 1275/2276 Misses: 761
..2.. <e9/156/1186> Hits: 69 2268/4544 Misses: 1381
..3.. <e9/126/3560> Hits: 127 4289/8833 Misses: 2541
..4.. <e9/149/7675> Hits: 259 8579/17412 Misses: 5174
..5.. <e9/122/7656> Hits: 253 8580/25992 Misses: 5189
..6.. <e9/48/6604> Hits: 332 10865/36857 Misses: 6641
..7.. <e9/45/11410> Hits: 635 20675/57532 Misses: 12701
..8.. <e9/21/25080> Hits: 926 30808/88340 Misses: 18521
..9.. <e9/14/38822> Hits: 1498 49663/138003 Misses: 29961
..10.. <j7/43/44784> Hits: 1410 49664/187667 Misses: 30421
..11.. <e9/10/66987> Hits: 2425 80515/268182 Misses: 48501
..12.. <j7/11/93257> Hits: 4400 145501/413683 Misses: 88001
..13.. <j7/7/66607> Hits: 4535 153352/567035 Misses: 90701
..14.. <e9/3/121875> Hits: 5765 193986/761021 Misses: 115301
18 PLY VAR B j7 W g8 B e9 W h2 B f7 W g4 B f9 W a6 B a5 W a4 B a7 W a5
B f2 W h1 B c3 W c2 B g2 W e1
Best
Magnus
Quoting Ingo Althöfer <[email protected]>:
"Aja" <[email protected]>
ManyFaces (White) still wins even if it loses the semeai but captures
the J4 group of 3 stones. And it's not possible for Black to save the
J4 group and win the semeai at the same time.
Yes, that is exactly what the experts in the forum found.
The question: Do the other bots see this as well,
and how early in the game do they see this outcome?
Ingo.
--
Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir
belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
