Saturday, May 14, 2022

University Postmortem

 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!


Thursday, April 14, 2022

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.


Monday, March 14, 2022

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.


Monday, February 14, 2022

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.