search

skotz / volcanoes

Prototype for a new board game
4 stars 1 forks source link

Opening books #24

Closed skotz closed 3 years ago

skotz commented 5 years ago

Precompute opening books

skotz commented 4 years ago

Meh

simondorfman commented 3 years ago

@skotz I know you closed this with a "Meh" previously, but maybe this new virtual overlay screenshot will inspire you:

opening analysis looks like A sides are better

I left this running for a few hours on an empty board and it looks to me like the "A" tiles may be stronger for the opening than the B, C, & D tiles. Not by much. But still, I'm curious to see what the AI would come up with if I left it running for long enough...

skotz commented 3 years ago

Cool

skotz commented 3 years ago

@simondorfman

I implemented a basic opening book generated by precomputing the best moves for the first 7 moves of the game. The calculation is done using the normal MCTS engine running for 60 seconds. There are currently 12,643 lines in the book which is enough to cover every possible position 7 moves deep (including growth turns).

The results of a 5 second per move tournament aren't earth shattering, but it did win. I'll create a v0.5.4 download with the book lines.

image

It took 3.5 hours to generate the depth-7 book at 60 seconds per position, so you can figure that a 600 seconds-per-position book at the same depth would take about 35 hours.

What I'd like to do in the future is find a way to determine which lines after the depth-7 books are worth precomputing (like only the critical lines) so that we don't have to precompute 160 million positions to go deeper.

simondorfman commented 3 years ago

@skotz this is super-interesting! I tried a couple of short tournaments. Running a longer tournament overnight too. I'm surprised that its opening move is N18, which is not an "A" tile.

Playing itself, the first 7 moves are all the same, which makes sense, since it's playing by a book. But it also mostly plays the same against itself for all the moves after number 7 too. Two exceptions out of 10 games: image

simondorfman commented 3 years ago

Is there any way I could compute the opening book with longer think times? I’m really curious to see what it comes up with.

skotz commented 3 years ago

Yeah. Right now it's hard coded to 60 seconds and doesn't give any progress indication, but I can change that. I'm very interested in generating a stronger book.

I'm also messing around with a hashing strategy that might speed up search speeds.

skotz commented 3 years ago

Coming soon (in the CTRL+D DEBUG menu).

image

skotz commented 3 years ago

Added this to v0.5.5. Please send any books generated over 60 seconds my way please.

You may need to run this outside of the Programs folder (like copy the files to a folder on the desktop instead of running it from the installed location) since it directly modifies a file in that location.

Also, I added several MCTS variations that use hashing, opening books, and fast win searching. The "trio" version uses all three. Initial tests seem like they could be quite strong. Let me know the results from any longer tournaments you happen to run.

simondorfman commented 3 years ago

Sweet!

I kicked off a 600 seconds book generation. Will post it here when it finishes.

simondorfman commented 3 years ago

Needed the computer for something else so had to cancel it. Will restart it again later.

Did a simulation on other computer and the new AIs are looking very strong:

2020-12-02 18_11_39-tourney-table-20201202010011 csv - Excel 2020-12-02 00_59_11-Volcanoes - Tournament
skotz commented 3 years ago

Unfortunately I think there's a bug with my hashing again... If you open the list of games for that tournament you'll see a lot of time adjudications. My theory is that it's running out of memory.

On Wed, Dec 2, 2020 at 6:12 PM Simon Dorfman notifications@github.com wrote:

Needed the computer for something else so had to cancel it. Will restart it again later.

Did a simulation on other computer and the new AIs are looking very strong: [image: 2020-12-02 18_11_39-tourney-table-20201202010011 csv - Excel] https://user-images.githubusercontent.com/106923/100946874-edf10a80-34c9-11eb-9eb7-31d251c05031.png [image: 2020-12-02 00_59_11-Volcanoes - Tournament] https://user-images.githubusercontent.com/106923/100946882-f21d2800-34c9-11eb-9d82-431d1776a4a6.png

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/skotz/volcanoes/issues/24#issuecomment-737573084, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACXRNXSWXRAWMHN6WZ2YOV3SS3JYPANCNFSM4GOSYELA .

simondorfman commented 3 years ago

Yeah, I see what you mean, 43 of 250 are AdjudicateTime. I'll see if I can verify memory is the issue. Maybe I can monitor memory while it's running somehow...

skotz commented 3 years ago

And unfortunately I'm treating timeouts as draws instead of declaring the last player to move (whoever didn't time out) the winner, so it's not a great representation of the results. I think I might have a fix. Need to test.

skotz commented 3 years ago

Fixed timeouts so that it's a win for the last player to move instead of a draw. Fixed tournament timeout calculations so that it doesn't let some engines think for way longer than they should while others only get to think for a fraction of their time before being declared a loser.

simondorfman commented 3 years ago

openings.dat.zip @skotz here's the opening book I generated with 600 seconds.