Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Sharp 2015 Challenge paper
        
(Message started by: lightvector on Oct 3^rd, 2015, 4:09pm)

Title: Sharp 2015 Challenge paper
Post by lightvector on Oct 3^rd, 2015, 4:09pm

Paper published in the ICGA Journal!

Uploaded and openly available with permission from the journal:
http://icosahedral.net/downloads/djwu2015arimaa_color.pdf

Wu, D. (2015). Designing a Winning Arimaa Program. ICGA Journal, Vol. 38, No. 1, pp. 19-41.

I wonder what the 2016 CC (if it does happen) will look like :).

Title: Re: Sharp 2015 Challenge paper
Post by chessandgo on Oct 4^th, 2015, 10:51am

Congrats :)

Title: Re: Sharp 2015 Challenge paper
Post by Fritzlein on Oct 4^th, 2015, 11:48am

What an excellent paper to complement an excellent bot! Who knew that lightvector would be as accomplished at writing as he is at coding?

I would have guessed, before reading, that sharp's leap in strength did not have much to due with improved evaluation, but it seems evaluation improvements played a critical role. Probably a weaker player than lightvector would have had difficulty identifying and encapsulating the strategic flaws which he fixed. It is interesting how much (and what sort of) human domain expertise is necessary to create a machine expert.

The improvements to search are what I find most fascinating, in particular the innovations that allowed sharp to be more selective. It has been my intuition for some time that it would be important to do extensions/reductions on some basis other than static evaluation or even shallow evaluation. To my way of thinking some moves are "critical" for evaluating a position even if they look superficially bad, and these moves must be examined.

I am therefore delighted to read section 5.3. Lightvector calls the moves that deserve special attention "tactical" rather than critical, but the point is the same. Most moves can be left out of the deepest search without significantly impacting playing strength, but a few moves simply must be examined to greatest depth, and the method of choosing these moves is not superficial evaluation. I note that human domain knowledge was again required to craft this move selection heuristic.

Not only does this paper give a rich sampling of features that figured prominently in sharp's victory, it also leaves me with a sense of oceans of small-but-cumulatively-immense features that are not discussed. I am left to wonder whether it is possible that lightvector spent even more time developing sharp than I spent developing my human Arimaa expertise.

Congratulations, lightvector, on a well-earned, monumental accomplishment, and thank you for sharing your insights!

Title: Re: Sharp 2015 Challenge paper
Post by half_integer on Nov 7^th, 2015, 5:36pm

Who can add the link to the papers page of the Arimaa site? It obviously should be there.

Title: Re: Sharp 2015 Challenge paper
Post by Migi on Jan 22^nd, 2016, 10:34am

Thank you for sharing this well-written and very interesting paper, and congratulations on winning the challenge!

One question I had after reading it though is why you are using a simple "always-replace" scheme for the transposition table. With an always-replace scheme, it seems to me that you'll end up doing a lot of unnecessary recalculation. The nodes near the root will very frequently be overwritten by leaf-nodes, and every time that happens you'll have to re-visit that whole subtree again (with better alpha-beta bounds, sure, and some nodes will still be cached also, but still). Surely a slightly smarter replacement scheme could prevent a lot of this unnecessary recalculation, at a negligible cost (both memory and calculation)?

It just seems like such a low-hanging fruit. As you said yourself, it's the simplest replacement scheme there is, and this stands in very stark contrast with all the other heuristics in Sharp, which you've clearly spent massive amounts of work on, to great effect. So for this "low-hanging fruit", did you really not try any different replacement schemes, or did the things you tried all perform worse than the simple always-replace scheme?

_{(edit: spelling)}

Title: Re: Sharp 2015 Challenge paper
Post by lightvector on Jan 24^th, 2016, 10:04pm

Good question. I didn't try anything else yet, but my observation has been that there has been almost no improvement in performance or decrease in the number of nodes searched in sharp from increasing the size of the transposition table. One would expect that if the replacement scheme were important, simply making the table larger should also show an improvement, and it doesn't.

It makes sense - sharp's evaluation is very heavy. I forget more precise numbers, but order of magnitude wise, I think I get only 100k nodes/sec typically on a single thread, which means that if you have a table with, say, 1G entries (x16 bytes/entry = 16GB), you have on the order of 10000 cpu-seconds before a random entry in the table gets in expectation one write. Even with 10 threads that's about 16 minutes, and the CC time control is only 2 minutes/move. That's consistent with the observation that a bigger table only barely decreases #nodes searched to reach a given depth.

It could be a few percent improvement in average performance, so by far not the biggest issue, but certainly worth implementing and testing a different scheme for the next version.

Title: Re: Sharp 2015 Challenge paper
Post by knarl on Feb 7^th, 2016, 3:53am

Just wondering if any profiling has been done on the multithreading implementation? If there's any blocking going on, it would be interesting to port it to a non-blocking thread pool implementation...