What is a State Graph?
A state graph of a game is a directed graph of nodes, where each node represents a state in the game and transitions are represented in the form of directed edges. All the states of the game can be represented with the help of a state graph, where the node which does not have any outgoing edge states that there are no moves left after this state and the game ends here.
If all the outgoing edges from the current node(or state) leads to winning nodes, then this node is a losing node. Else if there is at least a single outgoing edge to a losing state, then the current state is a winning state.
Winning and Losing States for Competitive Programming
In Competitive Programming, we often encounter problems where two players are playing a game optimally and we need to find the winner of the game. In order to solve such problems, we should have a clear understanding of Winning and Losing states of the game. In this article, we will go through the basics of Winning and Losing States and how to identify them using State Graph.
Table of Content
- Understanding Winning and Losing States
- What is a State Graph?
- Example of Winning and Losing States: The Ball Game
Contact Us