I've started studying a bit deeper into artificial intelligence with MIT's Artificial Intelligence OpenCourseWare and I have to say that it's really easy and I question how this is a graduate level course. At least in terms of theory I question how it's such a level, but I'm finding in implementation heuristics wasn't entirely the right question to have been asking, but instead found other methodologies.

I'm working toward changing the tic-tac-toe over to a two dimensional array and the node traversal should be easy as it's simply a matter of finding a node meeting the condition of containing a non-zero value within certain bounds. For example, I have the following list of positions with respect to the S (start) node which I need to check for G (goal), but G is undefined because it can be any of those within the defined bounds. Keep in mind that S will have the coordinates of 0,0 or [0][0] and all traversal is simply a matter of offset from S and we have a matrix such as...

00000

00000

00S00

00000

00000

So, given knowledge of win conditions from start we can ascertain what spots will never matter to a node with regard to a win condition.

*(Denoted by "x" below.)*
0x0x0

x000x

00S00

x000x

0x0x0

So again, if we take S = 0,0? We get the list of 16 potential goals:

First step:

- [-1][-1]
- [-1][0]
- [-1][+1]
- [0][-1]
- [0][+1]
- [+1][-1]
- [+1][0]
- [+1][+1]

Extended steps:

- [-2][-2]
- [-2][0]
- [-2][+2]
- [0][-2]
- [0][+2]
- [+2][-2]
- [+2][0]
- [+2][+2]

.. and eight dead spots, so doing this we cut the relevant nodes to 2/3 the original map.

*(The ratio of pruned nodes should become greater as we expand the map.)* But we can ascertain the list of dead/non-relevant nodes and their respective offsets to S and even define a pattern for scalability of play area/map .And this one seems a bit simpler in mapping by offsets. So, let's look at the list first, we have...

- [-2][-1]
- [-2][+1]
- [-1][-2]
- [-1][+2]
- [+1][-2]
- [+1][+2]
- [+2][-1]
- [+2][+1]

Happen to notice any patten in those sets of numbers? Basically any

** number == |n+1| if n > 1** can be pruned from our tree. Thus a conditional such as

**if(n > 1 && Math.abs(sY+sX) === n + 1) { /* prune this */} **becomes a thing of beauty for us... in theory. Let's expand our data set and win condition number by an additional step to test it out...

0xx0xx0

x0x0x0x

xx000xx

000S000

We have...

- [-3][-2]
- [-3][-1] ...

And we can actually stop there because we're now inherently wrong as n=3 and our condition is n+1=4, which the second node we'd want to prune actually is equal to that, but not the first one. Rather, we've now found that the excluded portion is instead, a range of values [n+1,n^2(-1)] so, let's expand our data set again to see if this holds up...

*(Keep in mind we can check all edges by checking one since we're using the absolute value of the sum of X,Y as a determiner.)*
0xxx0xxx0

- [-4][-3]
- [-4][-2]
- [-4][-1]...

So, now our range is 5-7, n=4, and thus [n+1,n^2(-1)] == [5, 7]. And even for n = 10 we should get the range of 11-19 being nodes to prune/ignore for this step.

0xxxxxxxxx0xxxxxxxxx0

- [-10][-9] .. pruned
- [-10][-1] .. pruned

While this is theory, it would allow us to create a more complex game with varying win condition and play maps. Say, being able to easily create a three dimensional version of the game by simply saying n^3 for formation of our 2D array and placing in play blocking spaces/nodes to the map which are primarily to convey data to a view or presentation layer.

Now, we also have to consider that any space already occupied by a non-matching piece is pruned. Thus the easiest way to go about our first step of course will be by the nodes that have an offset of <=|2| && offsetX !> |1| && offsetY !> |1|. When (X !== X && Y !== Y) to remove matching with node S. The reasoning behind this being that they are "blocking" paths and also of course, our first steps if we were to traverse with a methodology more sophisticated than throwing two for loops at it and calling it a success. So, we look for win conditions with of course... the for/while loops I just discounted, but in, as I said, a more sophisticated fashion. This will actually potentially cut the number of nodes we traverse in half or greater than half depending on the status of the surrounding nodes.

//

// assume we define the S node with a simple binary array traversal looking for non-zero nodes

// or perhaps we store state of last player moves and check those prior to binary traversal of the map

//

function findMatches(sY, sX) {

var n = 1;

for(var n = 1; n < playSpace; n++) {

// note: if n = 0, then the loop will try 0,0 and fail because of origin checking below then increment anyway

// starting at 1 as shown above gives a baseline/feel for what moves are possible

for(var y = -n; y <= n; y+=n) {

for(var x = -n; x <= n; x+=n) {

// basically I declare this here to keep things smoother in prune checking

var absXY = Math.abs(y) + Math.abs(x);

// check to make sure you aren't matching S, basically just a short-circuit for that instance

if((sY === sY && sX === sX) || (n > 1 && absXY >= n+1 && absXY <= (n^2)-1) ) {

// the second condition as you'll recall is our pruning algorithm

}

else if(node[sY][sX] === node[sY += y][sX += x]) {

// ideally, we add to a list of found nodes which can be compared against our next loop through

// or we could immediately branch from here checking for win conditions. We can also try nodes

// of the found coordinates in extended steps, the possibilities are many, but only one is efficient.

}

} // /(for(x)

} // /for(y)

// basically here we just say that if the space cannot exceed the playSpace and to increment the step

if(n !== playSpace) {

n += 1;

}

} // for(n)

} // /findMatches()

I suppose what I'd also like to do here is also say to prune/ignore the step when it would with regard to offset from start violate the playSpace along both the X and Y axises. I'd do this simply to prevent trying to access nodes that can't/shouldn't exist. Plus, why spend computational power on trying? That'd be a complete waste of time/resources.

I'm putting this up until later, but also thinking if I do the 3D implementation, I could actually do the display on a CSS Cube and control the rotation with the jQuery library I was planning to use anyway.