The future comes from the past

 It has been a long time since I took a break from working on my 2600 emulator. Next month I am going to return to that project. Things have changed a lot since I worked on that project so have a lot of decisions to make. Web Assembly has become a real thing and there are several good paths to using it. Kotlin is not one of them. I am trying to decide if I should port to C, or Assembly Script. I am also thinking of going with an IDE instead of just an emulator. 

The next few months will be looking at tools and technology available followed by porting my existing emulator code. From there will be a matter of finishing the emulator then possibly building an IDE around things.

An Awful Month and a Postponed Decision

 Last month was rough and I am just getting caught up to where I should be this weekend. I am now working as a full-time college professor, which is a surprising amount of work. Making matters tricky was that just after finalizing the contract a major event happened.

My father passed away on August 20^th. He had been taken to the hospital a few days earlier for pneumonia. He had recovered from it and had been moved up to the rehabilitation floor. I was assuming he would only be there a couple of weeks before my caretaking duties would start again. Instead, as I was packing up the stuff he wanted me to bring him for my morning visit I got a phone call from the hospital with the bad news.

It is really strange when something like this happens as part of my mind knew he was gone but another part insisted that this was some type of prank or a mistake. I knew I was not in a proper mental state so asked my neighbor to drive me to the hospital. I simply had to verify that this was real with my own eyes. Stupid, perhaps, but at least I got to say goodbye to him.

Next was the funeral. Dad wanted just a small gathering of his closest friends and family. Thankfully my sisters were there to help prepare this as I had so much preparation to do in a short time. I did write the eulogy which took multiple attempts. I was warned that when giving a eulogy that you should do several dry runs so you can get through it without breaking down. I am glad I followed this advice. Even then, there were a few moments where I could hear my voice breaking and had to pause for a few seconds. What is interesting is that it was at the strangest moments. How hard of a worker he was. How much he cared for my mother. Even writing this I am struggling.

If this wasn’t bad enough to deal with, on the day of the funeral the air conditioner wasn’t clicking on and we had a plumbing issue. The plumbing was easily resolved, thankfully. The air conditioner, was also easy but had a warm house all that day as we simply didn’t have the time to look into the problem. It turns out that there is a switch to the furnace outside the furnace room that magically turned itself off. My nieces and nephews swear they never played with the switch and it is high enough on the wall  (above head height) to prevent accidentally turning it off.

Even after the funeral, I have lots of work to do, but spread out over a few months until probate is finished. Slowly packing things up is not hard work, but often results in surprising memories. Which finally leads to the point of this posting. I still have no idea what I am going to be doing with the site and blog so will be delaying my decision until next month.

Future of blog

 Changes are coming. I have recently accepted a new full-time job. This is the ideal job for me as it is near home so I will still be able to be my dad’s caretaker. This means that the amount of time I have to work on my own projects will be exceedingly limited. This leads to the question about what I am going to be doing with my site and blog. Right now, I am still deciding which course that I want to take.

Option 1 close them down. This would be the easiest course but not really a satisfying solution.

Option 2 quarterly updates. This would keep the site active and I could use the blog to write making of articles outlining what I have done to create the games. 

Option 3 focus on the making game aspect. I would slowly build a game with videos on each step of the process with the blog being a transcript of the videos.

Option 4 focus on teaching how to make games. This would be more focused on the technologies used to make games and would have tutorials on how to program.

Option 5 Classic Machine Architecture. The course I wish would exist. A look at a classic machine (Atari 2600, NES, SNES or PS1) and how you would create a game with that machine. This would result in learning how machines work with machines simple enough for a more holistic approach.

Any suggestions on which direction I should take would be appreciated. I will post my decision on Spelchan.com on September 1st.

The fullscreen API

With my masters degree finally complete, I should have a bit more time to focus on my site. Unfortunately, my Dad is now disabled so I am taking care of him and being a care-taker has been taking far more time than anticipated. As he slowly improves, the amount of time I have available to work on my own things is slowly increasing but this may change shortly depending on upcoming events which I will talk about if they come to pass.  Reworking my site is certainly something that needs to be done. One of the big issues that I have is the size to make my games.

The problem is that there is no way of knowing what resolution that the user of a web application is using. The image below shows the different common resolutions that have been used in the past to the present. Making this problem more awkward is that windows don’t need to be full screen and different browsers have different amounts of stuff surrounding the page contents.

 

