Is there a way to represent a turn based game, with a finite, discrete number of moves, as a graph?

Is there a way to represent a turn based game, with a finite, discrete number of moves, as a graph?

Or what other forms of analysis can you use?

Let's use a mini version of the connect 4 board as an example. Say it is 3 columns by 5 rows, rules are that each player can pick x:{1,2,3} and that assigns them the coordinate (x,y) where y is the minimum y:{1,...,5} such that (x,y) does not already exist (just think about regular connect 4 rules if that confused you, the pieces stack on each other).

I enjoy turn based games, but I don't know a good way to analyze decision trees for them.

...

...

yes, in your example each move can simply described by the x-coordinate.

So a game can be described as a tuple (x1,x2,x3,x4,x5,x6,x7,...,xn) where the first player choses the odd components and the second player the even components.

A condition for admissible sequences is that the number of entries for each x is at most 5.

So you can describe all possible moves from a given sequence by adding a component say x(n+1) and assigning it any possible value.

...

...

...

...

>Is there a way to represent a turn based game, with a finite, discrete number of moves, as a graph?
my first year compsci class touched a bit on this in a homework assignment, this may be the naive answer.
any game as you described could be represented by a (most likely computationally impossibly huge) tree. if you knew the rules of the game and had infinite computer, you could just build the entire tree and
minmax on the assumption that your opponent will play perfectly. it's recursive because you try to assign a score to every node in the graph
large games are computationally infeasible to do this on, and there are algorithms to prune branches out of the tree to save computation time

for connect 4 in particular the brute force naive solution would just be to construct a massive game tree and ab-minmax it out. too lazy/unfamiliar to think of a better solution right now

fake

...

The naive way would be to represent it as a DAG with every valid board layout as a node with edges connecting nodes that can be moved between with valid moves

...

...

user sequences of moves don't matter for this game, only board state. You can represent the state of the game as

struct State
{
Empty = 0,
Red,
Green
}

class Board
{
public:
constexpr std::uint32_t sizeX = 7;
constexpr std::uint32_t sizeY = 6;
State state[sizeX][sizeY];
std::char columnSize[sizeX];

};

You can then define feature extraction methods such as >NumEmptyColums()
>NumRedTopColums()
>NumGreenTopColumns()

Things like this, and you can reason based on this.

I fuckinh hat e sci

...

Just GIVE UP

...

...

...

2 e c

...

...

...

You may want to check out also.

...

you're officially fucked now, all we need to do now is fill up the most left collom and we'll either have 4 in a row at the 4th or 5th circle

connect 4 is a solved game. if you go first you win

WHY WHY WHY WHY. Far right would have been best

We could have had them. We could have beat the green. But no, "No", says you. "I WANT TO LOSE" you scream.

how would we win from placing it on the far right?

the thing is, people can't look that far ahead in the future

he would have made it a very light red so our opponent wouldnt have seen it in his peripheral vision

a sneak attack, if you will

...

...

...

You lost.

Today on Veeky Forums I watched a game of Connect 4 play out. What a great use of my time.

>there are algorithms to prune branches out of the tree to save computation time
yes, if you have defined a heuristic, then branches that start with the worst scores can be ignored as long as other branches exist with better scores--or in some cases can be deleted altogether. the heuristic itself presents a time/space tradeoff. too simple and more space must be used. too complicated, and more time must be used.

>constexpr std::uint32_t sizeX = 7;
sepples babby

...