Talk:Game tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Games (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Games, a collaborative effort to improve the coverage of game related topics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Old talk[edit]

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

"Solving" Game trees[edit]

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)

Non-merge issues[edit]

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?[edit]

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? 217.229.13.214 (talk) 12:26, 15 August 2010 (UTC)