My plan was to use a 16x9 aspect resolution for future games as that has become the standard screen size. With most modern machines having at least 1280x720 resolution so 1024x576 seemed like an okay resolution to use for future games and I have been playing around with this. On my desktop machine, which was HD, this looked okay but when my monitor was upgraded to a 4k monitor, the locked resolution problem became exceedingly apparent. 

Two viable solutions came to my mind. The first is full screen mode that I have seen other sites take advantage of for videos. Looking into this, I discovered the fullscreen API and decided to explore this with my Canada Day game that I released on Canada Day (July 1st for the non-Canadian’s reading this). The API is easy to use once you have figured out how to use it, but as is often the case it does have a few weird aspects to it.

The API is invoked on a HTML display element which becomes full screen if the browser supports this. This is simply done by calling the element’s requestFullscreen method. This is simple enough but exiting full screen is not done by calling the element’s exitFullscreen method as any reasonable person would expect. Instead, you need to tell the document that you wish to exit full screen mode. While I can sort of see the logic behind this, as the element is becoming full screen and the document is returning from full screen, but couldn’t elements have an exitFullscreen method that calls the document version? API design really needs to be improved in this industry.

Once you are full screen, the next issue crops up. The canvas is the wrong resolution so it needs to be adjusted. This is assuming that you were even successful at switching to full screen. There is a “fullscreenchange” event that is triggered by switching between full and regular modes so writing a handler for the switch is easy enough. Finding the resolution for the full screen can then be done by using the screen.width and screen.height read-only variables.

function toggleFullscreen() {
    let canvas = document.getElementById("game");
    if (document.fullscreenElement == null) {
        canvas.requestFullscreen();
    }  else {
        document.exitFullscreen();
    }
    draw();
 }
function fullscreenChangedHandler(event) {
    let canvas = document.getElementById("game");
    if (document.fullscreenElement != null) {
        canvas.width = screen.width;
        canvas.height = screen.height;
    } else {
        canvas.width = 1024;
        canvas.height = 576;
    }
    canvasRect.w = canvas.width;
    canvasRect.h = canvas.height;
}

The game can then be developed in 4K and scaled to the resolution of the display. My thoughts are 4K will be good for a while so will use that as a baseline resolution for my future development. Scaling to lower resolutions may not be the best approach but works good enough for now. Ideally having different images for different resolutions would be the better solution but it may be quite a while before I bother working on my LOD system and I will likely switch from canvas 2d to webGLx before doing so.

Locking the canvas size in the non-fullscreen mode is the next challenge. I am thinking that the canvas should scale based on the canvas size so next month’s game will be experimenting with that.  

Death of the Phoenix Postmortem

 On itch.io, I noticed that gamedev.tv was having a game jam where all entrants got a free course. I decided to enter but have noticed a very unfriendly opening advertisement when I go to the gamedev site so am a bit leery.  The game I quickly wrote is on Spelchan.com and is called Death of the Phoenix as the theme of the jam was “Death is only the beginning” so this matched the theme. Here is my postmortem of that effort.

What went wrong

One of the most important aspects of a game jam is that due to the limited amount of time you need to have a realistic plan. The best approach is to start off with a basic game then, once it is working, add features until the time runs out. With a theoretical 10 days, it was easy to have a more ambitious plan. Unfortunately, I am taking care of my father who recently had a stroke and ended up partially paralyzed. With my caregiving responsibilities, the amount of time available to me is limited so a day is only a few hours and ended up being even less. 

My original plan was to have a map that the player would need to explore to find the material for building the nest and the location of the nest. The story would be told as brief cut frames that would happen when certain tiles were traversed, and there would be areas where the player would be able to restore their health that would act as save points if the player died.

When it became clear that the amount of working time was less than anticipated, my plans needed to be changed. I had implemented the combat system so decided to drop the map and simply have a visual novel instead. 

What went right

My original story system would have a class that would use a JSON object to provide the layout information for the scene. I had hopes that there was spare time left I could add animation parameters to the JSON data and have animated cut scenes. The JSON data format is a simplified version of class definitions in JavaScript making it extremely easy to use as objects. Because it is a human editable format, it is easy to create by hand. This makes putting together a script very quick and does not require code be written. I was even able to use the room scripts for the title screen and losing screen making a very quick visual novel language.

