2
$\begingroup$

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.

Board example, each green line represents a possible position of the car

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.

$\endgroup$
2
$\begingroup$

I think a search tree can be used to solve this problem, but I'm not sure that is the right way to go.

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.)

After building the state machine, you need to simulate it to find if the winning state is reachable. If so, the path that reaches that state is the solution to your game. Since the total "depth" of your state machine is small, running any reasonable path-finding algorithm would do.

$\endgroup$
2
  • $\begingroup$ Thank you! Approaching the problem as a FSM didn't cross my mind. That actually solve several doubts I had about the board representation. Will be experimenting with this idea for the following days, thanks again. $\endgroup$ Aug 24 at 18:44
  • 1
    $\begingroup$ @spurdosparde if you also want to include randomness in your game, then consider converting it to an MDP (markov descision process) instead, and apply some reinforcement learning technique (Q-learning for example) $\endgroup$
    – nir shahar
    Aug 25 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.