Barcelona 2002 Colloquium

--{ Barcelona 2002 }--

Who we are
Friend sites
Research notes

Board Games in Academia V


Tristan Cazenave

Comparative evaluation of strategies based on the value of direct threats

Taking into account the value of threats is not standard in computer Go programs. Many strategies can be used to take the value of threats into account. We made some experiments to compare relevant strategies. The value of five subgames are randomly chosen, and the strategies play in these independent subgames. Each subgame has four leaves: one leave after two Left moves, one after a Left-Right combination, one after Right-Left and one after Right-Right. A brute force approach tries all possible moves. It is time consuming, but it finds the best move. An approach that does not take threats into account will play the best move, only taking into account the opponent local answer. We call it MaxMove. An approach based on the notion of sente classifies a move as sente when the value of the threat associated to the move is greater than the value of the best move. We have tested two strategies based on sente. Sente multiplies by 4 the value of double sente moves, and by two the sente moves. SenteQ always choose double sente moves first, then sente moves, then gote moves. The MaxThreat strategy select the best subgame by comparing subgames taking threats into account. And finally we also used the ThermoStrat and the HotStrat strategies as defined by Berlekamp. Experimental results show that Thermostrat is optimal in practice, just followed by HotStrat which is easier to implement. MaxMove scores 93% of Optimal.

[ Home Page | Journal | Colloquia | Who we are | Friend Sites | Research Notes | Search ]