I want to expand this into a proper adventure game engine so will be experimenting with using JSON as a script (or collection of scripts) for some of my adventure game ports that I am planning to do. The data-driven approach makes some sense, and when combined with a command pattern may make for a straightforward way of quickly building episodes for a multiple episode adventure game but don’t want to go into details until I have something concrete. 

Mixed blessings

 My original intention was to do all the artwork myself but for prototyping I made the fortuitous decision to use creative common and public domain artwork as my placeholder art. This had the advantage that if I did run out of time, the art already is there, and I simply need to add attribution text to the game page. The downside is that mixing assorted styles of art makes the scenes less seamless. This can be fine in different regions of the game but can still be jarring. This is a worthwhile tradeoff as having a releasable build, even if not as polished as desired, is a good safety net.

Temporary artwork does need to be from a source that you can use, which reduces the source material, but does not need to be public domain or creative commons. Having royalty free assets would also work for temporary artwork. I have bought several bundles of royalty free music and art so simply need to go through the libraries I have and start using them.

Future plans

While I don’t expect to do anything with this game, I will be experimenting with building an adventure game engine using some of the approaches used in this game. I'm not sure how quickly this will be done as my time for work is limited, but an adventure game engine which is general enough for other games would allow for several of my larger projects to be completed quicker, so is a good direction to go.

 University Postmortem

After closing Blazing Games due mostly to too much competition, I returned to university in an attempt to get my bachelor’s degree to have the minimal degree that most companies hiring programmers were looking for and to make sure that my skills were up to date. While pursuing the degree, I was near the top of my class and thought that perhaps it may be worthwhile to get into the research side of computer science so opted to go for my MSc in Computer Science.

What Went Right

Just completing a master’s degree is an achievement. The number of students allowed into a program, at least at the university I attended, is only a small percentage of those who apply. The dropout rate is surprisingly high as well, especially within the sciences. While the graduate level courses are more work than third/fourth year courses, the difficulty jump is not as high as it was from first/second year courses to third/fourth year courses. Granted, the first/second year courses may appear easier to me as I was already familiar with the materials but tended to have to take the courses anyway as self-taught doesn’t count. While it is possible to challenge some courses, it is still a fair bit of work and you don’t save that much by doing it so may as well take the courses to fill in one or two missing spots in your knowledge.

The other major thing that went right was getting an answer to “is research an appropriate field for me?” While I was okay at research, looking at some of my alumni, it is clear that there are people much more suitable to academia than I am. This means that a future pursuit of a PhD is not likely for me. What I have learned about performing research will be useful for my further endeavors and to my surprise has improved my coding skills. The necessarily precise nature of research can be applied to software development, especially for testing software.

Even though there are no plans to pursue a PhD, I found myself really enjoying my work as a teaching assistant. Working as a teacher at a college or equivalent may be something in my future. Failing that, writing books to teach others may be an option. Videos are something I would like to experiment in, but with how over-crowded YouTube is, gaining an audience large enough to cover the effort is unlikely.  Still, a small (few dozen) audience is all I would need for a hobby so will probably give it a shot sometime.

What went wrong

The thesis aspect of my MSc took longer than expected due to a pandemic and the simple fact that I switched what I was working on part way through my research. My supervisor did warn me that the change in research direction would add time but was kind enough to let me go my own direction with research. The area I ended up researching involved multiple areas which did not help matters, especially when I was a newbie at machine learning so was still learning the basics while trying to expand upon existing research. 

Covid-19 probably impacted a lot of research. Normally, the effect on computer science would be minimal, but my research required a user study which requires people so having the campus shut down for a lengthy time was not good. This delay was longer than it should have been as my expectation was that classes would resume in the fall. When it became clear that this was not going to happen, the study was redesigned to be online. 

As already mentioned, my knowledge of the field of AI and machine learning was sparse. I had thought that graduate work was going to be like other courses where students learn the material. Graduate courses do work that way, but the thesis is really about taking a field further (even if only by a baby-step) so existing knowledge about a field is important. Picking a research area because it is something you want to learn is not a good idea. Learning a field while researching is not a good approach. My recommendation to future students is to make sure you are familiar with the field you are getting into before picking your area of research.

Mixed blessings

