Talk:Game tree

Old talk

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)

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)

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

Article cleanup

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.

No consensus to merge. Felix QW (talk) 19:01, 5 April 2022 (UTC)

---

I added a short lead section. The article also contains a section on solving game trees, which I believe is out of the scope of this article. Since many of the articles regarding the algorithms link to this article, it would be better to turn this article into one that is focused on defining what a game tree is and merging the solving section with their respective articles. The section should still be kept, but cleaned and shortened so as to provide only as short summary and linking to the respective main articles. Fffffgggg54 (talk) 05:02, 29 June 2021 (UTC)

I proposed merging or deleting the Solving game trees section with their respective articles. I added 2 sentences in the lead section that link to the articles for the methods mentioned in the solving section. Fffffgggg54 (talk) 05:38, 29 June 2021 (UTC)

Oppose merge: I can't see that a case has been made, nor can I imaging one. What was needed was to just link randomized algorithm and deterministic algorithm, which I have now done. Klbrain (talk) 22:01, 25 October 2021 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

India Education Program course assignment

This article was 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.

The above message was substituted from {{IEP assignment}} by PrimeBOT (talk) on 19:57, 1 February 2023 (UTC)

Unclear step in deterministic algorithm

I don't understand the wording of this step in the deterministic algorithm:

Look at the next ply up. If there exists a node colored opposite as the current player, color this node for that player as well. If all immediately lower nodes are colored for the same player, color this node for the same player as well. Otherwise, color this node a tie.

Could someone who knows the algorithm better than I do consider rewording the step if you agree it is unclear? Espertus (talk) 16:16, 4 April 2023 (UTC)