Saturday, February 14, 2015

My Last Game: Idle Developer

I make no secret about being a gamer and as such, I'd been noticing the overwhelming abundance of Idle Games being posted to sites like Kongregate. And part of me suspected it was because they were relatively easy to program and it got me thinking that I should just make one for fun. So I took a weekend on JSFiddle and made one with curiosity as to whether or not I could make one simply utilizing HTML5 technologies, but without using canvas.

Over the weekend I taught myself the SoundManager2 and SoundCloud APIs for access to their JSON formatted data in addition to really stretching my comfort zone with regard to use of timed events in Javascript.

Click here to play Idle Developer.

How to Play: You need to click on "Personal Blog" to begin earning money. You need to keep clicking until you automate with a manager upgrade, available under the managers tab, and you can buy more of an item as you can afford them, granting you more money per cycle.)

Requirements: A modern browser with support for CSS3's vh, vw, and gradient backgrounds.

=================================================

Update: I checked it out and for some reason the SoundCloud API isn't properly streaming the looping track to my API key any longer...?

Update 2: Turns out the track I was streaming had actually been removed from SoundCloud. Changed it over, after a bit of searching for a new loop, to "Acids and Bases" by Alexander Mote.

My First Website

So, I was looking at web developer jobs in the Cedar Rapids area and this one company I'm very interested in working with has a question in their standard form along the lines of, "In 150 characters or less, what makes you unique?"

I know everyone ends up answering these questions with some made-up b/s about working hard or whatever else. Sometimes even things visible in their resume. My answer is a bit different...

"I built my first site in 1996 on Geocities when I was 9, it was a Mega Man fan site."

And I realized in that statement, I've expressed a lot about who I still am. I'm a gamer, I've been around web development since before CSS was a thing and I've been using CSS since 1998. Because of learning these languages, I was inspired to learn Visual Basic before I was even in my teens and by the time I was in my teens...? I was hacking Sonic ROMs with a hex editor and exploring how system memory functioned.

Beyond that I'd always been fortunate enough to have Photoshop at my fingertips, at least since version 6. And even further, I was using Poser and Bryce for 3D modelling and animations.

But come back to me being a gamer. To some that would imply that I'm lazy and like spending all of my time building things up in places that don't technically exist. To those that realize who we really are? We learn how to obtain maximum results with minimal effort. A gamer is lazy, yes, absolutely, and that drives us to become expert strategists and as Bill Gates himself said, "I choose a lazy person to do a hard job. Because a lazy person will find an easy way to do it."

Anyway, I normally don't post stuff like this on here, obviously. Though I'll leave you with what is still my favorite song that I had on that long-defunct site packed with MIDI music. Storm Eagle from Mega Man X...


...also, young me, when I grew up I became an awesome developer that live streams Binding of Isaac and Hearthstone on Twitch when you're relaxing with games. =p

CSS: For the Love of Viewport Sizing

One of my biggest design joys that's come out of CSS3 is the "vh", (or viewport height,) property. For the longest time in developing sites, I would have to implement clunky javascript to implement height-based page elements in my design. Though of course, Chrome supported 100% as a value for the height property, that didn't translate over to non-Webkit browsers. And even when implementing the javascript, I'd have to add additional code to compensate for the intricacies in the way each browser handled its document rendering, let alone adjusting the div layer in question as the viewport would resize itself.

I like vh as a friend though and understand it as having a very good and specific uses. Remember all of those times you wished you could've had a sidebar that was 100% height all of the time? Now it exists. Though beyond that, it's ideal for the parallax layouts that've been en vogue for the last few years in the name of responsive/mobile first design. However, in the former of course, it might be more desirable to make that div a fixed position so it scrolls with the page displaying relevant additional data.

Unlike over at CSSTricks and their look at it though, I believe neither vh nor vw properties should ever be utilized for text display. This conclusion came after testing it for how it would scale up and down respectively. While scaling up isn't that much of a problem if the rest of the layout is similarly scalable. (Read: Images and similar static media would then have to be scaled using a related measure based upon desired display size and original proportion. Though the caviat here is you don't know what target values exist.) Scaling down eventually leaves you with an unreadable mess.

That's why I believe text should remain in the realm of static rather than dynamic sizing as the overwhelming majority of modern browsers will adjust text to an appropriate size on their own. In other words, rule one of development, don't re-invent the wheel.

When Responsive Design Sucks

I think responsive design is an awesome idea, I'm all for it. In fact, I'd argue we've been doing a form of responsive design in regard to how things would render differently between browsers for decades now. All we've really done is fully commit to the realization that there are different device sizes and the adaptation for making such better from a usability standpoint.

However, what I see is a lot of developers using it as an excuse for is developing a mobile site and ignoring desktop browsers. For example, I think the layouts you see where a page has multiple panels (divs that take up the full viewport height) works incredibly well on mobile devices, no question, beautiful. This is especially true when a developer will take the care to actually bother adding the Javascript intended for such layouts to create anchor/stop-points in the scroll.

That beauty and simplicity doesn't carry over to a larger screen environment as well, nor one where you're using methodology other than a swipe to scroll. In fact, I'd argue that it's more harmful as that specific type of sectioning removes the flowing, document-style standard that's existed for decades.

You see, those types of layouts on desktop didn't happen because we're unimaginative, but rather because they adapt well to the tools we're using to control them. Use a touch screen and a cursor for navigation on any given site and tell me your experience isn't frustrating in one way or the other. We've adapted 20 years or so of use into knowing what works on desktop devices and we shouldn't throw that away.

What I will agree with is that one should build the mobile site and then expand upon that layout for desktop devices. And really, there's less and less excuse for this outside of laziness and being too reliant on common CMSes as frameworks like AngularJS make this an almost trivial task via use of ng-hide/show (let alone custom directives) in conjunction with obtaining the viewport size.

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