I am not as good at math as I should be. When working with 3D graphics, I can muddle through the concepts to get things working but don’t fully understand the math. Having to work more with the underlying math behind procedural content generation via machine learning, it became clear that the problem wasn’t entirely a lack of understanding. I use some of the more advanced concepts behind math, the problem is I do this outside of the official math route so don’t know the symbolism or the tricks and techniques to best utilize the concepts. Improving math skills is definitely in my future, it is just a matter of finding time to do so.

When I entered my master’s program, I had thought that my organizational skills were good. There is software available for helping organize and write a thesis. The need for such software, as my organizing methods aren’t bad, was not evident to me. While manually organizing things works, there is a lot of overhead searching for things. Having software that handles and organizes all the research details would have sped up writing the thesis and would have also made me make more notes instead of relying on my memory. There are simply too many things to remember so no matter how good your memory is, you are going to forget things. What is worse, you will remember a detail you want to reference but not remember what article it was in so will have to spend too much time skimming through older articles you have read.

Final Thoughts

While I am not going to pursue my PhD, teaching in the future is not ruled out. While a MSc is not required for being a developer, it doesn’t hurt and the skills I learned while attending graduate school are useful. My future right now is in a bit of a hiatus as I am taking care of my father, and will be doing so until he is at a stage where he can take care of himself with minimal aid. While that is happening, my spare time is going to be on the development of my own game engine. Why? Partially for learning but mostly because of my NIH complex. More on that in the future!

Making Santa-Tac-Toe part 4 of 4

Part 4: Building the GUI

 In the previous parts, we created the core game logic and the AI agents that play the game. This was probably the most difficult part of this project, and we would not have a game without this work. Unfortunately, the part of the project that users care about is the user interface as this is what they see. User interface code tends to be bulky but simple so for this chapter we are just going to summarize what the classes that make up the user interface do and how they work together. For those readers are interested in detailed code, the source code is located at https://github.com/BillySpelchan/BlazingPorts.

As is common, the graphics for the game are all combined into an image file known as an image atlas. A scaled down version of the atlas image is shown below. As can be seen, all of the screens and the messages are images for this game to make things really quick. The downside to this approach opposed to programmatically building the display from simpler pieces is that the images are much larger and use up more space. For this simple game, the costs of a longer image loading time is more than offset by the improved performance and simplicity in coding.

All the image bounds and positioning information is stored in an object called STTConsts. Using an object to hold all the games constants keeps tuning information all in one area, making for an easy way to configure things.  In addition to placement information, the config also holds button configuration, enumerations, and AI settings for the two different opponents. A more general configuration file would probably want to avoid non-JSON data types for security and maintainability reasons.

Our game is screen based, with the STTMain class handling switching and controlling the screens. Having all screens controlled by a common host has the added, but not utilized here, advantage of being able to share messages and state information between screens. Screens used in the game share a common class creatively named Screen. This class has two utility methods to ease the UI requirements of the game. The createButton(label, bounds) method creates and adds a button to the display list. Likewise, createImage(atlasEntry, position=null) retrieves an image from the image atlas and displays it at the specified location.

The LoadingScreen class is the initial screen that is shown. loading screen only one which doesn’t use images from the atlas but instead displays a loading message until image atlas has been loaded. Once the image atlas has been loaded, the TitleScreen class is used to display the title. It has buttons to switch to the InstructionsScreen or one of two instances of the SelectScreen class. The InstructionsScreen simply displays three images that make up the instructions.

The SelectScreen has parameters for setting the background image and labels to allow both Santa and Krampus to present level options to the player. This determines which AI and which instance of the GameScreen will be called.

As with the SelectScreen, the GameScreen has configurable images so Santa and Krampus have their own screens. The game screen uses the STTTile class which uses images of Santa for X and Krampus for O which are displayed in the board. Game state messages are displayed as a comic-book dialog bubble at the top of the screen. Finally, the PlayAgainPrompt class is used to prompt the player if they want to play again once the game is over.

Making Santa-Tac-Toe part 3 of 4

 Part 3: Random Moves Meet Monty Carlo

Thanks in small part to AlphaGo, there is a huge interest in Monty Carlo Tree Search (MCTS). As the name implies, this is built off the idea of a Monty Carlo Simulation, where you run a large number of random simulations to help determine the best configuration of what is being simulated. Tic-Tac-Toe is too simple for MCTS, but the simulation aspect would be simple to implement and could be interesting so lets do that. We will then look at what would need to be done to turn the simulation into a proper MCTS AI. 

