Thursday, 30 July 2020

Balancing technical uplift with product development

This blog post is taken from chapter 7 of my book "Leading software teams with context, not control". I hope you enjoy it and it entices you to check out my book which is available in eBook and print formats at the above link. 

Closely behind the holy wars of programming languages, is the battle of technical uplift versus product feature development. It exists in every software organisation around the world, however, some are able to better balance the two more evenly. Software developers are best placed to understand how to keep their platforms stable, online and scaling with customer growth demands. This results in the software team typically being motivated in focusing on technical uplift initiatives to improve scalability and reducing technical debt. Whereas the product team knows and understands the customer, and are motivated to continuously find new ways to engage and inspire them. This results in the product team focusing on initiatives that drive new capabilities and features that deliver a better customer experience than their competitors. Finding a technique to balance both of these potentially conflicting and competing priorities can be challenging and fuelled with justified passion from both sides. In mature and collaborative organisations though, it promotes healthy and constructive debates on what initiatives add greater value.

It is important to note that when referring to technical uplift, it is not specifically referring to only technical debt. Although technical uplift sometimes needs to occur due to long standing technical debt, technical debt is the result of specific historical decisions knowingly being made that results in a platform becoming more expensive to maintain or potentially scale. Some technical debt is bad debt, in that the cost of repaying those decisions becomes exponentially higher as time passes. Whereas other debt is more easily repaid at a later point in time. A crucial call out to understand is that new technical debt is accepted and taken on as a team, it isn’t forced onto the team by stakeholders - that is not a software engineering team culture you want to let evolve.

Why the decision is not binary

Balancing technical uplift and product feature build rarely needs to be a binary decision. From a software developer’s perspective, they work day in and day out within the platform’s codebase. They understand many of the pain points that result in scalability issues, areas of the code that every software developer avoids working on because the slightest change can cause unknown production issues, or the frustration of repetitive and manual processes that have evolved over time making the team ineffective. By failing to ensure the software team has a voice in prioritising technical uplift can result in three key impacts. Firstly, the organisation is not trusting the most experienced people working on the platform who understand the key technical issues being faced and how to improve them. Secondly, the organisation is not solving fundamental problems within the platform that will enable faster and more effective development and deployment of new product features into production. Lastly, without trusting the team and empowering them to improve the codebase and platform, it will be detrimental to the culture within the team and ultimately the higher performing software developers will disengage and move on.

From the product perspective, product owners and product managers attempt to deliver the best possible customer experience. They listen to customers, gather feedback and aspire to release a range of new features to continually attract new customers or retain existing ones. They understand that doing this well will lead to an increase in profitability for the organisation. By not prioritising the development of new capabilities, a platform will be irrelevant as it eventually loses customers to competing organisations and platforms. The thought of losing customers is demotivating for anyone working within a product role and can lead to an increased turnover of product owners and managers within the organisation.

As mentioned above this is not a binary decision, in that an organisation does not have to focus 100% on technical uplift or 100% on product feature build. A healthy balance needs to be found between the two to ensure platform scalability, new product development and retention of team members within the organisation. Even an early stage startup focused entirely on growth needs to dedicate a percentage of time on technical uplift to ensure platforms don’t become too expensive to scale and maintain which is known to have crippled many startups throughout their scale-up phase. Twitter shared an insightful post on their blog many years ago that spoke to serious performance issues in relation to their search capability. It was a result of years of technical debt in their Ruby codebase which made it challenging to add features and improve the reliability of their search engine. However, the organisation trusted and empowered the software engineering team to implement a solution which resulted in the rewrite of their search capability which improved searching speeds on twitter three fold.

Don’t be binary

In a previous software leadership role, I remember walking into a team facing considerable technical challenges specific to the scalability of the platforms running in production. This was due to the organisation scaling up incredibly quickly over their recent years which had resulted in unfortunate architectural decisions being made, as well as a continual focus on product growth with little to no priority on technical uplift. The software team was frustrated and they were beginning to see a higher than normal number of resignations. This needed to be resolved. Over the next 24 months the team began focusing their efforts on fundamental technical uplift. Platforms were decommissioned, others were re-architected, all alongside a much needed modernisation of software engineering tools and practices. The team was investing effort into rapidly evolving their platforms to support the organisation’s expansion aspirations. The first 18 months brought a breath of fresh air within the software team as there was now motivation and support to improve. At this point in time, the software teams were focusing on average 80% of their efforts on technical uplift which was the nearly exact opposite 18 months prior. Throughout the next six months though, the team that had once only wanted to improve their technology and platforms began to question their purpose within the organisation. Sure, their platforms were considerably more stable and scalable, they were even able to deploy production changes within hours instead of months, but something was missing. The organisation's product vision was missing and teams started asking questions:
  • Why are we building this product?
  • Who are our actual customers?
  • What is our vision for this product?
The mindset across the group began showing signs of drifting back to where it was 18 months prior, which leads me to the point. It is unhealthy to have a software team focus 100% of their effort on technical uplift and ignore product feature development. Likewise you cannot expect a software developer to remain engaged if focusing solely on product feature development and disregarding any technical uplift or hygiene. A balance is required, and this balance is different in every team. This balance may also evolve every 6-12 months due to an organisation's ever changing environment. As a software leader, you need to be constantly pulse checking where teams are spending their effort. Your role is to motivate teams with a balance of technical uplift and product feature development and ensure a purpose for both exists, and is known.

How to find a healthy balance

To solve the challenge between technical uplift versus product feature development it is important to accept that there needs to be a balance of the two at all times. Rarely if ever, will a team need to focus 100% of their effort on one or the other, nor should you want a team to due to the reasons discussed above. As with most aspects of software leadership there isn’t a single approach that can be taken to achieve this outcome. However, the below approaches act as guidelines that can help ensure a balance between technical uplift and product feature development.

Clarify and make clear responsibilities

It is important the software team is responsible and given ownership for two distinct areas. The first being how a feature is solutioned. Software developers are the closest to the code, they understand the impacts different solutioning decisions have on the maintainability and scalability of the codebase. Ensuring software teams own solutioning, it avoids non-technical individuals outside of the team who are less qualified making fundamental technical decisions that could be detrimental to the health of the platform. As part of solutioning, teams should always gather input from relevant stakeholders but this is purely in a consultative capacity. This will also reduce the potential of corners being cut in solutions that normally always results in incurring technical debt.

The second is owning work effort. The software team undertakes the development, testing and deployment of work items, thus are the only ones qualified to estimate the work effort required. Is it impossible and naive to believe a stakeholder can define the work effort required by the team when they do not understand the low level intricacies of the platform. Stakeholders are in their right and should share constraints that may be related to compliance, marketing deadlines or similar with the team. If a stakeholder attempts to define work effort and commit a team to it, as a software leader you need to clearly set expectations that they do not have the relevant expertise to make this decision and that it is up to the team to own work effort estimation. It can be necessary to communicate this message with senior leaders across the organisation, while keeping individuals honest when noticing it occurring.

Where a stakeholder may get involved in conversations is around scaling back feature scope to reduce work effort required if there are legitimate time constraints. By allowing the software team to own work effort estimation you are ensuring that non-functionals are taken into account, that technical unknowns are accounted for, and that the team will solution in line with the software team's target state.

Making technical uplift visible

If technical uplift is not documented, not prioritised and not made visible, team's will always struggle to make progress in it. It would be like walking up an escalator in the wrong direction, the amount of additional effort required is considerably more. Teams wouldn’t and shouldn’t start work on a new product feature without first understanding the outcomes, the priority, defining relevant user stories and documenting a solution. Why should technical uplift work be any different? Documenting technical uplift involves the team defining their most important initiatives, determining the value, prioritising them relative to each other and then work effort estimating them as a team. Try to focus on the immediate top 10 technical uplift initiatives compared to hundreds to avoid overwhelming not just the team but the wider organisation. With technical uplift documented it can now have an opportunity to be discussed and prioritised alongside other priorities coming into the team. It is no longer a hidden list of vague work items in the minds of people within the team.

Justifying technical uplift initiatives smarter

Outside of making technical uplift visible, the other single reason why it can struggle to be prioritised comes down to an inability to justify it in a way that is understood by the organisation. As a software leader you are responsible for being the voice of reason and support when it comes to prioritising technical uplift. Your role needs to understand how the organisation justifies and prioritises initiatives so you can apply the same approach to technical uplift. Below are three common ways organisations prioritise:
  • Return on Investment (ROI):
    • ROI = total estimated value / cost to implement
    • Cost to implement includes all costs associated to develop and maintain including people costs, infrastructure costs, license costs etc..
  • Competitor feature parity.
  • Cost of Delay (CoD) is the cost to the organisation of not implementing the feature by a certain point in time. This may be lost revenue, compliance fines or lost customers due to a competitor moving faster.
Organisations will quite often use a combination of prioritisation methods as they mature to ensure a more complete justification. By understanding and applying the same justification to technical uplift initiatives it creates a level playing field allowing apples to be compared with apples.

Let’s explore a simple example using ROI as the only method to prioritise both a technical uplift or product initiative across an organisation. The product initiative will bring $240,000 of profit in the first year, at a total work effort cost of $75,000 (which equates to three software engineers for three months earning $100,000 a year). There is also a yearly cloud infrastructure cost of $12,000. ROI for the first year is calculated by:
  • ROI = total profit / total cost
  • ROI = $240,000 / ($75,000 + $12,000)
  • ROI = 2.75

This provides an ROI of 2.75.

The technical uplift initiative will deliver $420,000 of savings by deprecating a legacy platform reducing the need for a small team currently supporting it. The total work effort cost is $100,000 (which equates to 2 software engineers for 6 months earning $100,000). ROI is calculated by:
  • ROI = total profit / total cost
  • ROI = $420,000 / $100,000
  • ROI = 4.2
This provides an ROI of 4.2.

Without taking into account any other prioritisation approach it is clear that the technical uplift initiative provides a higher ROI to the organisation and should potentially be prioritised first.

It is also within your best interest to think carefully about the real costs of managing platforms that technical uplift will simplify and improve. If an initiative is wanting to automate deployment pipelines for a specific platform, it is valuable to understand the costs in maintaining the existing manual deployment processes. You may have four teams spending three hours each week manually releasing code. Over the course of just one year the team would spend $31,200 worth of effort manually releasing. This cost will continue to be incurred every year until the deployment process is automated. The cost of manually deploying also takes precious capacity away from developing new product features. When describing impacts and value in this way, it becomes even easier to rally support from product management as they are selfishly (and rightly so) focused on delivering more product features, faster.

