[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] An [open] question on game tree search theory
Hi Antti and others,
I think that's a very interesting problem.
If E is just a random number attached to every node in the tree, search is
meaningless---any min-max value over the tree is just a min-max value of
random numbers, and hence worthless.
Actually, min-max value of random numbers would not be totally worthless. It
would favour lines of play where black has more options and white fewer and
thus improve over making random moves (in many games).
For example, in chess E reflects usually among other things material balance.
There is probably even a (conjencture level) fact that positions with
material balance favoring white are statistically more probably
game-theoretic wins for white than those positions where material balance
favors black. This would be a mathematical link between E and G. Higher
values of E would yield game-theoretic win for white (in case of chess) with
higher probability in a strict statistical sense. Does min-maxifying keep and
strengthen this effect? Why? Someone probably knows this. And, is there a way
to measure the effect or verify it algorithmically?
Measuring the effect should be straightforward if you know the G values.
Perhaps the most interesting case where G is available, is a chess endgame
database. I don't know whether anyone has studied that. Machine learning with a
chess endgame database is probably quite common, for instance a student project
is proposed at http://www.informatik.uni-freiburg.de/~ml/jobs.html
I am interested in playout analysis, that is, playing the game stochastically
to the end from the current position, and analysing the statistics. This gives
another type of a heuristic which could be compared to E.
http://www.cis.hut.fi/praiko/go81/go_step.pdf
Regards,
--
Tapani Raiko, <tapani.raiko@xxxxxxxxxxxxxxxxx>, +358 50 5225750,
http://www.hut.fi/u/praiko/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/