The heart of a simulation is the ability to play a random game. This is simply a matter of making random moves until the game is in a win or tie state, at which point we return the state of the game so we can keep track of the wins and losses.

playMockGame(board, curPlayer) {
    let b = new TTTBoard(board.getTemplate());
    let state = b.getGameState();
    let p = curPlayer;
    while (state.state === TTTConsts.PLAYING) {
        b.setTileByIndex(super.getNextMove(b, p), p);
        p = (p === TTTConsts.X) ? TTTConsts.O : TTTConsts.X;
        state = b.getGameState();
    }
    return state;
}

We want to score each potential move that a player can make, so simply loop over all the moves adding them to our scores array which we will be using for the next move method that our API requires we implement.

buildScoreBoard(board, curPlayer) {
    let scores = [];
    for (let i = 0; i < 9; ++i)
        scores.push(this.scoreTile(board, i, curPlayer));
    return scores;
}

Scoring a tile is simply a matter of making sure the move is valid, followed by playing several mock games and counting how many of the games the AI wins versus the losses.

scoreTile(board, index, curPlayer) {
    if (board.getTileByIndex(index) !== TTTConsts.EMPTY)
        return -2 * this.trials;
    let winState = (curPlayer === TTTConsts.X) ? TTTConsts.X_WON : TTTConsts.O_WON;
    let loseState = (curPlayer === TTTConsts.X) ? TTTConsts.O_WON : TTTConsts.X_WON;
    let score = 0;
    this.testBoard.clone(board);
    this.testBoard.setTileByIndex(index, curPlayer);
    let opponent = (curPlayer === TTTConsts.X) ? TTTConsts.O : TTTConsts.X;
    for (let i = 0; i < this.trials; ++i) {
        let state = this.playMockGame(this.testBoard, opponent);
        if (state.state === winState) score += 1;
        if (state.state === loseState) score -= 1;
    }
    return score;
}

Finally, implementing getNextMove is simply a matter of calling buildScoreBoard and then picking the highest score. We add a random value to each score as a tiebreaker.

getNextMove(board, playerToMove= TTTConsts.EMPTY) {
    let scores = this.buildScoreBoard(board,playerToMove);
    let index = 0;
    let high = scores[0] + Math.random();
    for (let i = 1; i < 9; ++i) {
        let temp = scores[i] + Math.random();
        if (temp > high) {
            index = i;
            high = temp;
        }
    }

    return index;
}

The MCTS algorithm is a bit more involved than what we are doing, but with such a small tree, implementing a full MCTS is purely academic. We would need to track a bit more information for each node in the game to properly do MCTS. Lets quickly take a look at the algorithm. It is broken into 4 basic steps.

1 Selection. The idea here is that we pick a node that we want to explore further. This is usually done by looking at the win/loss ratio in combination with the times the node has been looked at for the nodes that are not fully expanded. We want to pick the most promising node but at the same time want to make sure that each node is explored enough to properly estimate it’s worthiness. There are many methods to do this though the simplest is to use threshold * (wins+1)/(plays+1) but there are better methods available.

2 Expansion is simply to add one of the unexplored nodes of the target onto our tree. Instead of just having a scoreboard for the current round, we would need to track all the nodes we have expanded in some type of tree structure and keep track of the win/loss ratio for all of them.

3 Simulation (playing random game), what we are doing already.

4 backpropagation. Taking the score the expanded node received and passing it through all the parent nodes adjusting their probability. Remember to consider who has won so that you invert the win/loss ratio from opponent nodes.

The big issue here is that it is easy to run out of memory as you expand. One solution to this is to cap the number of nodes allocated and when you run out of nodes go into a pruning stage where you remove nodes of poorly performing choices. A node pool is a good way of doing this as when the pool is empty, you do a pruning pass adding pruned nodes (including children) back into the pool.

Now that we have several AI agents, we can put together our Christmas game. This will be covered in the next part.

Making Santa-Tac-Toe part 2 of 4

 Part 2: Solving Using a Tree