Finally, it is in your best interest to coach software leaders within your team on these prioritisation approaches. This will result in many of the justification and prioritisation conversations being able to happen directly within the team and avoid the need for your role to become involved in every single one of them.

Coupling technical uplift with product features

Sounds simple right? If your organisation is product led, there will be a never ending list of new product initiatives in the backlog. One of your responsibilities of a software leader is to continually look for opportunities and synergies between technical uplift initiatives and new product initiatives. By coupling a new product feature with a relevant technical uplift improvement that resides in the same area of the codebase, it can often reduce effort around testing which creates efficiencies when compared to delivering them both in isolation.

For example, there may be a product feature to implement an additional payment provider to the customer. Within the technical uplift backlog there could be an initiative to improve the level of unit testing that exists within the platforms payment service. There is a clear relationship between these two items of work. In terms of efficiency, there is a benefit to increase the unit testing coverage within the payment service while adding an additional payment provider. Not only do these two initiatives reside in the same area of the codebase, but the work effort in completing them together is also less than the sum of both their work efforts in isolation. This is a result of the effort required to test the platform's payment implementation can be performed just once, not twice. Secondly, the software developers will already be familiar with the payment section of the codebase thus being more efficient, rather than context switching back at a future point in time.

Another example may revolve around the need to support demand in customer growth which requires introducing additional servers into the rotation. The software team also has a technical uplift initiative in the backlog to move all cloud infrastructure into code. Taking a short term tactical approach would see the team simply add an additional server manually into the rotation pool. However, this wouldn’t move the software team any closer to their target state of infrastructure as code. An approach could be to implement the additional server as infrastructure as code, but manually add the server into the rotation. This provides the benefit of meeting the product requirement but also aligning a portion of the work to the software teams target state without re-implementing the entire load balancing capability as code. Of course, if it is possible to also move the load balancer to infrastructure as code, it should be considered.

Identifying synergies between technical uplift and product initiatives has been one of the most successful approaches I have been able to follow to ensure a healthy balance.

Larger technical uplift sometimes requires a project

In some instances, a technical uplift initiative is simply too large in work effort to be coupled into a product initiative. A fundamental goal of software teams is to ensure they release small and release often. This implies avoiding weeks or even months of code not being released into production. When a technical uplift initiative requires considerable work effort to see it through to completion, it needs to be treated as a project. This involves defining clear outcomes, measures of success, documenting high level scope usually as user stories, estimating work effort and a justification aligned to the organisation's process.

Using the technical uplift example of implementing an automated build pipeline, the justification may look like:
  • The current cost to the organisation of not implementing
    • Four teams each undertake one release every week.
    • Each release costs four hours of work effort.
    • As each release is after hours it also incurs three hours Time in Lieu (TIL).
    • This sums up to 1,456 hours a year releasing features.
    • This equates to $72,800.
  • Total cost in work effort to implement is 988 hours
    • This equates to two software engineers for three months.
    • The total work effort costs $49,400.
  • By entirely automating the platforms build pipelines, after the first year there will be a cost saving of $23,400 and then $72,800 for subsequent years.
That is a very persuasive justification as this initiative pays for itself after just 9 months. Taking it one step further, as the teams are now able to release new product features with zero manual effort it enables smaller feature releases more frequently. This reduces production deployment risks while delivering value add features to customers faster than ever before. I would challenge you to find any product role who wouldn’t support this initiative within the organisation.

Ensuring a combined organisational roadmap

In many organisations it can make sense to have a separate technical uplift roadmap and product initiative roadmap. This can support a more efficient planning process within specific teams as these roadmaps are often owned by different leaders. However, at an organisational level when organisational priorities are published, it is imperative to have a single and aligned roadmap that includes both technical uplift and product initiatives prioritised side by side.

Breaking down larger technical uplift initiatives

The larger the work effort is for an initiative, the harder it is going to be to justify and prioritise. Organisational leaders usually struggle to support large initiatives as their value won’t be realised for a considerable time into the future. Prioritising a six month work effort product initiative is challenging enough, let alone a six month technical uplift initiative. As a software leader, you need to be continuously looking for ways to break larger initiatives into smaller work items that can be delivered into production sooner.

For example, take the technical initiative to implement a new organisational wide logging and monitoring platform that has a total work effort of seven months. By breaking it down into smaller work items as seen below, the effort required to justify is greatly decreased, risks are reduced and work items that can run in parallel may become more clear.
  1. One sprint to research and document a solution.
  2. Three sprints to build out the base logging and monitoring platform.
  3. Two sprints to upskill and train all software teams.
  4. Three sprints to integrate logging into the first platform.
  5. One sprint to implement monitoring into the first platform.
  6. ... Repeat steps 4 and 5 for each additional platform.
Always focus on finding the smallest item of work that can be released into production that still adds value to the organisation.

Definition of Done

A Definition of Done (DoD) is essential for every software team to define and proactively adhere to. The purpose of a Definition of Done is to improve the overall quality of the capabilities that the team deploys into production. Quite often a Definition of Done includes specific non-functional requirements (NFRs) that a team values, which may include:
  • Automated testing exists for each feature.
  • Solution and code has been peer reviewed.
  • Documentation has been created or updated.
  • Monitoring has been implemented to ensure observability of all critical paths.
  • Product owner has reviewed and signed off on the new capability.
A Definition of Done does not reduce existing technical debt, however, it plays a part in reducing new technical debt being created which would otherwise need to be paid back in the future.

TL;DR

  • The decision between technical uplift and product initiatives shouldn’t be a binary decision. An organisation needs to find a healthy balance between the two to ensure platform scalability, new product development and retention of team members.
  • Technical uplift initiatives need to be documented, prioritised and made visible to the wider organisation otherwise the team will always struggle to make progress.
  • Continually look for opportunities to couple technical uplift with new product initiatives. This will encourage efficiencies by reducing testing time and reducing context shifting the software team may face by tackling both initiatives separately.
If you enjoyed this blog post, you can check out my book "Leading software teams with context, not control", that has 22 other chapters on leading software teams. You can purchase it from Leanpub as well as other online stores like Amazon in eBook or print format.


Tuesday, 28 July 2020

I've written a book about leading software engineering teams

Ten months ago I set myself a one year goal to write a book on leading software engineering teams. This books purpose was to document the practices and initiatives I followed while leading software teams. It was to provide myself with a reference model to refer back to and reduce the cognitive load required within my day to day role. What started off as a casual few hours a week planning and firming up the books chapter, rapidly turned into 3+ hours every night researching, writing, rewriting, deleting and writing some more in an effort to complete this side project before our first baby was born. I didn't exactly make the 9 month deadline, but published v1.0.0 three days later. The book is titled "Leading Software Teams with Context, Not Control" and can be purchased from Leanpub as well as other online stores like Amazon in eBook or print format .

Why this book was written

As a software engineering leader, the scope of your role is extensive. You have many competing responsibilities and priorities that need to be balanced to ensure you and your team are as effective as possible. These can include providing architectural direction, driving peer to peer collaboration, ensuring cross-team alignment, motivating teams with purpose, supporting team members' career progression, or perhaps helping remove blockers and impediments. All of these efforts work to create a specific culture within a software team that aims to improve effectiveness, engagement, and retention.

I wrote this book for software leaders who are responsible for leading teams. More specifically it focuses on approaches for leading multiple software teams whether that is directly or indirectly through leadership roles reporting into your role. There is a level of unique complexity that comes with leading, aligning and supporting multiple software development teams. This book aspires to provide you with helpful and reusable approaches that can be leveraged to bring about a greater level of efficiency into your role as a leader. There are many books written around leading teams or leading people, this book takes a lens of what specific practices and initiatives you should be investing your time into when leading technical software teams.

Regardless of the size of your software team, if you find yourself needing to better balance both the technical and people aspects of leading teams, or guidance on initiatives you could be running to improve team alignment, effectiveness and engagement then this book is written for you.

What's in the book?

The book comprises of 23 chapters that discuss a broad range of initiatives you can run when leading software engineering teams. These range from baselining a software team to effective software engineering metrics to crafting an experimentation culture. The book is broken into 3 parts:
  • Part 1: Creating alignment
  • Part 2: Leading teams
  • Part 3: Uplifting team culture
Each chapter has a loose structure of explaining the topic, talking to why it is important within a software engineering team and different approaches you can use to implement within your own team. Most chapters include multiple exercises that you can adopt into your organisation, as well as the occasional story around specific experiences I have had while leading teams in my previous and current roles.

Interested in more insight to exactly what is in each chapter just incase it tempts you to pick yourself up a copy? Here it is...

Part 1: Creating alignment

  1. Baselining a software team
    All the thing you need to do to understand the current state of your software engineering team. It talks to technical and team cultural measures and techniques to determine a teams baseline.
  2. Defining a software team target state
    A software target state is the technical and non-technical aspirations of the team that are flags on the top of the hill for you and your team to continuously climb towards. Learn how to define a software target state for your team.
  3. The software engineering roadmap
    A software engineering roadmap is a visual representation that defines a team's pathway to achieving their target state. This chapter explains the importance and how to implement one.
  4. Effective software team metrics
    Metrics within software are measurements that are put in place to keep you and your teams honest, accountable and continuously improving. Learn about what makes good team metrics, as well as metrics you need to avoid.
  5. Importance of collaborating on team goals
    Setting goals for your team or team members does not need to be an overly time consuming exercise, although it does need to align to your team target state, roadmap and team metrics.
  6. Balancing reactive versus strategic work
    Getting stuck in the weeds is all too common for software engineering teams, learn about strategies to better balance the time you spend on strategic based work items.
  7. Balancing technical uplift with product development
    The decision between technical uplift and product initiatives shouldn’t be a binary decision. Discover approaches to find a healthy balance between the two to ensure platform scalability, new product development and retention of team members.
  8. Introducing a new technology
    As a software leader, you are accountable for ensuring relevant new technology is being adopted within your team at a healthy and manageable pace. This is compared to implementing too many technologies too quickly and running the risk of losing great software developers from technology change fatigue or cognitive overload due to overly complex platforms.
  9. Platform SLAs
    Discover SLAs that add value to a platform, as well as important items to consider when implementing SLAs for your software teams platforms.

