13 replies to this topic

[timothyjlaird]

The goal in my clone of the game "Hex" is to occupy a contiguous chain of hex spaces in your color from one side of the board to the opposing side before your opponent does the same (see board below).

My problem is that I am not sure how to detect end of game without using brute force. I'm storing the state of all the hex spaces in both a single and two dimensional array (where each array position is an integer and 0=unoccupied, 1=player 1, 2=player 2). The only algorithm I can think of to check if the game is ended is to go through each hex on the left side of the board, check all adjacent hexes to the right and see if they are occupied in the same color...if so move one hex to the right and repeat until either I am out of adjacent hex spaces with the same color or the board ends. Then do the same for the other player's color. Is there a better way to do this?

[Trienco]

You can always go with a standard depth-first or A* search (for which the distance to the other edge -width - x- is the heuristic and the goal state is x = width - 1).

Your approach of only moving right would most likely fail as soon as the path needs to loop around opposing players cells and actually has to move left.

[timothyjlaird]

You can always go with a standard depth-first or A* search (for which the distance to the other edge -width - x- is the heuristic and the goal state is x = width - 1).

Your approach of only moving right would most likely fail as soon as the path needs to loop around opposing players cells and actually has to move left.

Yeah I thought about it last night and it would fail. I suppose the first step is building a tree (or graph) for each occupied red hex on the furthest left of the board one at a time (for red at least). Then walk the tree for each instance and see if it ever reaches opposing side of the board. Any reason why that would not work?

[Brother Bob]

It works, but you have some unnecessary logic in your method. Just building the tree is enough; if you even add an end-node to the tree, you have reached the other side. Since you don't have to store the tree for later traversal, you can effectively build and traverse it at the same time, without explicitly storing it, using recursion. It should be easy enough to start at any one hex and to recursively check all its unvisited neighbors; if you ever reach an end hex, you have a complete path from the starting side to the end side.

It is important to keep track of visited and unvisited nodes when recursing to not get stuck in loops. If the game allows multiple starting points, you have to check all of them in case they are not connected.

Pseudo code:

bool check(currentHex) {
    if(isEndHex(currentHex)) {
	    return true;
    }

    for neighbor=each neighbor of currentHex {
	    setVisited(neighbor);
	    bool res = check(neighbor)
	    resetVisited(neighbor);

	    if(res == true) {
		    return true;
	    }
    }

    return false;
}

I hope I got the logic correct. You should call check() for all starting hexes and it should return true if the hex has a path to an end hex.

[CyberRascal]

Since the only way a game can be ended is when placing a marker at a position, so each time a hex is marked, do a breadth first search until there are no more connected positions of the same color, or two different end positions are found.

I'm at a lecture, writing on my phone, so sorry if I'm terse. Anyone see anything wrong with my approach?

[CyberRascal]

The above is o(n) with n = nodes in connected graph.

At each placement, you could instead cache the connected end nodes to that position. You could then just check if the neighbours have any elements connected to end nodes. Constant time end-game check at each placement.

[Sandman]

At each placement, you could instead cache the connected end nodes to that position. You could then just check if the neighbours have any elements connected to end nodes. Constant time end-game check at each placement.

Not exactly constant, as a new placement may cause another tile that was previously not connected to either side to become connected - thus requiring those nodes to be checked, and their neighbours to be checked...

So worst case, it's still linear time. But the average/best case performance would be better.

[EpicWally]

I think A* is a good place to start, but since you don't really care what the shortest way across is (only that there is a complete path across) it could be somewhat simplified (you don't need any heuristic values, parents, distances, or anything like that.) Have each hex have a list of hexes called neighbors. Then, when a hex is set to a player, have it check the six hexes around it to see if they are set to the same player, and if so, add that hex to its neighbor list, and add itself to that hex's neighbor list. Then, for the check win condition, have it add the most recently added hex to an open list. Then take the first hex in your open list, move it to the closed list, and have it add all of its neighbors not already in the open or closed list to the open list, and repeat. When it is done, it will have a list (closed) of everything in the chain connected to the most recently placed tile. You can then quickly search that chain to see if it has a tile at the x=0 and a tile at the x=10 (or whatever your coordinates are) and if it finds both in that list, it knows it's a win. If not, it clears the lists, and passes the turn.

[timothyjlaird]

Based on the responses I think I have an algorithm worked out.

Let there be one master list for each player. Each of these master lists contains one or more lists of contiguous hex spaces.

Each hex space will store array positions for all possible adjacent hexes (<=6).