With the basic game class that was created in the last part, we are ready to create a better player to play against. This is where the computer can have an advantage over us humans as they can examine many more moves per second than we can. This allows more exploration of the possible moves, and with a simple game like Tic-Tac-Toe, can even explore all the possible moves when deciding what move they wish to make. How is this possible? When you think about a game, it can be represented as a tree structure as shown in the image below.

The first move has nine options. The second has 8 options for each of the 9 boards. The third move has 7 options for each of the 72 boards and so on. The total number of board configurations is 9!, which is 9 factorial or 9x8x7x6x5x4x3x2x1 for a grand total of 362,880. As each move leads to a set of other moves, the game can be represented as a tree. The AI then just hast to start on the node of the tree representing the current state of the board then find the move most likely to win. There is one problem, namely that the opponent also wants to win.

We need to be able to pick the best move to make for the computer while also assuming that the opponent will always pick the best move that they can. This may sound like a problem, as what happens if the opponent doesn’t pick the best move? The answer is that the AI will still be in a good position, possibly even able to win the game faster by taking advantage of the mistake. Still, if you are using some of the pruning techniques we will be discussing, this could be a problem as the AI may not have stored information about that move and will have to search from scratch.

The basic approach then is to recursively search the tree taking the best move from whoever the current player is.  As the opponent winning is bad for us, we will invert the score from the opponent so will weigh the moves that the opponent wins as an undesirable position for us. This is implemented as a recursive pair of methods.  ScoreTiles simply takes a board and scores each possible move on the board by calling scoreTile. ScoreTile checks to see if a particular tile is a valid move and if so if that move will result in a win. If the move is not an immediate win or tie, we need to look at the next moves in the game taking the highest score from that and inverting it. This recursion will repeat until a winning or tie move is reached.

scoreTiles(board, curPlayer) {
    let scores = [];

    for (let i = 0; i < 9; ++i) {
        if (board.getTileByIndex(i) === TTTConsts.EMPTY) {
            scores.push(this.scoreTile(board, i, curPlayer));
        } else
            scores.push(TTTConsts.INVALID_MOVE);
    }

    return scores;
}

scoreTile(board, index, curPlayer) {
    if (board.getTileByIndex(index) !== TTTConsts.EMPTY) return TTTConsts.INVALID_MOVE;
    this.testBoard.clone(board);
    this.testBoard.setTileByIndex(index, curPlayer);
    let winState = (curPlayer === TTTConsts.X) ? TTTConsts.X_WON : TTTConsts.O_WON;
    let state = this.testBoard.getGameState();
    if (state.state === TTTConsts.PLAYING) {
        // recurse
        let rboard = new TTTBoard();
        rboard.clone(this.testBoard);
        let opponent = (curPlayer === TTTConsts.X) ? TTTConsts.O : TTTConsts.X;
        let scores= this.scoreTiles(rboard, opponent);
        let highIndex = 0;
        for (let i = 1; i < 9; ++i)
        if (scores[highIndex] < scores[i])
            highIndex = i;
        return -scores[highIndex];
    }
    return (state.state === winState) ? 1 : 0;
}

The getNextMove API call then simply calls the ScoreTiles for the existing move and picks the move with the highest score.

getNextMove(board, playerToMove = TTTConsts.EMPTY) {
    let scores = this.scoreTiles(board, playerToMove);
    console.log(scores)
    // return best move
    let highIndex = 0;
    for (let i = 1; i < 9; ++i)
        if (scores[highIndex] < scores[i])
            highIndex = i;
    return highIndex;
}

The search tree for Tic-Tac-Toe is a small enough tree that we can fully explore it, but what if it is not? More complicated games may not allow for us to search the entire tree in a reasonable timespan. For these games we need to come up with a different way of scoring the state of the board. This will be game specific, but one approach I would consider if there is not a good way of finding a weight for the board would be to recurse to the desired end depth and then simply do a series of random games and return a score based on how many wins occurred. Limiting the depth that you search also is a way to reduce the difficulty of the game.

To speed up searching, there are ways of pruning the search tree. If you assume that your opponent will always take the winning move if it is available, you can stop searching for an opponent move once there is a winning move available. This may not sound like much but can reduce the search by a surprising amount. 

One of the new and highly effective ways of picking moves is the use of the Monty Carlo Tree Search algorithm. We will not be implementing the full algorithm but will do the starting point and explain the algorithm in the next part.