Talk:Game tree

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Strategy games, an effort by several users to improve Wikipedia articles on strategy games. For more information, visit the project page, where you can join the project and/or contribute to the discussion.	Portal
Start	This article has been rated as start-Class on the assessment scale.
Mid	This article is on a subject of mid priority within strategy games for inclusion in Wikipedia 1.0.
Strategy games To-do: edit  Create: Close Combat: The Russian Front • Close Combat: Battle of the Bulge • Close Combat: Invasion Normandy Expand: HeroQuest (board game) • Boku (game) • Qubic • Death Stacks • Entropy (board game) • Fitchneal • Five Field Kono Copyedit: Crossings (game) • Gonnect • Quoridor • Company of Heroes • Dark Reign • Myth (computer game) Cleanup: Abalone (board game) • Battle Realms • Outlive • Stronghold (2001 game) • Fleet Command • Combat Mission (computer game series) • Diplomacy (game) Cite Sources: Colonization (computer game) • MacHack (chess) Update: List of strategy video games More...

[edit] Old talk

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)