Talk:Game tree

From Wikipedia, the free encyclopedia

why the average branching factor of the chess search tree is 35  ?

[edit] "Solving" Game trees

Somewhere, and I regret to say I no longer recall where, I saw an algorithm for solving game trees assuming that you have the full tree available to you. It had something to do with coloring nodes, starting at the bottom depending on whether the game ended in a win for a, win for b, or a draw, and then moving up the tree coloring more nodes depending on the colors of the nodes below it. A tree was then marked as solvable for a or b depending on whether the very top of the tree got to be colored one or the other, meaning that there was a garaunteed path to victory for either a or b (or a garaunteed draw).

I came here because I was hoping to find the details of this algorithm, since I can't seem to find it anywhere now, and I don't remember the exact process of coloring the next level up on the tree after you've colored the bottom layer. Can anyone help? Or if there is already an article on this topic elsewhere, could you point me to it? I've been searching for the longest time... Fieari 21:52, 2 May 2005 (UTC)

Found it! And just added it. Fieari 02:02, May 30, 2005 (UTC)

A reference would be handy. Pete.Hurd 01:06, 23 August 2006 (UTC)

[edit] Non-merge issues

Given the decision not to merge this page with extensive form game I suggest changing the first sentence from "In game theory, a game tree..." to "In computer science, a game tree..." since the formal game theory equivalent is the extensive form, but this concept seems different from the the topic presented here (for example extensive form games can have information sets which preclude the backwards induction solution presented here). Pete.Hurd 02:55, 23 August 2006 (UTC)