Part 2: Leading teams

  1. Effective 1:on:1s
    1:on:1s are weekly or fortnightly catch-ups with each of your direct reports, that provide an opportunity for you to listen, provide guidance, coach, listen more and support them within their role and future career aspirations. Find out about approaches to make the most out of 1:on:1s within your team.
  2. Continuous performance feedback
    Performance feedback within software teams should more than a once yearly exercise that is orchestrated through the organisation's HR department. There are many opportunities to provide constructive feedback to your team every day of the week.
  3. Impactful position descriptions
    Position descriptions are short (no more than 3 pages), well formed documents that clearly articulate the impact a role has, where it sits within the organisation and breaks down the key responsibility areas of that role. Discover how to craft position descriptions that create a sense of excitement and motivation within a role that is genuinely valued within the organisation.
  4. Candidate centric interviews
    Understand what candidate centric interviews are and how they build trust between the interviewer and the candidate which results in them being more genuine about their experiences, concerns in the role and their career aspirations. While at the same time becoming more invested in the role within the team.
  5. Onboarding effectively
    Effective onboarding should include a combination of discussions, introductions, workshops, documentation sharing and mentoring to support new starters in becoming a motivated and effective team member. This chapter explains the different phases of onboarding to focus on within your software teams.
  6. Software team structures
    Learn how to implement ‘just enough hierarchy’ while coupling it with small team sizes of seven or less, to dramatically reduce the blast radius and impact when an individual chooses to move on from the organisation. 
  7. Career pathway framework for software teams
    A software career pathway framework links together roles to represent different pathways of progression an individual can follow to advance their career within the team that aligns with their skills, experience and motivation. It is not a trivial task, however this chapter aims to provide some key learnings to fast track your own implementation.

Part 3: Uplifting team culture

  1. Context over control
    It is in the title of this book, and this chapter explains how a context over control approach allows software leaders to lead vastly larger teams and projects when compared to a micromanagement approach.
  2. Engaging team meetings
    As a software leader you are accountable for ensuring weekly team meetings are set up, are engaging, have the right amount of energy and bring value to as many individuals within that session as possible.
  3. Team health checks
    Team health checks usually consist of six to ten questions that focus on technical, team and communication practices that each team discusses and rates every six to eight weeks. Understand what makes health checks valuable and approaches on running health checks within your teams.
  4. Building a culture of learning
    A software team that is built around a culture of learning allows its members to learn in all aspects of their role. Learn about how building a culture of learning can be achieved at no financial cost to the organisation.
  5. Crafting an experimentation culture
    Software teams that embrace an experimentation culture have a more maintainable technology stack, incur less technical debt, and are thus able to iterate faster on developing and releasing new capabilities. Discover approaches to encourage experimentation in every aspect of your teams day to day.
  6. Software engineering working groups
    Software engineering working groups involve a set of individuals working together to build a center of excellence around a specific topic. This chapter explains different approaches of implementing working groups within your organisation.
  7. Running a software team hack day
    Running a hack day allows your teams to take a break from the day to day and collaborate together on solving real software engineering problems being faced. Learn about a high level structure and run sheet you can use to run your very own hack day.
Although this goal can now be ticked off my list, I'm looking forward to many future iterations as I evolve my ways of running software engineering teams. If you would like to check out a free sample, you can download it over at Leanpub. eBook formats are available on Leanpub, Amazon, Google Play and iBooks. Print copies can also be purchased from Amazon.


Monday, 8 July 2019

NeuroEvolution using TensorFlow JS - Part 3

Introduction


This tutorial is part 3, if you have not completed NeuroEvolution using TensorFlowJS - Part 1 and NeuroEvolution using TensorFlowJS - Part 2, I highly recommend you do that first. As it will:
  • Explain how to setup the codebase
  • Teach you how to code a basic NeuroEvolution implementation
  • Improve the performance of the NeuroEvolution
  • Implement the ability to save/load models
In this last tutorial we will:
  • Learn how to use simple shape/object/color detection to gather the inputs required to feed into TensorFlow JS (instead of interacting directly with the GameAPI object)
This tutorial is also based on the source code found on my GitHub account here https://github.com/dionbeetson/neuroevolution-experiment.

Let's get started!

Create base class

We need to create a class that will be used instead of GameAPI to gather all of the required inputs from the game every 10ms and then pass them to TensorFlow JS to make the same prediction to jump or not.

Disclaimer:
  • There is already logic in js/ai/Ai.js to initialise this class if you select the checkbox 'Use Object Recognition' in the UI
  • There are a few inputs small items we are not decoupling from the original GameAPI (eg: getScore()), as it was outside the scope of my experiment. But it could be implemented if we really wanted to.
How it works

  1. Every 10ms the game will execute a method to 
    1. Extract an image from the game canvas
    2. Convert the image to greyscale
    3. Using a 10x10 pixel grid create a layout of the level in regards to:
      1. What is whitespace (color=white)
      2. What are obstacles to jump over (color=grey)
      3. Where the player is (color=black)
    4. Look ahead 4 blocks (40 pixels) and determine if there is a block or dip to jump over
    5. Determine the x/y coordinates that can feed into TensorFlowJS
    6. Ai.js will then use the same logic as the previous tutorials to determine to jump or not

Create a file called js/ai/GameImageRecognition.js and then paste in the below code.

js/ai/GameImageRecognition.js

class GameImageRecognition {
}
Lets now create the start() method which is called by default in Ai.js which will start the game, setup the canvas tracker (which is essentially a new hidden canvas DOM element that we paint an image of the game canvas into every 10ms) and use it for detecting shapes/objects/player position etc...

js/ai/GameImageRecognition.js

start() {
  const self = this;

  this.#enableVision = document.querySelector("#ml-enable-vision").checked;

  // @todo - remove dependency on gameAPI object - although outside of scope of this example
  this.#gameApi.start();
  this.setupCanvasTracker();

  // Simulate what happens in the game
  setTimeout(() => {
    self.#isSetup = true;
  }, 100);
}
We will also add in a few other helper functions to get things moving.

js/ai/GameImageRecognition.js

setupCanvasTracker(){
  this.#visualTrackingCanvas = document.createElement("canvas");
  this.#visualTrackingCanvas.setAttribute("width", this.#gameApi.getWidth());
  this.#visualTrackingCanvas.setAttribute("height", this.#gameApi.getHeight());
  this.#visualTrackingCanvas.setAttribute("class", "snapshot-canvas");

  this.#gameApi.getContainer().appendChild(this.#visualTrackingCanvas);
  this.#gameApiCanvas = this.#gameApi.getCanvas();
}

setHighlightSectionAhead(index) {
  // Not required for this demo
  return;
}

isOver() {
  return this.#gameApi.isOver();
}

isSetup() {
  return this.#isSetup;
}
As well as some required class variables

js/ai/GameImageRecognition.js

#gameApi = new GameApi();
#gameApiCanvas;
#isSetup = false;
#visualTrackingCanvas;
#enableVision = false;
Now wire up the UI event handler

js/ai/ui.js

document.querySelector("#ml-use-object-recognition").addEventListener("change", function() {
  if ( this.checked ) {
    neuroEvolution.useImageRecognition = true;
  } else {
    neuroEvolution.useImageRecognition = false;
  }
});
And add in the required setters for useImageRecognition

js/ai/NeuroEvolution.js