So when a hex for a player is added...
1. If this is the first ever hex to be added for a player, add a new list to the master list and put that hex in it.
2. Walk through the array of possible adjacent hexes for the newly added hex. Check those array positions to see if it is occupied by the same player. If there is a match, assume it is contiguous and add the matched adjacent hex to the list of contiguous hexes the newly added hex is on. If a newly added hex has no adjacent matches, add a new list to the master list and put it in there.
3. Loop through all of the lists in the master list, check for adjacencies and collapse the two lists being compared if a match is found.
4. Check each list of contiguous hexes in the master list to see if there are two hexes from opposite sides of the board. If they are found, the game is over.

So in this example there would be two master lists, one for red and one for blue. Red has one list of contiguous hex spaces and blue has four.



I know this algorithm isn't very elegant...that aside, can anyone find a case where it would not work? I'm very new to this path logic stuff and this the best I could wrap my head around.

I appreciate all the help so far with this! I'll post code somewhere when it is done.

Edited by timothyjlaird, 06 September 2012 - 09:24 PM.

[Sandman]

Sounds like it should work, but it also sounds a bit overcomplicated, with lots of needless hunting around in lists.

You don't need to maintain giant lists of lists. If you are familiar with recursion you can write a pretty simple function to do the test.

Ropey Pseudocode:

bool ConnectsToEdge(Edge edgeToCheck, Hex currentHex, Player player)
{
	for each neighbourHex
	{
		if(neighbourHex.IsOwnedByPlayer(player))
		{
			if neighbourHex.IsEdgeHex(edgeToCheck)
				return true
			else
				if ConnectsToEdge(edgeToCheck, neighbourHex, player)
					return true
		}
	}
	return false
}

Edited by Sandman, 07 September 2012 - 05:14 AM.

[EpicWally]

I agree with Sandman. There's really no reason to keep a list of all chains. When a tile is placed, the only possible winning chain must contain that new tile. Otherwise the game would have been won already. So, you only need to build the chain around the more recently placed tile, and check that chain each turn. Anything not part of this chain is completely irrelevant to the calculation, so why save it and check it?

[jrh2365]

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/01union-find.pdf

Here are some slides with a couple algorithms that would work. As shown in slide 23, Weighted Quick-Union would probably be the best choice, handling both the creation of new connections and the testing of whether nodes are connected in lg N time.

Some more details are available here: http://algs4.cs.princeton.edu/15uf/, and a Java implementation of Weighted Quick-Union can be found on that page under Creative Problems. (direct link http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html)

If you were choose this approach (it might be overkill?) then some tips:

• You would use 2 weighted quick-union structures, one for each player.
• Instead of needing to check the connectivity of every node on the left with every node on the right, you could create 2 "virtual" nodes - one on each side. You connect every node on the left to the first virtual node, and every node on the right to the second virtual node. Then you can quickly check if the player has won by checking if the 2 virtual nodes are connected.

[timothyjlaird]

Sounds like it should work, but it also sounds a bit overcomplicated, with lots of needless hunting around in lists.

You don't need to maintain giant lists of lists. If you are familiar with recursion you can write a pretty simple function to do the test.

Ropey Pseudocode:

bool ConnectsToEdge(Edge edgeToCheck, Hex currentHex, Player player)
{
	 for each neighbourHex
	{
		if(neighbourHex.IsOwnedByPlayer(player))
		{
			if neighbourHex.IsEdgeHex(edgeToCheck)
				return true
			else
				if ConnectsToEdge(edgeToCheck, neighbourHex, player)
					return true
		}
	}
	return false
}

I tried to implement it and it results in an infinite loop...maybe I'm misunderstanding the psuedo-code somewhere?

private boolean checkHexConnectsToEdge(int hexEdgeIndexToCheck, int currentHexIndex)
{
  killCounter++;
  
  int[] adjHexSpaces = playHexes[currentHexIndex].getAdjacentHexes();
  for(int counter = 0; counter < adjHexSpaces.length; counter++)
  {
   if(playHexes[adjHexSpaces[counter]].isOccupiedByPlayer1())
   {
	if(playHexes[adjHexSpaces[counter]].getHexNumber() == hexEdgeIndexToCheck)
	 return true;
	else
	{
	 if(checkHexConnectsToEdge(hexEdgeIndexToCheck, playHexes[adjHexSpaces[counter]].getHexNumber()))
	  return true;
	}
   }
  }
  return false;
}

I have also attached some of the code. I hate asking but if you could take time to look I would appreciate it. In the code all I'm trying to check is if the chain reaches array position 21 which is a hex on the far right side (for player 1). I'm afraid there is something small I am missing.  nodesApplet.txt   6.61K   23 downloads

[Sandman]

I tried to implement it and it results in an infinite loop...maybe I'm misunderstanding the psuedo-code somewhere?

I think it might be a bug in the psuedocode - it's missing a test to ensure that you don't check the same hex twice. Without this, it can keep going back and forth between two neighbouring tiles until the stack explodes :/