# Building a game tree from a board game

Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge. The goal of this game is being able to survive a certain number of turns (25) without running out of gas or food (starting with 100 gas and 50 food), the score depends on how filled this two gauges are (from 1 to 100, 0 is game over). Every turn these gauges loss a set amount (-10 for gas, -5 for food), but across the board there are nodes where these gauges can be replenished by a set amount (+100 for gas, +40 for food), after using a node, it will become unavailable for a set amount of turns (10 turns), using a node also counts as a turn, so the gauges are reduced.

I've been reading about game trees to represent two-player games and how they're used for Go, Chess and others, but aside not being able to find information about single player games, one big question popped in my mind. "How can I build a tree from a board game like this?"

I would be really grateful if you could point me towards books or papers that could teach me how to build a tree for this purpose, my only clue is the max depth can be 25 at most, was also thinking about graphs, but in all honestly, I'm completely lost on how can I generate a tree from any random board this game can have.

Thank you.

I think it makes more sense to model the game as a finite state machine. Properties of your board would be part of the "state", such as your current food and gas and position on the game board. What happens after each valid move would be a transition in this state machine. Extending the state machine with some "dynamic" transitions could be useful, such as "advance a turn unless food or gas is $$\leq0$$" (this allows you to build the state machine purely with the knowledge of the locations.)