Wednesday, November 19, 2014

Pruning Trees

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]
    2. [-1][0]
    3. [-1][+1]
    4. [0][-1]
    5. [0][+1]
    6. [+1][-1]
    7. [+1][0]
    8. [+1][+1]
    Extended steps:
    1. [-2][-2]
    2. [-2][0]
    3. [-2][+2]
    4. [0][-2]
    5. [0][+2]
    6. [+2][-2]
    7. [+2][0]
    8. [+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...
    1. [-2][-1]
    2. [-2][+1]
    3. [-1][-2]
    4. [-1][+2]
    5. [+1][-2]
    6. [+1][+2]
    7. [+2][-1]
    8. [+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...
    1. [-3][-2]
    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
    1. [-4][-3]
    2. [-4][-2]
    3. [-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
    1. [-10][-9] .. pruned
    2. [-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.

    Monday, November 17, 2014

    Naughts & Crosses AI about ready...

    So, I took a bit after waking up earlier to put some finishing touches on the AI project, and I'm ready to put it into jQuery or AngularJS to handle the click functionality, potential animations, and data binding. In lue of having the finished project complete right now, here's what the (mostly) functional code looks like...

    // changed from empty strings to null and ultimately 0 to provide
    // flexibility in game rules and potential mode options
    // key: 0 = empty, 1 = "X"/player1, 2 = "O"/player2
    var square = [0,0,0,0,0,0,0,0,0],
        moveCount = 0,
        turn = 0,
        //
        // for later AI logic optioning
        //
        aggroAI = true,        // intentional win
        defAI = true,        // intentional defense
        //
        // for later two and zero player options or odd game modes
        // such as players incrementing or decrementing each other's marks
        //
        mode = 1;

    function playerTurn() {
    }
       
    function getValues() {
        for(var i = 0; i < 8; i++) {
            square[i] = eval("document.tic.sqr" + i+=1 + ".value");
        }
    }

    //
    // state checks working on premise of: A=B && B=C :: A=C
    //
    function stateCheck() {
        getValues();
        //
        // horizontal win check
        //
        for(var i = 0; i < 6; i+=3) {
            if(square[i] === square[i+=1] && square[i+=1] === square[i+=2]) {
                announceWinner();
            }
        }
        //
        // vertical win check
        //
        for(var i = 0; i < 2; i++) {
            if(square[i] === square[i+=3] && square[i+=3] === square[i+=6]) {
                announceWinner();
            }
        }
        //
        // diagonal win check -- non-iterative because the two checks have opposing
        // patterns and adjusting for such would just serve to make things needlessly complicated
        //
        if((square[0] === square[4] && square[4] === square[8]) ||
           (square[2] === square[4] && square[4] === square[6])) {
                announceWinner();
        //
        // draw check
        //
        } else if(moveCount === 9) {
            alert("Draw");
            reset();
        }
    }

    function announceWinner() {
        if(square[i] === 1) {
            alert("X wins!");
            reset();
        } else if(square[i] === 2) {
            alert("O wins!");
            reset();
        }
    }

    //
    // logic to determine place value
    //
    function decisivePlay() {
        stateCheck();
        if(turn === 1) {
            if(square[0] === 0) {
                if(square[1] === square[2]) || (square[4] === square[8]) ||    (square[3] === square[6]) {
                    document.tic.sqr1.value = "O";
                    square[0] = 2;
                }
            } else if(square[1] === 0) {
                if(square[0] === square[2]) || (square[4] === square[7]) {
                        document.tic.sqr2.value = "O";
                        square[1] = 2;
                        return true;
                }
            } else if(square[2] === 0) {
                if(square[0] === square[1]) || (square[6] === square[4]) || (square[5] === square[8]) {
                        document.tic.sqr3.value = "O";
                        square[2] = 2;
                        return true;
                }
            } else if(square[3] === 0) {
                if(square[4] === square[5]) || (square[0] === square[6]) {
                        document.tic.sqr4.value = "O";
                        square[3] = 2;
                        return true;
                }
            } else if(square[4] === 0) {
                if(square[3] === square[5]) || (square[1] === square[7]) || (square[0] === square[8]) || (square[2] === square[6]) {
                        document.tic.sqr5.value = "O";
                        square[4] = 2;
                        return true;
                }
            } else if(square[5] === 0) {
                if(square[3] === square[4]) || (square[2] === square[8]) {
                        document.tic.sqr6.value = "O";
                        square[5] = 2;
                        return true;
                }
            } else if(square[6] === 0) {
                if(square[7] === square[8]) || (square[2] === square[4]) ||    (square[0] === square[3]) {
                        document.tic.sqr7.value = "O";
                        square[6] = 2;
                        return true;
                }
            } else if(square[7] === 0) {
                if(square[6] === square[8]) || (square[1] === square[4]) {
                        document.tic.sqr8.value = "O";
                        square[7] = 2;
                        return true;
                }
            } else if(square[8] === 0) {
                if(square[6] === square[7]) || (square[0] === square[4]) || (square[2] === square[5]) {
                        document.tic.sqr9.value = "O";
                        square[8] = 2;
                        return true;
                }
            }
        }
        else {
            return false;
        }
    }

    function randomPlay() {
        //
        // unsure if it's more expensive to do the recursive function
        // or collect available spots into a temporary array and then select,
        // so I went with recursion because it was simpler to implement
        //
      var randomSpot = Math.ceil(Math.random()*9);
     
      if(eval("document.tic.sqr" + randomSpot + ".value") === "" && turn === 1) {
        eval("document.tic.sqr" + randomSpot + ".value") = "O";
        square[randomSpot-=1] = "O";
        return true;
      } else {
        // will continue trying to make random plays until success
        randomPlay();
      }
    }

    function AI() {
        // uses the if check to make a decisive play if possible
        if(decisivePlay() === true) {
            advanceTurn();
        } else {
        // makes a random play if there's no win condition present
            randomPlay();
            advanceTurn();
        }
    }

    function advanceTurn() {
        if(turn === 1) {
            turn = 0;
        } else {
            turn = 1;
        }
        moveCount += 1;
        //
        // check state of game after advancing turn counter for draw state compatibility
        //
        stateCheck();
    }

    function reset() {
        for(var i = 1; i < 9; i++) {
            eval("document.tic.sqr" + i + ".value = \"\"");
        }
        for(var i = 0; i < 8; i++) {
            square[i] = 0;
        }
      turn = 0;
      moveCount = 0;
    }

    Couldn't Sleep, So I Built An AI...

    I couldn't sleep, so I built an AI... kind of.

    I happened upon a post by one of Google's various interviewing employees on Reddit earlier and saw he asks a "difficult" question in terms of programming AI for tic-tac-toe. This got me thinking about how in all of the time I'd been programming and for all of the interest I've had in machine learning, data structures, game theory, and AI... I'd never done anything merging all of these things... until that is, this morning.

    I started working through the problem by Googling for answers and found minimax and all other game theory waiting for me. However, since tic-tac-toe is a fairly deterministic game, nothing fancy is really needed to make things work. I'm also a big fan of not re-inventing the wheel when you can simply go see one. But all I found in my initial search was a dingy old wheel from the days of IE4! (This one specifically.)

    And I'll warn you now, it isn't pretty... but it works.

    So, I set to work immediately tearing into the old code for not using iterative processes. And then I realized no fewer than half of the functions included actually did nothing. And in most of the cases, just reiterated what another function was doing. And this is what scares me about programmers that don't know how to do a basic for loop, recursive functions, nor actual comparison operators. Hell, the entire thing doesn't even use anything more complicated than a String in terms of objects. o_o How?

    Anyway, I set about prettying up the code by adding line endings, changing things over to arrays, and utilizing recursion. Then I found out I don't have to be afraid to use eval()! How about that? I found the perfect use for it in being able to do iterations for the grid via per-defined constraints on code that only runs client-side. (And frankly, for server side languages with the intent of being such, you have stuff like variable variables in PHP.)

    So, I'm about "done" an hour and a half later and having chopped away just over 330 lines of Javascript from the original, compacting them into neat little functions. Then I realized I could expand this fairly easily, given how maintainable I've made the code at this point, to truly make the game two player, zero player, or even give options to how the AI will play against you. Like, disabling aggressive or defensive move sets, which would roll over the decision to the random move functionality. The entire thing is almost fully modular at this point.

    I'm far from done though, before I upload the finished project, I want to take the presentation layer out of the code. Remember how it was using strings? Yeah... It was for more than to keep track of what marks were where. So, I'm planning on replacing the buttons with jQuery and probably replace the variables with integers the 0, 1, and 2 for no mark, X, and O respectively. That will also open up to using alternative marking sets and likely make the whole mess run more efficiently, which is neat.

    At what point in rebuilding the code is there nothing left of the original? Perhaps in some sense, the springboard of the old code has provided the "DN-AI" for this version. =)

    Sunday, November 16, 2014

    A De-stresser...

    Since it's seasonally appropriate, a little fun with a classic joke to not stress about the job hunt too much.

    Q: Why do programmers mix up Halloween and Christmas?
    A: Because Oct 31 === Dec 25.

    Wakka-wakka! Have a good night!

    Explanation for the non-techies/non-math people: Oct(al) is a base 8 numbering system and Dec(imal) is base 10. Thus 31 in octal is equivalent to 25 in decimal. Also, thank you once again IBM for introducing octal to every computer scientist ever. (But then, it's understandable given the bit limitations back then.)

    Somebody Please At Least Interview Me...

    Still having trouble getting a programming job and I can't really understand why. I mean, I was out of the field for about a year due to personal reasons, but that doesn't mean my brain has turned to mush. At this point I'd be happy to even get an entry level programming position. I've been looking for four months, am no longer geographically tied, but have preference for either San Francisco/Bay Area or Indianapolis/Chicago.

    And what shocks me is that there are people who make it to any type of interview that don't know basic programming stuff. Keep in mind these times are on a laptop without a spacebar and done in plain old Notepad. Neither were worth my time to open Eclipse for...

    FizzBuzz Classic
    Background: Saw this on Jeff Atwood's Coding Horror blog and was shocked at the concept of 199/200 programming interviews not being able to write something so simple. The basic concept is to run through numbers, 1-100, and output "Fizz" on a number divisible by 3, "Buzz" on a number divisible by 5, and both if divisible by both 3 and 5...

    // declare output strings for consistency
    var fizz = "Fizz",
      buzz = "Buzz";

    // begin iteration at 1 and end at 100
    for(var i = 1; i < 100; i++) {
    // compare for both 3 and 5 first so we don't waste time going through the 2 other tests if not divisible by either
    if(i%3 === 0 || i%5 ===0) {
      // test for 3 
      if (i%3 === 0) {
        // tests for 3 && 5 without creating another if/else externally which would have to occur at the beginning of the tree
        if (i%5 === 0) {
          // if 3 && 5
          console.log(fizz + buzz);
       } else {
         // if 3 alone
         console.log(fizz);
      // test for 5 alone
      } else if (i%5 === 0) {
        // if 5 alone
        console.log(buzz);
      }
    } // end if(||)
    } // end loop
    // Took 3 minutes. Basic iteration and condition testing with if statements chosen over switch because I find switches can get verbose and messy.

    The Anagram Checker (Simple)
    Background: This one was from the same post, but from the comments section, which specifically stated they had a similar experience where they were instead asked to compare two strings to see if they are anagrams of one another...

    // declare the strings to be compared
    var word1 = "input",
      word2 = "utnpi";

    // test to see if they're String objects
    if (word1.typeof(String) && word2.typeof(String)) {
        // parse the Strings as ints and compare them to each other
        if(parseInt(word1, 36) === parseInt(word2,36)) {
            // if the resulting ints are equal
            console.log("The two inputs are anagrams of one another.");
            return true;
        } else {
            // hopefully self-explanatory
            console.log("The two inputs are not anagrams of one another.");
            return false;
        }
    } else {
        // error output, but would frankly be better done with a try/catch block for actual error reporting
        console.log("Inputs must be type of string");
        return false;
    }

    // Done in 5 minutes, but didn't know parseInt() had the multiplier argument field. So, that added extra Googling time on a fairly slow connection. Please pardon it not taking the edge case of case sensitivity into account.

    Note: All comments were added after for "walkthrough".

    Wednesday, September 17, 2014

    Gaining New Javascript and Python skills...

    Recently I've decided to take my JavaScript skills to the next level. While I've been an engineer for many years, (nearly a decade professionally and twice that as a hobbyist for those curious,) I had always dismissed JavaScript as many had, a language for nice little transitory animations and form validation on sites. I am however, finding that it can be a full fledged and fairly powerful language.

    To bring my skill set in JS up to snuff I've been doing the Codecademy courses in both JavaScript and jQuery, in addition to going through various JavaScript powered APIs. And I can safely say, my horizons and abilities with not only JavaScript, but also object oriented programming have expanded dramatically. This is mostly due to using JSON (JavaScript Object Notation) and working to understand various RESTful APIs such as those of Microsoft's OneDrive/SkyDrive and YouTube.

    With most of what I can take away from Codecademy done, I've turned to doing their Python and Ruby courses for fun and a bit to feel the accomplishment of finishing all of their main courses. As I do this though, I find myself realizing how little I actually know of the Angular framework and seeing how fast I adapted to new concepts and syntax. (For example, the "dictionaries" in Python essentially being JSON syntax... Awesome!)

    So, I'm looking at doing Code School's courses since I've already done a little of their JavaScript Mastery course and Github elective, I really want to make myself a continually stronger software engineer. But I've decided that I won't be doing that until after I get all of Codecademy finished out and I highly encourage anyone interested in beginning into the realm of programming to start there. I even tell those I tutor to go there as a supplement to everything else, as I know I can't cover every learning style.

    Saturday, August 30, 2014

    I Love Eclipse

    Decades ago, when I started developing, I had no clue about IDEs and the like. My first would probably technically have been Dreamweaver and then a version of Visual Studio back when VB6 was still a thing. But eventually, I found myself using Eclipse and while it was a bit steeper, it made more sense as I began doing more, and I still find myself using it to this day for continually more development.

    For example, in previous postings I've pointed out it can be used for PHP and even as a RDBMS for SQL via plug-in. Another advantage I get from it is that it can be used to develop Android applications since it was one of the first officially recommended methods by Google and also, Eclipse was meant to be a Java IDE above all else, so the marriage made sense.

    But I continue a decade or so later, find myself continuing to use Eclipse as my go-to IDE. Even more-so because of it being cross-platform and my switching readily between Linux and Windows. Part of me wishes I had more money to throw at supporting them.