set useImageRecognition( useImageRecognition ) {
  this.#useImageRecognition = useImageRecognition;
}
Reload your browser (http://127.0.0.1:8080/), check 'Use Object Recognition' and click 'Start evolution' button. You should see the games begin, but get a lot of game.gameApi.getPlayerY is not a function errors. This is because we need to implement a range of functions to gather input.
Before we do that though, we will add in the logic to extract information from the game canvas every 10ms.

js/ai/GameImageRecognition.js


// Method to extract data from canvas/image and convert it into a readable format for this class to use
extractVisualTrackingData(){
  let data = this.#gameApiCanvas.getContext('2d').getImageData(0, 0, this.#visualTrackingCanvas.width, this.#visualTrackingCanvas.height);
  let dataGrey = this.convertImageToGreyScale(data);

  this.#visualTrackingMap = this.generateVisualTrackingMap(dataGrey, this.#visualTrackingCanvas.width, this.#visualTrackingCanvas.height, this.#visualTrackingMapSize, this.#colors);

  this.updatePlayerPositionFromVisualTrackingMap(this.#visualTrackingMap, this.#colors);

  this.#sectionAhead = this.getSectionAhead(this.#playerX, this.#playerY, 4, this.#visualTrackingMapSize, this.#playerGroundY);
}

// Method to create an object indexed by xposition and yposition with the color as the value, eg: 10x40 = grey
generateVisualTrackingMap(data, width, height, visualTrackingMapSize, colors) {
  let visualTrackingMap = {};
  for( let y = 0; y < height; y+=visualTrackingMapSize ) {
    for( let x = 0; x < width; x+=visualTrackingMapSize ) {
      let col = this.getRGBAFromImageByXY(data, x+5, y+5)
      let key = x+'x'+y;
      visualTrackingMap[key] = colors.background;

      if ( 0 == col[0] ) {
        visualTrackingMap[key] = colors.player;
      }

      if ( col[0] > 210 && col[0] < 240 ) {
        visualTrackingMap[key] = colors.block;
      }
    }
  }

  return visualTrackingMap;
}
These above functions have extra dependencies. Let's add in functionality to convert an image into greyscale, as well as get the RGBA from a specific pixel on that image.

js/ai/GameImageRecognition.js

convertImageToGreyScale(image) {
  let greyImage = new ImageData(image.width, image.height);
  const channels = image.data.length / 4;
  for( let i=0; i < channels; i++ ){
    let i4 = i*4;
    let r = image.data[i4 + 0];
    let g = image.data[i4 + 1];
    let b = image.data[i4 + 2];

    greyImage.data[i4 + 0] = Math.round(0.21*r + 0.72*g + 0.07*b);
    greyImage.data[i4 + 1] = g;
    greyImage.data[i4 + 2] = b;
    greyImage.data[i4 + 3] = 255;
  }

  return greyImage;
}

getRGBAFromImageByXY(imageData, x, y) {
  let rowStart = y * imageData.width * 4;
  let pixelIndex = rowStart + x * 4;

  return [
    imageData.data[pixelIndex],
    imageData.data[pixelIndex+1],
    imageData.data[pixelIndex+2],
    imageData.data[pixelIndex+3],
  ]
}
Add these class variables as well

js/ai/GameImageRecognition.js

#visualTrackingMap = {};
#visualTrackingMapSize = 10;
#sectionAhead = [];
#playerX = 0;
#playerY = 0;
#playerGroundY = 0;
#colors = {
  block: 'grey',
  visionOutline: 'red',
  player: 'black',
  background: 'white'
};
Now we want to add in 3 methods that will be called from Ai.js to detect some of the inputs from the previous tutorials.

js/ai/GameImageRecognition.js

getHeight() {
  return this.#visualTrackingCanvas.height;
}

getWidth() {
  return this.#visualTrackingCanvas.width;
}

getPlayerY() {
  return this.#playerY;
}
Reload your browser (http://127.0.0.1:8080/), check 'Use Object Recognition' and click 'Start evolution' button. Again, you should see the games begin, but now get a lot of game.gameApi.getPlayerX is not a function errors. Ok, we are making progress, let's implement this method.
This method is actually the method we hook into to do all of the processing of the games canvas. Realistically we could have pulled this out into it's own setInterval(), but for the purpose of this demo let's couple it in with getPlayerX() which is called within every think() invocation.

js/ai/GameImageRecognition.js

getPlayerX() {
  this.extractVisualTrackingData();
 
  return this.#playerX;
}
Now add in a method to determine the players x/y position on the canvas (we do this by finding the 10x10 pixel that is color #000000 (black)). Simple, yet effective.

js/ai/GameImageRecognition.js

updatePlayerPositionFromVisualTrackingMap(visualTrackingMap, colors) {
  for (const xy in visualTrackingMap) {
    let value = visualTrackingMap[xy];

    if ( colors.player == value) {
      let position = xy.split('x');
      this.#playerX = parseInt(position[0]);
      this.#playerY = parseInt(position[1]);

      // If we dont have a ground, then set it
      if( 0 == this.#playerGroundY ) {
        this.#playerGroundY = this.#playerY;
      }
    }
  }
}
Next up is a lot of logic to look through visualTrackingMap which stores all the colors of each 10x10 pixel section and determine what lies ahead in relation to the player.

js/ai/GameImageRecognition.js

getSectionAhead(playerX, playerY, aheadIndex, pixelMapSize, playerGroundY){
  let x;
  let y;
  let section;
  let aheadWidth = aheadIndex*10;

  x = Math.ceil(playerX/pixelMapSize) * pixelMapSize + aheadWidth;
  y = Math.ceil(playerY/pixelMapSize) * pixelMapSize;

  section = this.getCollisionSectionAhead(x, y);

  if( false == section ) {
    section = [x, playerGroundY+pixelMapSize, pixelMapSize, pixelMapSize];
  }

  return {
    x: section[0],
    y: section[1],
    width: section[2],
    height: section[3],
  };
}

// Logic to get the xy and width/height of the section ahead that we need to use to determine if we jump over or not
getCollisionSectionAhead(x, y) {

  // Look for drop/dip section ahead we need to jump over
  y = this.#playerGroundY;

  if ( this.isSectionSolid(x, y) ) {
    // Look for taller section ahead we need to jump over
    let xyStart = this.findTopLeftBoundsOfSolidSection(x, y-this.#visualTrackingMapSize);
    let xyEnd = this.findTopRightBoundsOfSolidSection(xyStart[0], xyStart[1], 1);
  
    return [xyStart[0], xyStart[1], xyEnd[0] - x, y - xyEnd[1] + this.#visualTrackingMapSize];
  } else {

    if (  false === this.isSectionSolid(x, y+this.#visualTrackingMapSize) ) {
      let xyStart = this.findBottomLeftBoundsOfSolidSection(x, y);
      let xyEnd = this.findBottomRightBoundsOfSolidSection(xyStart[0], xyStart[1], 1);

      return [xyStart[0], xyEnd[1]+this.#visualTrackingMapSize, xyEnd[0] - x, this.#visualTrackingMapSize];
    }
  }

  return false;
}

isSectionSolid(x, y){
  let section = this.#visualTrackingMap[x + 'x'  +y];
  if ( this.#colors.block == section ) {
    return true;
  }

  return false;
}

findTopLeftBoundsOfSolidSection(x, y) {
  if ( this.isSectionSolid(x, y) ) {
    return this.findTopLeftBoundsOfSolidSection(x, y-this.#visualTrackingMapSize)
  }

  return [x,y+this.#visualTrackingMapSize];
}

findTopRightBoundsOfSolidSection(x, y, counter) {
  if ( counter < 5 && this.isSectionSolid(x, y) ) {
    counter++
    return this.findTopRightBoundsOfSolidSection(x+this.#visualTrackingMapSize, y, counter)
  }

  return [x,y];
}

findBottomLeftBoundsOfSolidSection(x, y) {
  if ( false === this.isSectionSolid(x, y) && y < this.#visualTrackingCanvas.height) {
    return this.findBottomLeftBoundsOfSolidSection(x, y+this.#visualTrackingMapSize)
  }

  return [x,y-this.#visualTrackingMapSize];
}

findBottomRightBoundsOfSolidSection(x, y, counter) {
  if ( counter < 5 && false === this.isSectionSolid(x, y) ) {
    counter++
    return this.findBottomRightBoundsOfSolidSection(x+this.#visualTrackingMapSize, y, counter)
  }

  return [x,y];
}

getSectionFromPlayer(index) {
  return {
    x: this.#sectionAhead.x,
    y: this.#sectionAhead.y,
    width: this.#visualTrackingMapSize,
    height: this.#playerY-this.#sectionAhead.y
  };
}
I will be the first to admit the above logic is not clean/performant and can really be improved. But the purpose of this demo was to prove what is possible - feel free to submit a PR if you want to improve :-)
Getting closer... Reload your browser (http://127.0.0.1:8080/), check 'Use Object Recognition' and click 'Start evolution' button. You should now see a lot of game.gameApi.isPlayerJumping is not a function errors. Let's implement that and a few other methods that are needed regarding the player.

js/ai/GameImageRecognition.js

isPlayerJumping() {
  if( this.#playerY < this.#playerGroundY ) {
    return true;
  }

  return false;
}

getPlayerVelocity() {
  return 0;
}

canPlayerJump() {
  if( this.isPlayerJumping() ) {
    return false;
  }

  return true;
}
Reload your browser (http://127.0.0.1:8080/), check 'Use Object Recognition' and click 'Start evolution' button. You should now see a lot of game.gameApi.setDebugPoints is not a function errors. Let's implement.

js/ai/GameImageRecognition.js

setDebugPoints(debugPoints) {
  this.#gameApi.setDebugPoints(debugPoints);
}
We are actually missing a key method jump(). For the sake of this demo, we are just going to revert to calling the GameAPI. We could simulate this with a bit of trickery by focusing in on the canvas and triggering the 'spacebar' button. But a little too much for this demo.

js/ai/GameImageRecognition.js

jump(){
  // The only way to simulate this is by pressing the spacebar key, but because we have multiple games at once it isn't easily possible.
  this.#gameApi.jump();
}
Reload your browser (http://127.0.0.1:8080/), check 'Use Object Recognition' and click 'Start evolution' button. You should now see the game mostly work, although a few errors will pop up. Add in the below.

js/ai/GameImageRecognition.js

getProgress() {
  return this.#gameApi.getProgress();
}

getScore() {
  return this.#gameApi.getScore();
}

isLevelPassed() {
  return this.#gameApi.isLevelPassed();
}

remove() {
  if( null !== this.#visualTrackingCanvas.parentNode ) {
    this.#visualTrackingCanvas.parentNode.remove();
  }
}

show() {
  if( null !== this.#visualTrackingCanvas.parentNode ) {
    this.#visualTrackingCanvas.parentNode.classList.remove('game-container-hide');
  }
}
Reload your browser (http://127.0.0.1:8080/), check 'Use Object Recognition' and click 'Start evolution' button. Everything should work now, if you let it go it will eventually solve all of the levels.
However... Wouldn't it be nice to see what the ML is actually seeing on each game? Let's add in some debugging info

js/ai/GameImageRecognition.js

drawRectOnCanvas(rect, color) {
  let context = this.#visualTrackingCanvas.getContext('2d');
  context.beginPath();
  context.strokeStyle = color;
  context.lineWidth = "1";
  context.rect(rect.x, rect.y, rect.width, rect.height);
  context.stroke();
}

// Function responsible for drawing what the computer sees, we then use this to get the inputs for tensorflow
drawMachineVision() {
  if( this.#enableVision ) {
    // Clear everything first
    this.#visualTrackingCanvas.getContext('2d').clearRect(0, 0, this.#visualTrackingCanvas.width, this.#visualTrackingCanvas.height);

    // Draw player
    this.drawRectOnCanvas({
      x: this.#playerX,
      y: this.#playerY,
      width: this.#visualTrackingMapSize,
      height: this.#visualTrackingMapSize,
    }, this.#colors.visionOutline);

    // Draw map sections
    for (const xy in this.#visualTrackingMap) {
      let value = this.#visualTrackingMap[xy];

      if ( this.#colors.block == value) {
        let position = xy.split('x');
          this.drawRectOnCanvas({
          x: parseInt(position[0]),
          y: parseInt(position[1]),
          width: this.#visualTrackingMapSize,
          height: this.#visualTrackingMapSize
        }, this.#colors.visionOutline)
      }
    }


    this.drawRectOnCanvas({
      x: this.#sectionAhead.x,
      y: this.#sectionAhead.y,
      width: this.#sectionAhead.width,
      height: this.#sectionAhead.height,
    }, 'blue');
  }
}
Then change the method getPlayerX() to look like this.

js/ai/GameImageRecognition.js

getPlayerX() {
  this.extractVisualTrackingData();
  this.drawMachineVision();
  return this.#playerX;
}
Reload your browser (http://127.0.0.1:8080/), check 'Use Object Recognition', check 'Enable ML vision' and click 'Start evolution' button. You should now see lots of red boxes that highlight what the ML is actually using as inputs. You're browser will most likely struggle, however it will work.

I get consistent results along the lines of:
  • Level 1: Takes 10-25 generations
  • Level 2: Takes 15-40 generations
  • Level 3: Takes 40-400 generations (as it has to learn to jump blocks and gaps).

Congratulations!

I hope this tutorial was useful for you to learn how to use TensorFlowJS to build a NeuroEvolution implementation. Any questions leave them in the comments below, or tweet me on twitter at @dionbeetson

Source code

All source code for this tutorial can be found here https://github.com/dionbeetson/neuroevolution-experiment.

Sunday, 26 May 2019

NeuroEvolution using TensorFlow JS - Part 2

Introduction


This tutorial is part 2, if you have not completed NeuroEvolution using TensorFlowJS - Part 1, I highly recommend you do that first. As it will:
  • Explain how to setup the codebase
  • How to run the local dev environment
  • How to setup the basic NeruoEvolution implementation

In this tutorial we will be:
  • Adding visual debugging information
  • Adding more inputs for TensorFlow to use to predict jumping
  • Implement crossover within TensorFlowJS
  • Use the best progressing NeuralNetwork to ensure faster NeuroEvolution
  • Add saving and loading of NeuralNetwork models

This tutorial is also based on the source code found on my GitHub account here https://github.com/dionbeetson/neuroevolution-experiment.

Let's get started!

Add in visual/debugging

We will be adding in useful debugging information to the right hand column and to the game itself.

Chart the progress of each evolution

We are going to use ChartJS to track the progress (as a percentage) and the score for the best game of each evolution. Create a file called js/ai/NeuroEvolutionChart.js and copy the below logic into it. It is a basic ChartJS implementation that I won't go into detail in this tutorial.

js/ai/NeuroEvolutionChart.js

class NeuroEvolutionChart {
  constructor() {
    this.chart = null;
    this.config = {
    type: 'line',
    data: {
     labels: [],
     datasets: [{
      label: '',
      backgroundColor: '#999999',
      borderColor: '#EEEEEE',
          borderWidth: 3,
      data: [],
      fill: false,
     },{
      label: '',
      backgroundColor: '#91C7B1',
      borderColor: '#A1CFBC',
          borderWidth: 2,
      data: [],
      fill: false,
     }]
    },
    options: {
     responsive: true,
     title: {
      display: false
     },
     tooltips: {
      mode: 'index',
      intersect: false,
     },
        legend: {
          display: false
        },
     hover: {
      mode: 'nearest',
      intersect: true
     },
     scales: {
      xAxes: [{
       display: false,
       scaleLabel: {
        display: true,
        labelString: 'Round'
       }
      }],
      yAxes: [{
       display: true,
            ticks: {
              beginAtZero: true,
              min: 0,
              max: 100
            },
       scaleLabel: {
        display: false,
        labelString: 'Progress'
       }
      },{
       display: true,
            position: 'right',
            ticks: {
              beginAtZero: true,
              min: 0,
              max: 200
            },
       scaleLabel: {
        display: false,
        labelString: 'Score'
       }
      }]
     }
    }
   };

    this.setup();
  }

  setup(){
    var ctx = document.getElementById('trend').getContext('2d');
    this.chart = new Chart(ctx, this.config);
  }
}
Now, add an update() method that will be responsible for pushing the data points onto the chart. It will also only keep 12 data points (the very first evolution, and the latest 11 evolutions). This is to avoid clutter on the page.

js/ai/NeuroEvolutionChart.js

update(progress, score) {
  // Purge middle data (to avoid clutter)
  if( this.config.data.labels.length > 12 ) {
    this.config.data.labels.splice(1, 1);
    this.config.data.datasets[0].data.splice(1, 1);
    this.config.data.datasets[1].data.splice(1, 1);
  }

  this.config.data.labels.push((this.config.data.labels.length+1))
  this.config.data.datasets[0].data.push(progress);
  this.config.data.datasets[1].data.push(score);

  this.chart.update();
}
Back in the NeuroEvolution class add the following variable declaration to the top

js/ai/NeuroEvolution.js

#neuroEvolutionChart = new NeuroEvolutionChart();
Then in the same file in the finishGeneration(games, timeTaken) method, right after the line this.#bestGames.sort(this.sortByFitness); add in.

js/ai/NeuroEvolution.js

// Update UI - Chart
this.#neuroEvolutionChart.update(bestPlayerByFitness.progress, bestPlayerByFitness.score);
Reload your browser, and click the 'start evolution' button. After each evolution you will start to see the chart in the top right update.

Additional debugging visuals

Let's quickly add in some more useful debug information which includes:
  • The best game progress to date
  • Track the best score from each evolution
  • A progress bar in the header to track round and generation progress

In the NeuroEvolution class add the below methods

js/ai/NeuroEvolution.js

updateUIaddBestGenerationToBestScore( pickBestPlayerByFitness, timeTaken ) {
  let bestScore = document.createElement("li");
  bestScore.innerHTML = pickBestPlayerByFitness.score + ' (' + pickBestPlayerByFitness.progress.toFixed(1) + '%) (' + pickBestPlayerByFitness.fitness.toFixed(3) + ') (' + timeTaken + 's)';
  this.#bestScores.insertBefore(bestScore, document.querySelector("li:first-child"));
}

updateUIRoundInformation() {
  document.querySelector("#round-current").innerHTML = this.#generation;
  document.querySelector("#round-total").innerHTML = this.#maxGenerations;
  document.querySelector("#round-progress").style.width = '0%';
  document.querySelector("#generation-progress").style.width = (this.#generation/this.#maxGenerations)*100 + '%';
}

updateUIBestPlayerScore( bestGame ) {
  document.querySelector("#best-player-score").innerHTML = bestGame.score + " points (" + bestGame.progress.toFixed(1) + "%)";
}
In the first line of the start() method add:

js/ai/NeuroEvolution.js

processGeneration(games, bestPlayerBrainsByFitness) {
  this.updateUIRoundInformation();
  ...
Then right after where you added in this.#neuroEvolutionChart.update... add in:

js/ai/NeuroEvolution.js

// Update UI
this.updateUIaddBestGenerationToBestScore(bestPlayerByFitness, timeTaken);
this.updateUIBestPlayerScore(this.#bestGames[0]);
this.updateUIRoundInformation();
Lastly, add the following variable declaration to the top

js/ai/NeuroEvolution.js

#bestScores = null;
and the following constructor

js/ai/NeuroEvolution.js

constructor() {
  this.#bestScores = document.querySelector("#best-scores");
}
Reload your browser, and click the 'start evolution' button. You should start seeing debug information in your right hand column.

Another useful debug is to visualise the inputs that are being used to predict the jump() action.

Back in the Ai class within the think() method, just before the game.brain.predict() line, add in this code block to push debug points into the game canvas.

js/ai/Ai.js

game.gameApi.setDebugPoints([
  {
    x: 0,
    y: inputs[0]
  },
  {
    x: inputs[2],
    y: 0
  },
  {
    x: 0,
    y: inputs[3]
  },
  {
   x: 0,
   y: inputs[4]
  }
]);
Reload your browser, and click the 'start evolution' button. You should start seeing crosshairs for the inputs being used by TensorFlow JS on every prediction call.

Sometimes it is useful to be able to 'pause the game before the next evolution begins. You will see a checkbox in the left column labelled 'Pause after generation'. Let's wire it up, as it currently is not.

In ui.js add in the below change handler to capture user interaction.

js/ai/ui.js

document.querySelector("#ml-pause-before-next-generation").addEventListener("change", function() {
  neuroEvolution.pauseBeforeNextGeneration = this.checked;

  if( false == neuroEvolution.pauseBeforeNextGeneration && neuroEvolution.pausedGames.length > 0 && neuroEvolution.pausedBestNeuralNetworksByFitness.length > 0 ) {
    neuroEvolution.start(neuroEvolution.pausedGames, neuroEvolution.pausedBestNeuralNetworksByFitness);
  }
});

neuroEvolution.pauseBeforeNextGeneration = document.querySelector("#ml-pause-before-next-generation").checked;
This isn't enough though, we need to build in the logic to actually pause the game. We are basically going to wrap the ai.start(bestPlayerBrainsByFitness); call within the start() method in NeuroEvolution.js in an IF statement based on if the pause checkbox is checked. If it is checked, we will then store the current games within a local class variable so we can retrieve it once the checkbox is unchecked.

The completed method looks like this now.

js/ai/NeuroEvolution.js

start(games, bestPlayerBrainsByFitness) {
  this.updateUIRoundInformation();

  if ( this.#generation < this.#maxGenerations ) {

    if( false == this.#pauseBeforeNextGeneration ){
      for ( let i = 0; i < games.length; i++ ) {
        games[i].gameApi.remove();
      }

      games = undefined;

      this.#pausedGames = [];
      this.#pausedBestNeuralNetworksByFitness = [];

      this.#generation++;

      const ai = new Ai(this.finishGeneration.bind(this));
      ai.start(this.#useImageRecognition, bestPlayerBrainsByFitness);

    } else {
      this.#pausedGames = games;
      this.#pausedBestNeuralNetworksByFitness = bestPlayerBrainsByFitness;

      for ( let i = 0; i < games.length; i++ ) {
        games[i].gameApi.show();
      }
    }
  } else {
    this.enableSpeedInput();
  }
}
Then add in the following variable declarations in the NeuroEvolution class.

js/ai/NeuroEvolution.js

#pausedGames = [];
#pausedBestNeuralNetworksByFitness = [];
#pauseBeforeNextGeneration = false;
And then add in the required getters/setters in the NeuroEvolution class.

js/ai/NeuroEvolution.js

get pauseBeforeNextGeneration() {
  return this.#pauseBeforeNextGeneration;
}

set pauseBeforeNextGeneration( pauseBeforeNextGeneration ) {
  this.#pauseBeforeNextGeneration = pauseBeforeNextGeneration;
}

get pausedGames() {
  return this.#pausedGames;
}

get pausedBestNeuralNetworksByFitness() {
  return this.#pausedBestNeuralNetworksByFitness;
}

get bestGames() {
  return this.#bestGames;
}

set pauseBeforeNextGeneration( pauseBeforeNextGeneration ) {
  this.#pauseBeforeNextGeneration = pauseBeforeNextGeneration;
}

Speeding up NeuroEvolution

Ok that is debugging done for now. Let's move onto improving our NeuroEvolution to solve this game a little faster. This involves 3 things:
  1. Adding more inputs for TensorFlow to use to predict jumping
  2. After each evolution randomly choosing to use the 'best game to date', as this can keep things on track if we have a single bad evolution randomly (trust me it happens)
  3. Implementing a crossover method so instead of mutating only 1 of the best games, we take 2 of the best games and breed a child NeuralNetwork from their 2 results (which is called a crossover)
  4. If a game passes the level, don't mutate or crossover, as we already have a successful NeuralNetwork

Adding more inputs for TensorFlow JS

In the Ai class we are going to add in 3 more inputs for (isPlayerJumping, playerVelocity & canPlayerJump). Within the think() method after the existing 5 inputs, add in these additional inputs.

js/ai/Ai.js

// Is player jumping
inputs[5] = (game.gameApi.isPlayerJumping() ? 1 : 0);
inputsNormalised[5] = map(inputs[5], 0, 1, 0, 1);

// Player velocity
inputs[6] = (game.gameApi.getPlayerVelocity() ? 1 : 0);
inputsNormalised[6] = map(inputs[6], -1.1, 1.1, 0, 1);

// Can play jump?
inputs[7] = (game.gameApi.canPlayerJump() ? 1 : 0);
inputsNormalised[7] = map(inputs[7], 0, 1, 0, 1);
Then change the variable declaration for inputs in Ai class to 8

js/ai/Ai.js

#inputs = 8; 

Implement crossover within TensorFlowJS

In the NeuroEvolution class within the completeGeneration() method, we are going to modify the breeding section to make it a little smarter. Make the for loop look like this.

js/ai/NeuroEvolution.js

// Breeding
for (let i = 0; i < games.length; i++) {
  let bestPlayerA = this.pickBestGameFromFitnessPool(games);
  let bestPlayerB = this.pickBestGameFromFitnessPool(games);
  let child;

  child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerA.neuralNetwork.clone(), bestPlayerB.neuralNetwork.clone()));
 
  bestPlayerBrainsByFitness.push(child);
}
Now we need to add in the crossover method to the same file.

js/ai/NeuroEvolution.js

crossoverNeuralNetwork(neuralNetworkOne, neuralNetworkTwo) {
  let parentA_in_dna = neuralNetworkOne.input_weights.dataSync();
  let parentA_out_dna = neuralNetworkOne.output_weights.dataSync();
  let parentB_in_dna = neuralNetworkTwo.input_weights.dataSync();
  let parentB_out_dna = neuralNetworkTwo.output_weights.dataSync();

  let mid = Math.floor(Math.random() * parentA_in_dna.length);
  let child_in_dna = [...parentA_in_dna.slice(0, mid), ...parentB_in_dna.slice(mid, parentB_in_dna.length)];
  let child_out_dna = [...parentA_out_dna.slice(0, mid), ...parentB_out_dna.slice(mid, parentB_out_dna.length)];

  let child = neuralNetworkOne.clone();
  let input_shape = neuralNetworkOne.input_weights.shape;
  let output_shape = neuralNetworkOne.output_weights.shape;

  child.dispose();

  child.input_weights = tf.tensor(child_in_dna, input_shape);
  child.output_weights = tf.tensor(child_out_dna, output_shape);

  return child;
}
Reload your browser, and click the 'start evolution' button. You should start seeing games solve themselves a bit faster in fewer generations (normally around 20).

10% chance to crossover best game

Back in the NeuroEvolution class, within breeding section, let's add one final update so that on random occasions (10% chance), we do a crossover with the best game to date. Make the breeding section look like this

js/ai/NeuroEvolution.js

// Breeding
for (let i = 0; i < games.length; i++) {
  let bestPlayerA = this.pickBestGameFromFitnessPool(games);
  let bestPlayerB = this.pickBestGameFromFitnessPool(games);
  let bestPlayerC = this.#bestGames[0];
  let child;

  if ( random(1) < 0.1) {
    const ai = new Ai();
    let bestPlayerD = new NeuralNetwork(ai.inputs, ai.neurons, ai.outputs);
    child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerC.neuralNetwork.clone(), bestPlayerD));
  } else {
    child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerA.neuralNetwork.clone(), bestPlayerB.neuralNetwork.clone()));
  }

  bestPlayerBrainsByFitness.push(child);
}
We also need to expose getters in the Ai class for the input, neuron & output variables. Add the following methods:

js/ai/Ai.js

get inputs(){
  return this.#inputs;
}

get neurons(){
  return this.#neurons;
}

get outputs(){
  return this.#outputs;
}
Reload your browser, and click the 'start evolution' button. You should start seeing games solve themselves a bit faster in fewer generations (normally around 10-15).

Don't mutate on success

Now wrap the Breed functionality in an IF statement to ensure that if a game passes the level, we don't mutate or crossover, we just continue using the successful NeuralNetwork.

js/ai/NeuroEvolution.js

if ( false != gamePassedLevel ) {
  for ( let i = 0; i < games.length; i++ ) {
    if (games[i].gameApi.isLevelPassed() ) {
      games[i].neuralNetwork.save('neuralNetwork');
      for (let ii = 0; ii < games.length; ii++) {
          bestPlayerBrainsByFitness.push(games[i].neuralNetwork.clone());
        }
      }
    }

    console.log('Level Passed:', this.#bestGames[0], this.#bestGames.length, this.#bestGames);
    this.start(games, bestPlayerBrainsByFitness);
  } else {
    // Breeding
    for (let i = 0; i < games.length; i++) {
      let bestPlayerA = this.pickBestGameFromFitnessPool(games);
      let bestPlayerB = this.pickBestGameFromFitnessPool(games);
      let bestPlayerC = this.#bestGames[0];
      let child;

      if ( random(1) < 0.1) {
        const ai = new Ai();
        let bestPlayerD = new NeuralNetwork(ai.inputs, ai.neurons, ai.outputs);
        child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerC.neuralNetwork.clone(), bestPlayerD));
      } else {
        child = this.mutateNeuralNetwork(this.crossoverNeuralNetwork(bestPlayerA.neuralNetwork.clone(), bestPlayerB.neuralNetwork.clone()));
      }

      bestPlayerBrainsByFitness.push(child);
    }
 
   this.start(games, bestPlayerBrainsByFitness);
}
Reload your browser, and click the 'start evolution' button. Once enough evolutions process to pass the level, you will notice that all future games in evolutions will start passing consistently.

This is a far as we will take this tutorial in regards to evolving and speeding up our NeuroEvolution logic. Next we will move onto saving/loading our NeuralNetwork models.

Saving & Loading our NeuralNetwork models

The last piece to implement is the saving and loading functionality of our NeuralNetwork. This is so once you have a NeuralNetwork that works you can save it and load it back when needed. We will be implementing the:
  1. Ability to automatically save a NeuralNetwork that passes to localStorage
  2. Ability to manually save best NeuralNetwork to localStorage
  3. Ability to manually save best NeuralNetwork to disk
  4. Ability to load from local storage
  5. Ability to load from disk

First we need to add the ability to save within the NeuralNetwork.js file. Add these 2 methods

js/ai/NeuralNetwork.js

stringify() {
  let neuralNetworkToSave = {
    input_weights: this.input_weights.arraySync(),
    output_weights: this.output_weights.arraySync()
  };

  return JSON.stringify(neuralNetworkToSave);
}

save( key ) {
  localStorage.setItem(key, this.stringify());
}

Automatically save a NeuralNetwork that passes to localStorage

In the NeuroEvolution. class within the method finishGeneration(). Add in the below to the IF statement when a game level is passed.

js/ai/NeuroEvolution.js

games[i].neuralNetwork.save('neuralNetwork');
So it should look like this:

js/ai/NeuroEvolution.js

for ( let i = 0; i < games.length; i++ ) {
  if (games[i].gameApi.isLevelPassed() ) {
    games[i].neuralNetwork.save('neuralNetwork');
    for (let ii = 0; ii < games.length; ii++) {
      bestPlayerBrainsByFitness.push(games[i].neuralNetwork.clone());
    }
  }
}

console.log('Level Passed:', this.#bestGames[0], this.#bestGames.length, this.#bestGames);
this.start(games, bestPlayerBrainsByFitness);
Your game will now automatically save the NeuralNetwork model to localStorage key neuralNetwork if it passes the level.

Manually save best NeuralNetwork to localStorage

To manually save to local storage add the below code to ui.js

js/ai/ui.js

document.querySelector("#btn-ml-save-neuralnetwork-localstorage").addEventListener('click', function (event) {
  if( neuroEvolution.bestGames.length > 0 ) {
    neuroEvolution.bestGames[0].neuralNetwork.save('neuralNetwork')
  }
});

Manually save best NeuralNetwork to disk

To manually save to disk you can add the below code to ui.js

js/ai/ui.js

document.querySelector("#btn-ml-save-neuralnetwork-disk").addEventListener('click', function (event) {
  if( neuroEvolution.bestGames.length > 0 ) {
    let neuralNetworkJSON = neuroEvolution.bestGames[0].neuralNetwork.stringify();
    let a = document.createElement("a");
    let file = new Blob([neuralNetworkJSON], {type: 'application/json'});
    a.href = URL.createObjectURL(file);
    a.download = 'neuralNetwork.json';
    a.click();
  }
});

Loading NeuralNetwork Models

To load from local storage or disk we need to create a method to handle loading a NeuralNetwork into memory. Create the below method in ui.js (there is probably a better file location for this method now that I think about it).

js/ai/ui.js

const loadNeuralNetwork = (neuralNetworkData) => {
  const ai = new Ai();
  let neuralNetwork = new NeuralNetwork(ai.inputs, ai.neurons, ai.outputs);
  neuralNetwork.dispose();

  neuralNetwork.input_weights = tf.tensor(neuralNetworkData.input_weights);
  neuralNetwork.output_weights = tf.tensor(neuralNetworkData.output_weights);

  let neuralNetworks = [];
  for ( let i = 0; i < ai.totalGames; i++ ) {
    neuralNetworks.push(neuralNetwork);
  }

  let games = neuroEvolution.pausedGames;
  neuroEvolution.pausedGames;
  neuroEvolution.reset();

  neuroEvolution.start(games, neuralNetworks);
};

We also need to add the below method into the Ai class.

js/ai/Ai.js

get totalGames(){
  return this.#totalGames;
}

Load from local storage

Now to load from localStorage into memory, add the below into ui.js

js/ai/ui.js

document.querySelector("#btn-ml-load-neuralnetwork-localstorage").addEventListener('click', function (event) {
  cachedLevelSections = [];
  let games = neuroEvolution.pausedGames;
  neuroEvolution.pausedGames;
  neuroEvolution.reset();

  let neuralNetworkData = localStorage.getItem('neuralNetwork');

  loadNeuralNetwork(JSON.parse(neuralNetworkData));
});
We also need to add the reset method into the NeuroEvolution class.

js/ai/NeuroEvolution.js

reset() {
  this.#bestGames = [];
  this.#generation = 1;
  this.#pausedGames = [];
  this.#pausedBestNeuralNetworksByFitness = [];
  this.#pauseBeforeNextGeneration = false;
}

Load from disk

Now to load from disk into memory, add the below into ui.js

js/ai/ui.js

document.querySelector("#btn-ml-load-neuralnetwork-disk").addEventListener('change', function (event) {
  let file = this.files[0];
  let reader = new FileReader()
  let textFile = /application\/json/;
  let fileText = '';

  if (file.type.match(textFile)) {
    reader.onload = function (event) {
       let importedNeuralNetwork = JSON.parse(event.target.result);

       loadNeuralNetwork(importedNeuralNetwork);
    }
  }

  reader.readAsText(file);
});
Reload your browser, and click the 'start evolution' button. You will notice if you inspect Chrome DevTools you will see a localStorage key called 'brain' once a level is passed.


You can also now also use the buttons in the left hand menu to save and load the best NeuralNetwork to disk.

Within the GitHub codebase within the models/ directory you will see 3 existing models that can be loaded up to pass levels 1, 2 & 3.

Try it yourself and get your NeuroEvolution implementation to pass Level 1, then Level 2, then finally Level 3.

I get consistent results along the lines of:

  • Level 1: Takes 5-20 generations
  • Level 2: Takes 5-20 generations
  • Level 3: Takes 40-700 generations (as it has to learn to jump blocks and gaps).

Congratulations!

I hope this tutorial was useful for you to learn how to use TensorFlowJS to build a NeuroEvolution implementation. Any questions leave them in the comments below, or tweet me on twitter at @dionbeetson

Source code

All source code for this tutorial can be found here https://github.com/dionbeetson/neuroevolution-experiment.

Part 3 - coming soon...

Coming soon and will be using image recognition to solve the same browser based game.

NeuroEvolution using TensorFlowJS - Part 1

Introduction


This tutorial will walk you through how to implement NeuroEvolution using TensorFlow JS. This NeuralNetwork will learn how to play a simple browser based game that requires a player to jump over blocks and gaps. It is based on the source code found on my GitHub account here https://github.com/dionbeetson/neuroevolution-experiment.

The difference in this solution compared to other solutions out there is that instead of building ML directly into the core game source code (like I saw in a lot of examples); the ML and Game source code are completely decoupled. This simulates a much more realistic real world example, as you would rarely have direct access to the source code when applying ML (you would only have access to specific inputs). I created an an API/SDK for the browser based game to expose some key functionality (the inputs the NeuralNetwork needs), but end state is to use image analysis so this solution is more adaptable to other applications.

References

Although I wrote this codebase myself I took a lot of input/influence from a huge range of great tutorials that already exist. You can see a list of the key tutorials/repos I learned from on the GitHub Readme for this project here.

Let's get started!

Setup

Clone this repo from GitHub:
git clone git@github.com:dionbeetson/neuroevolution-experiment.git
Then run in terminal the below to setup the repository for this tutorial:
npm install

npm run setup-tutorial
This basically moves the js/ai directory to js/ai-source, and leaves everything else in place. If you ever need to refer back to the original source code use js/ai-source as reference.

Now run the below to startup the app:
npm run dev
The browser will load up the application, but you will see 404 errors within the DevTools console. You will though however, have a working browser game. Click 'Play game', and use the spacebar to jump to test things out. Throughout this tutorial you are going to be building a NeuroEvolution implementation to learn how to automatically solve this game.

Quick overview of the UI

  • Left section: Includes base controls for Manual and AI interactions. In order from top to bottom
    • Level: You can select the level (there are currently 3 levels available in the game in order of complexity)
    • Play game: Play an user interacted game
    • Enable drawing: Whether you want to render the drawing on canvas
    • Speed: How fast the game will run
    • Start Evolution: Start the NeuroEvolution
    • Save to localStorage: Save best current NeuralNetwork into localStorage
    • Save to disk: Save best current NeuralNetwork to disk
    • Load from localStorage: Load current NeuralNetwork in local storage into memory and start NeuroEvolution
    • Load from disk: Load a NeuralNetwork from disk into memory and start NeuroEvolution
    • Pause after generation: For debugging, pause after each evolution so you can see / debug it
  • Middle section: The game(s) render within the large middle column
  • Right section: Is used to display debugging information for the NeuroEvolution implementation

This tutorial has 4 key files

For the entire tutorial we will be working within the js/ai/ directory.
  1. ui.js: Controls the UI interactions
  2. NeuralNetwork.js: Is the base neural network
  3. Ai.js: This class instantiates (by default 9) games & corresponding NeuralNetwork instances
  4. Neuroevolution.js: This class will run up to 1500 generations of Ai.js until it successfully passes the selected level

Setup base structure

Let's start to build out enough base logic to be able to predict if we should jump or not using TensorFlowJS.

Create a directory js/ai, and create a file called js/ai/ui.js which will handle basic UI controls. Within this file we want to instantiate the NeuroEvolution class (that we are about to create, and bind a UI button to start the evolution process).

js/ai/ui.js

let neuroEvolution = new NeuroEvolution();

document.querySelector("#btn-ml-start").addEventListener('click', function (event) {
  neuroEvolution.start([]);
}, false);
Now we need to create the skeleton of NeuralNetwork.js, Ai.js & Neuroevolution.js.

For the NeuralNetwork let's just start with a constructor that allows us to send input_node/hidden_node & output_node count arguments.

js/ai/NeuralNetwork.js

class NeuralNetwork {
  constructor(input_nodes, hidden_nodes, output_nodes) {
    // The amount of inputs (eg: player y position, height of next block etc..)
    this.input_nodes = input_nodes;
    // Amount of hidden nodes within the Neural Network)
    this.hidden_nodes = hidden_nodes;
    // The amount of outputs, we will use 2 (will be needed for level 3)
    this.output_nodes = output_nodes;

    // Initialize random weights
    this.input_weights = tf.randomNormal([this.input_nodes, this.hidden_nodes]);
    this.output_weights = tf.randomNormal([this.hidden_nodes, this.output_nodes]);
  }
}
Now we need to create the Ai class. This will include a method that will create 1 game for now and link it with a NeuralNetwork instance. We will start with a start() method to create instances of a NeuralNetwork, a checkGame() method that will be called every 50ms which will call the think() method that we will expand to make the actual prediction to jump or not jump.

js/ai/Ai.js

class Ai {
  #totalGames = 1; // Will increase to 9 games later
  #inputs = 5;
  #neurons = 40;
  #outputs = 2;
  #games = [];
  #gamesRunning = 0;
  #sectionsToSeeAhead = 1;
  #timeTakenDateStart = null;

  start(useImageRecognition, neuralNetworks, completeCallback) {
    this.#timeTakenDateStart = new Date();

    for ( let i = 0; i < this.#totalGames; i++ ) {
      let neuralNetwork;

      if ( undefined !== neuralNetworks && neuralNetworks[i] instanceof NeuralNetwork ) {
        neuralNetwork = neuralNetworks[i];
      } else {
        neuralNetwork = new NeuralNetwork(this.#inputs, this.#neurons, this.#outputs);
      }

      let gameApi;

      if ( useImageRecognition ) {
        gameApi = new GameImageRecognition();
      } else {
        gameApi = new GameApi();
      }

      this.#games[i] = {
        gameApi: gameApi,
        neuralNetwork: neuralNetwork,
        interval: null
      }

      // Debug look ahead
      this.#games[i].gameApi.setHighlightSectionAhead(this.#sectionsToSeeAhead)

      // Start game
      this.#gamesRunning++;
      this.#games[i].gameApi.start();

      this.#games[i].interval = setInterval(this.checkGame.bind(null, this, this.#games, this.#games[i]), 50);
    }
  }

  checkGame(ai, games, game) {
    if( game.gameApi.isSetup() ) {
      ai.think(game);
    }
  }

  think(game) {
  }
}
Now create the NeuroEvolution class that will be responsible for running multiple evolutions of Ai.js until we get an evolution that passes the level.

js/ai/NeuroEvolution.js

class NeuroEvolution {
  #generation = 1;
  #maxGenerations = 1500;
  #useImageRecognition = false;

  start(games, bestPlayerBrainsByFitness) {

    if ( this.#generation < this.#maxGenerations ) {

      for ( let i = 0; i < games.length; i++ ) {
        games[i].gameApi.remove();
      }

      games = undefined;

      this.#generation++;

      const ai = new Ai(this.finishGeneration.bind(this));
      ai.start(this.#useImageRecognition, bestPlayerBrainsByFitness);
    } else {
      this.enableSpeedInput();
    }
  }

  finishGeneration(games, timeTaken) {
   // TODO
  }

  updateUIRoundInformation() {
    document.querySelector("#round-current").innerHTML = this.#generation;
    document.querySelector("#round-total").innerHTML = this.#maxGenerations;
    document.querySelector("#round-progress").style.width = '0%';
    document.querySelector("#generation-progress").style.width = (this.#generation/this.#maxGenerations)*100 + '%';
  }
}
Now you have your base structure in place.

Reload your browser (http://127.0.0.1:8080/), and click the 'Start evolution' button. You should see 1 game playing, and failing (no jumping), no matter how many times you reload the page. That is because we haven't implemented the prediction logic. Let's implement that using TensorFlowJS in a moment.

Quickly, before that, in the Ai class, let's create 9 games at once instead of 1, as NeuroEvolution will be incredibly slow with only 1 NeuralNetwork at a time. Depending on your computer specs you can increase this to a higher number. I did find that 9 worked quite well though.

js/ai/Ai.js

#totalGames = 9
Reload your browser, and click 'Start evolution' button again. You should see 9 games playing.

Predicting whether to jump or not

To use TensorflowJS to predict to jump, we need to modify a few files. First in Ai.js in the think() method add the below logic in. Essentially we are accessing public information that the JS game exposes in js/game/GameAPI.js (like player position, next block height etc..) and then normalising all inputs to be between 0-1 as TensorFlow JS requires this.

js/ai/Ai.js

think(game) {
  let inputs = [];
  let inputsNormalised = [];

  // Player y
  inputs[0] = (game.gameApi.getPlayerY());
  inputsNormalised[0] = map(inputs[0], 0, game.gameApi.getHeight(), 0, 1);

  // Player x
  inputs[1] = game.gameApi.getPlayerX();
  inputsNormalised[1] = map(inputs[1], inputs[1], game.gameApi.getWidth(), 0, 1);

  let section = game.gameApi.getSectionFromPlayer(this.#sectionsToSeeAhead);

  // 2nd closest section x
  inputs[2] = section.x + section.width;
  inputsNormalised[2] = map(inputs[2], inputs[1], game.gameApi.getWidth(), 0, 1);

  // 2nd closest section y
  inputs[3] = section.y;
  inputsNormalised[3] = map(inputs[3], 0, game.gameApi.getHeight(), 0, 1);

  // 2nd closest section y base
  inputs[4] = section.y + section.height;
  inputsNormalised[4] = map(inputs[4], 0, game.gameApi.getHeight(), 0, 1);

  // Call the predict function in the NeuralNetwork
  let outputs = game.neuralNetwork.predict(inputsNormalised);

  // If input is about 0.5 then jump, if not, stay still
  if ( outputs[0] > 0.5 || outputs[1] > 0.5 ) {
    game.gameApi.jump();
  }
}
We also will need to create the predict() method in the NeuralNetwork class. This method creates an input_layer, hidden_layer and output_layer and returns 2 predictions (which are both numbers between 0-1).

js/ai/NeuralNetwork.js

predict(user_input) {
  let output;
  tf.tidy(() => {
    let input_layer = tf.tensor(user_input, [1, this.input_nodes]);
    let hidden_layer = input_layer.matMul(this.input_weights).sigmoid();
    let output_layer = hidden_layer.matMul(this.output_weights).sigmoid();
    output = output_layer.dataSync();
  });
  return output;
}
Reload your browser, and click the 'start evolution' button.

You will now see 9 games playing, and some should be jumping, and some not. This is completely random. Reload a few times if you need to to ensure this is the behaviour you are seeing.

Once all of your players die you will notice the game stops. As of now, we have used TensorFlow JS to make a prediction about whether to jump or not. This is based on a set of inputs (player X, player Y & section ahead height/Y).

Now we need to add in the NeuroEvolution aspect so that we pick the best progressed games and start a new evolution with those NeuralNetworks (but we will evolve/mutate them slightly before hand).

In NeuroEvolution add a method called calculateFitness(). This method iterates through all games once finished, creates a fitness rating which is just the % progress of the game. It then has logic to increase the fitness of better performing games, so that later on in our logic, there is a higher chance the better performing NeuralNetworks are chosen for the next evolution. Hope that all makes sense.

js/ai/NeuroEvolution.js

calculateFitness(games) {
  for ( let i = 0; i < games.length; i++ ) {
    let game = games[i];
    games[i].fitness = game.gameApi.getProgress() / 100;
    games[i].score = game.gameApi.getScore();
    games[i].progress = game.gameApi.getProgress();
  }

  // The below code makes the better progressed games have a higher fitness so they have a higher chance of being selected for next generation
  games.sort(this.sortByFitness);
  games.reverse();

  let prev = 0;
  for ( let i = 0; i < games.length; i++ ) {
    games[i].fitness = this.#discountRate * prev + games[i].fitness;
    prev = games[i].fitness;
  }

  games.sort(this.sortByFitness);

  return games;
}
In NeuroEvolution.js add a method that will check if at least 1 game has passed the level in the current evolution.

js/ai/NeuroEvolution.js

didAtLeastOneGameCompleteLevel(games) {
  for ( let i = 0; i < games.length; i++ ) {
    if (games[i].gameApi.isLevelPassed() ) {
      return games[i];
    }
  }

  return false;
}
In NeuroEvolution add a method that will pick the exact best player with the highest fitness. We use this to display and keep a track of the best performing NeuralNetwork.

js/ai/NeuroEvolution.js

pickBestGameByActualFitness(games){
  let game;
  let prevFitness = 0;
  for ( let i = 0; i < games.length; i++ ) {
    if (games[i].fitness > prevFitness) {
      game = games[i];
      prevFitness = game.fitness;
    }
  }

  return game;
}
In NeuroEvolution add a method that will pick one (not always the best like the above method) of the best players with the highest fitness

js/ai/NeuroEvolution.js

pickBestGameFromFitnessPool(games) {
  let index = 0;
  let r = random(1);

  while (r > 0 ) {
    if( undefined !== games[index] ) {
      r = r - games[index].fitness;
      index++;
    } else {
      r = 0;
    }
  }
  index--;

  let game = games[index];

  return game;
}
In NeuroEvolution we can now improve the finishGeneration() method with the below logic. This code will:
  1. Calculate fitness for all 9 finished games
  2. Store the best player in a local variable
  3. Add the best player to the bestGames[] array
  4. Ensure we only keep the best 5 games (for memory/performance reasons)
  5. Iterate over all games and mutate the best performing NeuralNetworks into new NeuralNetworks for the next evolution
  6. Start the next NeuroEvolution

js/ai/NeuroEvolution.js

finishGeneration(games, timeTaken) {
  games = this.calculateFitness(games);

  // Did one of the games finish?
  let gamePassedLevel = this.didAtLeastOneGameCompleteLevel(games);

  let bestPlayerByFitness = gamePassedLevel;
  let bestPlayerBrainsByFitness = [];

  if( false === bestPlayerByFitness ){
    bestPlayerByFitness = this.pickBestGameByActualFitness(games);
  }

  this.#bestGames.push(bestPlayerByFitness);
  this.#bestGames.sort(this.sortByFitness);

  // Only keep top 5 best scores
  if( this.#bestGames.length > 5 ) {
    this.#bestGames = this.#bestGames.slice(0, 5);
  }

  // Breeding
  for (let i = 0; i < games.length; i++) {
    let bestPlayerA = this.pickBestGameFromFitnessPool(games);
    let child;

    child = this.mutateNeuralNetwork(bestPlayerA.neuralNetwork.clone());

    bestPlayerBrainsByFitness.push(child);
  }

  this.start(games, bestPlayerBrainsByFitness);
}
Lastly, in NeuroEvolution you will need to add the below variable declarations.

js/ai/NeuroEvolution.js

  #discountRate = 0.95;
  #bestGames = [];
Reload your browser, and click the 'start evolution' button. You should again see 9 games playing, some will also be jumping like last time. However, it still wont progress past the first evolution. This is because we need to wire up Ai.js to call the callback method in the checkGame method and add some logic to check if the game is over. Let's update the checkGame() method to look like the below.

js/ai/Ai.js

checkGame(ai, games, game) {
  if( game.gameApi.isOver() ) {
    clearInterval(game.interval);

    ai.#gamesRunning--;
    document.querySelector("#round-progress").style.width = ((games.length-ai.#gamesRunning)/games.length)*100 + '%';

    if( ai.areAllGamesOver(games) && 0 == ai.#gamesRunning ) {
      let timeTakenDateComplete = new Date();
      let timeTaken = (timeTakenDateComplete - ai.#timeTakenDateStart) / 1000;

      ai.#completeCallback(games, timeTaken);
    }
  } else {
    if( game.gameApi.isSetup() ) {
      ai.think(game);
    }
  }
}
We also need to add the following variable declarations to Ai class.

js/ai/Ai.js

#completeCallback;
Reload your browser, and click the 'start evolution' button.

You should see an error as we didn't declare the method areAllGamesOver(). Let's quickly add the below to Ai

js/ai/Ai.js

areAllGamesOver(games) {
  for ( let i = 0; i < this.#totalGames; i++ ) {
    if( false == games[i].gameApi.isOver() ) {
      return false;
    }
  }

  return true;
}
... Another error, we forgot to set the completeCallback. In Ai, create a constructor up the top after the variable declaration.

js/ai/Ai.js

constructor(completeCallback) {
  this.#completeCallback = completeCallback;
}
Reload your browser, and click the 'start evolution' button.

Ok, we are making progress, but we are now missing the clone() method. We need to be able to clone NeuralNetworks after each generation so we don't interfere with previous NeuralNetwork objects.

In NeuralNetwork class add the clone() method as well as the dispose() method, as that is called from within the clone() method.

js/ai/NeuralNetwork.js

clone() {
  return tf.tidy(() => {
    let clonie = new NeuralNetwork(this.input_nodes, this.hidden_nodes, this.output_nodes);
    clonie.dispose();
    clonie.input_weights = tf.clone(this.input_weights);
    clonie.output_weights = tf.clone(this.output_weights);
    return clonie;
  });
}

dispose() {
  this.input_weights.dispose();
  this.output_weights.dispose();
}
Reload your browser, and click the 'start evolution' button. You will see we are close now, we are just missing the mutateNeuralNetwork() method. This method is responsible for slightly tweaking the cloned NeuralNetwork so that you get a slightly different result in the next evolution. Let's go ahead and add the mutateNeuralNetwork() method into the NeuroEvolution class. I'm not going to go into more detail on this, but you can google it and find this method in a few other examples out there. I also wasn't the original author of this, I just adjusted it to work for my implementation. See GitHub for reference to original source code.

js/ai/NeuralEvolution.js

mutateNeuralNetwork(b) {
  function fn(x) {
    if (random(1) < 0.05) {
      let offset = randomGaussian() * 0.5;
      let newx = x + offset;
      return newx;
    }
    return x;
  }

  let neuralNetwork = b.clone();
  let ih = neuralNetwork.input_weights.dataSync().map(fn);
  let ih_shape = neuralNetwork.input_weights.shape;
  neuralNetwork.input_weights.dispose();
  neuralNetwork.input_weights = tf.tensor(ih, ih_shape);

  let ho = neuralNetwork.output_weights.dataSync().map(fn);
  let ho_shape = neuralNetwork.output_weights.shape;
  neuralNetwork.output_weights.dispose();
  neuralNetwork.output_weights = tf.tensor(ho, ho_shape);
  return neuralNetwork;
}
Reload your browser, and click the 'start evolution' button. Now after each of the 9 games fail the first time, the UI will start a new evolution. If you let this go for a few minutes you should see the game get solved - it normally takes around 30-50 generations with this current implementation.

Congratulations!

This is a very simple implementation of NeuroEvolution. In Part 2, we will go through making improvements to really speed things up including:
  • Implementing crossover within TensorFlowJS
  • Using the best progressing NeuralNetwork to ensure faster NeuroEvolution
  • Saving and loading models
  • Adding debugging information

Source code

All source code for this tutorial can be found here https://github.com/dionbeetson/neuroevolution-experiment.

Part 2

Continue on to NeuroEvolution using TensorFlowJS - Part 2