|WikiProject Games||(Rated Start-class, Mid-importance)|
|WikiProject Computer science||(Rated Start-class, Mid-importance)|
|This article is the subject of an educational assignment at College Of Engineering Pune supported by Wikipedia Ambassadors through the India Education Program during the 2011 Q3 term. Further details are available on the course page.|
why the average branching factor of the chess search tree is 35 ?
"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)
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)
Game trees are not trees according to graph theory?
The article states a game tree is a directed graph, whereas trees in graph theory are undirected graphs (with additional features). Is there an explanation why game trees are not trees in graph theoretic sense? 188.8.131.52 (talk) 12:26, 15 August 2010 (UTC)