Forem: Gabe Romualdo

Random Seed in JavaScript and Node.js

Gabe Romualdo — Fri, 26 Mar 2021 05:13:43 +0000

Introduction

Random seed is a method of initializing random number generators using an initial seed value. Random generators with the same seed will output the same pseudo-random results.

I found this method to be particularly useful when developing a game I'm working on, which has a random 'Daily Challenge'. In this case, random seed can be useful to select a random game using the current date as a seed.

Code

So, here's how to create a random seed in Node.js, using the seedrandom NPM package:

// In Node.js
const seedrandom = require('seedrandom');
const generator = seedrandom('[your seed here]');
const randomNumber = generator();

And if you're on the client-side:

// On The Browser
const generator = new Math.seedrandom('[your seed here]');
const randomNumber = generator();

In both of these code snippets, the generator function will return a new random number each time, given the seed the generator was initialized with. In this case, it will be formatted as a numerical value, although

Dependencies

If you're running on Node.js, download the seedrandom package as follows:

npm install seedrandom

Or using Yarn:

yarn add seedrandom

If you're writing client-side code without webpack, you can either download the file from seedrandom's GitHub repository, or use a CDN by adding the following code snippet at the end of your <body> tag:

<script src="https://cdnjs.cloudflare.com/ajax/libs/seedrandom/3.0.5/seedrandom.min.js"></script>

Conclusion

Random seed is one of a few features that is present in most major programming languages but is not available out-of-the-box in JavaScript. It can be incredibly useful in a wide array of cases, both on the web and running on the server-side using Node.

I hope this helps, and thanks for scrolling.

— Gabriel Romualdo, March 26, 2021

An Algorithm to Swap Two Variables Synchronously, Without Creating a Temporary Variable

Gabe Romualdo — Wed, 24 Mar 2021 02:19:34 +0000

Introduction

Let's say you want to swap the values of two integer variables, a, and b. Simply setting a equal to b and then b equal to a does not work, since a and b would just end up both equaling the initial value of b.

# doesn't work (both a and b end up equaling b):
a = b
b = a

So, typically, you'd create another variable — let's call it c — and set that variable to the value of a, and then do something like this:

# the simplest solution, with a temporary variable:
c = a
a = b
b = c

This is very simple, but the extra variable is not actually necessary.

Note that some programming languages, for example Python, provide the ability to swap two variables in a single line, like a, b = b, a. I will explain how to swap two variables without a temporary variable without utilizing this feature.

The Algorithm

By summing the two variables and adding a few subtraction operations, this same swapping operation can be done without a temporary variable, like this:

a = a + b
b = a - b
a = a - b

To see that this works, let's test it out with a = 100 and b = 5.

a = a + b # a = 100 + 5 = 105
b = a - b # b = 105 - 5 = 100
a = a - b # a = 105 - 100 = 5

As we can see, after running these operations, a = 5 and b = 100, so the values were swapped, as expected.

This can also be similarly done with multiplication and division, like this:

a = a * b
b = a / b
a = a / b

This version is generally less efficient because most (if not all) programming languages take longer to calculate products and quotients in comparison to sums and differences.

Conclusion

Overall, this is an interesting algorithm that can be used in programs where you are swapping two integer values. Since it only saves a very small amount of space by not creating the temporary variable, it is not particularly useful in smaller projects and programs. However, on a larger scale when working with millions of variables and values at a time, and you'd like to save as much space and storage as possible, this can be useful.

I hope you enjoyed this article and found this to be an interesting algorithm.

Thanks for scrolling.

— Gabriel Romualdo, March 23, 2021

How to Set Up Rate Limiting and Rate Slowing Down in Express.js

Gabe Romualdo — Tue, 12 Jan 2021 01:27:17 +0000

Rate limiting is the process of preventing repeated requests to a server in effort to remove spam requests. Typically, a limit is set, such as 200 requests to the server per minute, and any IP address that exceeds that limit will be blocked from making requests for a set period of time.

Rate slowing down is the process of slowing down server responses to an IP that has been sending too many requests. For example, the slow down limit could be set to 200 requests per minute, and an extra 2.5 seconds more response time could be added for each request that exceeds the limit.

Both of these methods of preventing spam requests are common can be an essential feature to the server or API of many projects. In this article, I'll explain how rate limiting and rate slowing can be done with Express.js in Node, and I'll discuss some of the use cases and differences between both of these techniques.

Rate Limiting in Express

Install the express-rate-limit package

npm install express-rate-limit

Or:

yarn add express-rate-limit

Set a rate limit and use it in an Express app

const rateLimiter = require("express-rate-limit"); 

app.set("trust proxy", 1); // use this line if you’re using a proxy (Heroku, DigitalOcean, etc.); so req IPs are the client’s IP, not the IP of the proxy service

// set a rate limit of 200 reqs/min
const rateLimit = rateLimiter({
    max: 200 // the rate limit in reqs
    windowMs: 1 * 60 * 1000, // time where limit applies
});

// use the rate limit in your Express app
app.use(rateLimit);

Rate Slowing Down in Express

Install the express-slow-down package

npm install express-slow-down

Or:

yarn add express-slow-down

Configure rate slow down and use it in an Express app

const rateSpeedLimiter = require("express-slow-down"); 

app.set("trust proxy", 1); // use this line if you’re using a proxy (Heroku, DigitalOcean, etc.); so req IPs are the client’s IP, not the IP of the proxy service

// allow 200 reqs/min, reqs after that are delayed by 2500ms
const rateSpeedLimit = rateSpeedLimiter({
    delayAfter: 200 // slow down limit (in reqs)
    windowMs: 1 * 60 * 1000, // time where limit applies
    delayMs: 2500 // slow down time
});

// use the rate slow down in your Express app
app.use(rateSpeedLimit);

Rate Limiting vs Rate Slowing Down

The case for rate limiting: first, rate limiting is generally more common, especially in production. Once an effective rate limit has been chosen, rate limiting is a clear way to block malicious and unwanted requests. Rate limiting is also useful for public APIs. People that offer APIs often provide a rate limit for users without an API key, or users who haven’t paid a fee for a certain number of requests.

The case for rate slowing down: rate slowing down is a more lenient approach on preventing spam requests. It can be more effective in cases where it is not ideal to outright block particular users, or if there are very rare cases where the rate limit could be exceeded, by search engine scrapers and spiders, for example.

Overall, rate limiting is a stricter and more common way to prevent spam requests, whereas rate slowing down provides a more lenient approach.

Conclusion

I hope this article helps in understanding how to implement rate limiting and rate slowing down in Express.js, and what the use cases for both methods are.

Thanks for scrolling.

— Gabriel Romualdo, January 11, 2021

Programs to Compute Trig Functions in Python, JavaScript, & Perl (with Maclaurin Series)

Gabe Romualdo — Thu, 31 Dec 2020 21:23:17 +0000

Introduction

Have you ever wondered how your computer calculates certain mathematical functions, like division, or trigonometric functions like sine or cosine? Well, for some of these mathematical functions, there exist useful formulas to calculate very accurate results pretty easily. For sine and cosine, one commonly used formula looks like this:

And for cosine:

Note that the input of each function is in radians, not degrees.

The series used in both formulas is called a Maclaurin series (a type of Taylor series), and can be derived from the sine and cosine functions with a series expansion.

How the Programs Work

I've written programs to implement these two computations in three major scripting languages: Python, JavaScript, and Perl. These programs do not include any built-in trig functions or other utilities except the use of the in-built π constant in some cases. All code is CC0 licensed.

The approach I used creates a generalized function called computeSeries which takes in x as the number to calculate the sine or cosine of, a starting number in the series (x for sine and 1 for cosine), and the exponent and factorial base in the first term of the series (3 for sine and 2 for cosine).

In calculating each series, I found that only about 10 terms in the series were needed to get a decently accurate result.

The programs additionally include utility functions for sine and cosine functions in degrees. The end of each program also includes a few tests of each function, which work as expected.

In Python

Feel free to view the below code as a GitHub Gist.

from math import pi

# round a number (x) to nearest 10 digits
def rounded(x):
    return round(x, 10)

# get the factorial of a number (x)
# factorial(x) is the product of every number from 1 to N inclusive
def factorial(x):
    n = 1; # n is the result
    # multiply n by every number from 1 to x inclusive
    for i in range(2, x + 1):
        n *= i
    return n

""" get the result of the cos and sin formulas
    where the functions are sin(x radians) or cos(x radians),
    n is the start value (n = x for sin, n = 1 for cos), and
    i_start is the exponent and factorial base in the first term """
def computeSeries(x, n, i_start):
    iterations = 20 # iterations is twice the amount of terms to use
    multiplier = 1
    for i in range(i_start, i_start + iterations, 2): # i increases by 2 each term
        multiplier *= -1 # alternates between addition and subtraction each term
        next_term = (x**i) / factorial(i) # each term is (x^i) / i!
        n += multiplier * next_term # add or subtract from final result
    return n

# get sin of x radians
def sin(x):
    return rounded(computeSeries(x, x, 3))

# get cos of x radians
def cos(x):
    return rounded(computeSeries(x, 1, 2))

# get sin of x degrees
def sinDeg(x):
    return sin(x * pi / 180)

# get cos of x degrees
def cosDeg(x):
    return cos(x * pi / 180)

# test the functions
print(sin(pi / 6)); # 0.5
print(sinDeg(45)); # 0.7071
print(sinDeg(52)); # 0.78801

print(cos(pi / 3)); # 0.5
print(cosDeg(45)); # 0.7071
print(cosDeg(52)); # 0.615661

In JavaScript

Feel free to view the below code as a GitHub Gist.

// round a number (x) to nearest 10 digits
const rounded = (x) => {
    return parseFloat(x.toFixed(10));
}

// get the factorial of a number (x)
// factorial(x) is the product of every number from 1 to x inclusive
const factorial = (x) => {
    let n = 1; // n is the result
    // multiply n by every number from 1 to x inclusive
    for(let i = 2; i <= x; i++) {
        n *= i;
    }
    return n;
}

/* get the result of the cos and sin formulas
   where the functions are sin(x radians) or cos(x radians),
   n is the start value (x for sin, 1 for cos), and i_start
   is the exponent and factorial base in the first term */
const computeSeries = (x, n, i_start) => {
    const iterations = 20; // iterations is twice the amount of terms to use
    let multiplier = 1;
    let i = i_start;
    while(i < i_start + iterations) {
        multiplier *= -1; // alternates between addition and subtraction each iteration
        const next_term = (x**i) / factorial(i); // each term is (x^i) / i!
        n += multiplier * next_term // add or subtract from final result
        i += 2 // i increases by 2 each term
    }
    return n
}

// get sin of x radians
const sin = (x) => {
    return rounded(computeSeries(x, x, 3));
}
// get cos of x radians
const cos = (x) => {
    return rounded(computeSeries(x, 1, 2));
}
// get sin of x degrees
const sinDeg = (x) => {
    return sin(x * Math.PI / 180);
}
// get cos of x degrees
const cosDeg = (x) => {
    return cos(x * Math.PI / 180);
}

// test the functions
console.log(sin(Math.PI / 6)); // 0.5
console.log(sinDeg(45)); // 0.7071
console.log(sinDeg(52)); // 0.78801

console.log(cos(Math.PI / 3)); // 0.5
console.log(cosDeg(45)); // 0.7071
console.log(cosDeg(52)); // 0.615661

In Perl

Feel free to view the below code as a GitHub Gist.

#!/usr/bin/perl
use warnings;

$pi = 3.14159265358979323;

# get the factorial of a number (x)
# factorial(x) is the product of every number from 1 to N inclusive
sub factorial {
    my ($x) = @_;
    my $n = 1; # n is the result
    # multiply n by every number from 1 to x inclusive
    my @nums_to_multiply = (1..$x);
    for(@nums_to_multiply){
        $n *= $_;
    }
    return $n;
}

=begin
get the result of the cos and sin formulas
where the functions are sin(x radians) or cos(x radians),
n is the start value (n = x for sin, n = 1 for cos), and
i_start is the exponent and factorial base in the first term
=cut
sub computeSeries {
    $ITERATIONS = 20; # iterations is twice the amount of terms to use
    my ($x, $n, $i_start) = @_;
    my $multiplier = 1;
    $i = $i_start;
    while($i < $i_start + $ITERATIONS) {
        $multiplier *= -1; # alternates between addition and subtraction each term
        $n += $multiplier * (($x**$i) / factorial($i)); # add or subtract ((x^i) / i!) from final result
        $i += 2; # i increases by 2 each term
    }
    return $n;
}

# get sin of x radians
sub mySin {
    my ($x) = @_;
    return computeSeries($x, $x, 3);
}
# get cos of x radians
sub myCos {
    my ($x) = @_;
    return computeSeries($x, 1, 2);
}
# get sin of x degrees
sub sinDeg {
    my ($x) = @_;
    return mySin($x * $pi / 180);
}
# get cos of x degrees
sub cosDeg {
    my ($x) = @_;
    return myCos($x * $pi / 180);
}

# test the functions
print(sin($pi / 6) . "\n"); # 0.5
print(sinDeg(45)   . "\n"); # 0.7071
print(sinDeg(52)   . "\n"); # 0.78801

print(cos($pi / 3) . "\n"); # 0.5
print(cosDeg(45)   . "\n"); # 0.7071
print(cosDeg(52)   . "\n"); # 0.615661

Conclusion

I hope this helps in understanding how computers and languages would go about calculating trigonometric functions like sine and cosine. If you'd like to read more about how exactly mathematical formulas used to calculate the trig functions are derived, I would recommend taking a look at the videos on Taylor and Maclaurin series by Khan Academy.

These programs are all licensed under the CC0 license, so feel free to use any of the code as you wish, without attribution.

Thanks for scrolling.

— Gabriel Romualdo, December 31, 2020

How to Use the HTML5 Gamepad API (with complete examples)

Gabe Romualdo — Tue, 15 Dec 2020 22:30:29 +0000

The HTML5 Gamepad API is one of the more exciting HTML5 APIs in my opinion. It allows a website to pretty easily take input from a game controller that is connected to the user’s machine. The API supports hundreds of game controllers, both wireless and wired, including Xbox One controllers and PS4 controllers to name a few.

Before we begin, note that the gamepad API may not detect a gamepad until you press a button or move a stick on the controller. So, make sure to press some of the buttons when you test any sites or programs that use the Gamepad API.

Note: controllers and other game inputs are referred to as ‘gamepads’ throughout this article and in the gamepad API documentation.

Checking if Your Gamepad is Connected and Troubleshooting Potential Issues

To check if your gamepad is successfully connected, run navigator.getGamepads() in the JavaScript console and check if the result has a Gamepad object, and is not an array of null elements.

If your gamepad isn’t working with the API, here are a few things to try:

check if the device is connected to your machine via bluetooth, USB, or other method
try restarting your computer or web browser
try pressing some of the buttons or moving one of the sticks on the controller so that it is detected
try closing any other games or apps that are using the gamepad

Get a List of Connected Gamepads

The Gamepad API allows up to four gamepads to be connected at once.

To get an array of connected gamepads, use the navigator.getGamepads() method. The array is always of length four, where unused gamepad slots are null. The element(s) of connected gamepad(s) are Gamepad object(s). Here’s an example value of the navigator.getGamepads() method:

console.log(navigator.getGamepads());
// --> [Gamepad Object, null, null, null]
// Here, only one gamepad is connected, and the other three gamepad slots are null.

Before trying to use a the functionality of the Gamepad API, make sure a gamepad is connected using the instructions in the previous section.

The `Gamepad` Object

The Gamepad object includes two important properties that are available in the vast majority of all gamepads and controllers: buttons and axes.

axes is an array of length four which represents the position of the left and right sticks in the gamepad. The first two elements in axes are the (x, y) coordinates of the position of the left stick, whereas the third and fourth elements in axes are the (x, y) coordinates of the position of the right stick. (x, y) values are numbers between -1 and 1 where the (0, 0) means the stick is has not moved.

In the horizontal axes (first and third elements in axes), -1 would indicate the stick is moved fully to the left, and 1 would mean the stick is moved fully to the right. In the vertical axes (second and fourth elements in axes), -1 would indicate the stick is moved fully to the top, and 1 would mean the stick is moved fully to the bottom.

Here’s an example value of axes with explanations in the comments:

setInterval(() => {
    const myGamepad = navigator.getGamepads()[0]; // use the first gamepad
    console.log(`Left stick at (${myGamepad.axes[0]}, ${myGamepad.axes[1]})` );
    console.log(`Right stick at (${myGamepad.axes[2]}, ${myGamepad.axes[3]})` );
}, 100) // print axes 10 times per second

Contrary to buttons in HTML, event listeners cannot be added to gamepad buttons. Instead, you can check if a button is currently pressed by using the boolean pressed property in the element in the buttons array.

Here’s a list of button indexes are their Xbox and PS4 Equivalents in the HTML5 Gamepad API:

Index	Button `.pressed` Code	Button on Xbox	Button on PlayStation
0	`gamepad.buttons[0].pressed`	A	X
1	`gamepad.buttons[1].pressed`	B	O
2	`gamepad.buttons[2].pressed`	X	Square
3	`gamepad.buttons[3].pressed`	Y	Triangle
4	`gamepad.buttons[4].pressed`	LB	L1
5	`gamepad.buttons[5].pressed`	RB	R1
6	`gamepad.buttons[6].pressed`	LT	L2
7	`gamepad.buttons[7].pressed`	RT	R2
8	`gamepad.buttons[8].pressed`	Show Address Bar	Share
9	`gamepad.buttons[9].pressed`	Show Menu	Options
10	`gamepad.buttons[10].pressed`	Left Stick Pressed	Left Stick Pressed
11	`gamepad.buttons[11].pressed`	Right Stick Pressed	Right Stick Pressed
12	`gamepad.buttons[12].pressed`	Directional Up	Directional Up
13	`gamepad.buttons[13].pressed`	Directional Down	Directional Down
14	`gamepad.buttons[14].pressed`	Directional Left	Directional Left
15	`gamepad.buttons[15].pressed`	Directional Right	Directional Right
16	`gamepad.buttons[16].pressed`	Xbox Light-Up Logo	PlayStation Logo

Here's an example of checking if Button One (A on Xbox, X on PS4) is pressed:

const myGamepad = navigator.getGamepads()[0]; // use the first gamepad

setInterval(() => { 
    console.log(`Is Button One Pressed? ${myGamepad.buttons[0].pressed}`);
}, 1000 / 10) // check 10 times per second if the button one is pressed

Detect When a Gamepad Has Been Connected

The name of the event when a gamepad has been connected to the user’s machine is gamepadconnected. The event argument that is passed into the event function includes a gamepad property, which is a Gamepad object for the gamepad the has been connected.

Instead of accessing this gamepad directly, it is more common to get the index of this gamepad in the navigator.getGamepads() array by using the Gamepad.index. For example:

// global gamepad object
let gamepadIndex;
window.addEventListener('gamepadconnected', (event) => {
    gamepadIndex = event.gamepad.index;
});

// now print the axes on the connected gamepad, for example: 
setInterval(() => {
    if(gamepadIndex !== undefined) {
        // a gamepad is connected and has an index
        const myGamepad = navigator.getGamepads()[gamepadIndex];
        console.log(`Left stick at (${myGamepad.axes[0]}, ${myGamepad.axes[1]})` );
        console.log(`Right stick at (${myGamepad.axes[2]}, ${myGamepad.axes[3]})` ); 
    }
}, 100) // print axes 10 times per second

A More Complicated Example

Here's an example program that displays which buttons on a controller are pressed at a given time. Try running this code and pressing buttons on your gamepad; you should see that the indexes of the buttons that are pressed is displayed.

<body>
    <h1>No Controller Connected</h1>
</body>

<script type="text/javascript">
// global gamepad object
let gamepadIndex;
window.addEventListener('gamepadconnected', (event) => {
    gamepadIndex = event.gamepad.index;
});

setInterval(() => {
    if(gamepadIndex !== undefined) {
        // a gamepad is connected and has an index
        const myGamepad = navigator.getGamepads()[gamepadIndex];
        document.body.innerHTML = ""; // reset page
        myGamepad.buttons.map(e => e.pressed).forEach((isPressed, buttonIndex) => {
            if(isPressed) {
                // button is pressed; indicate this on the page
                document.body.innerHTML += `<h1>Button ${buttonIndex} is pressed</h1>`;
            }
        })
    }
}, 100) // print buttons that are pressed 10 times per second
</script>

Browser Support

The HTML5 Gamepad API has complete support in most modern web browsers today. However, there are a few browsers that don't yet support it as of December 2020, including:

IE (11)
Opera Mini
Opera Mobile
Android Browser
KaiOS Browser

For more up-to-date information on browser support, see the Gamepad API's CanIUse Page.

To check if the browser supports the Gamepad API in JavaScript, the following code can be used:

const hasGamepadAPI = () => "getGamepads" in navigator;

Conclusion

I hope this helps in learning how to use the HTML5 Gamepad API. While the API is not yet widely used in online games at the moment, it can still be useful for a number of projects and can be fun to try out.

Thanks for scrolling.

— Gabriel Romualdo, December 15, 2020

How to Schedule Cronjobs in Python

Gabe Romualdo — Sat, 12 Dec 2020 22:52:11 +0000

Cronjobs are tasks that can be run periodically, such as every five minutes, or every day at midnight, or even every Friday at noon.

Cronjobs have a number of different use cases, and are widely used in many notable codebases.

Many hosting servers have existing ways to set up cronjobs, but if you don't have that capability, you may want to go for a different solution.

I'll explain how you would go about creating cronjobs in Python, in which a Python function, program, or command can be run periodically, whether that be every day, every few minutes, or even every month or year.

Check if you have Python 3 installed:

If the following command does not yield a version number, download Python 3 from python.org.

python3 -V

Install the schedule package from Pypi

Run this command to install the schedule package:

pip install schedule

Or if you're using pip3:

pip3 install schedule

Set up and run a cronjob with the .do method

To schedule a cronjob, use the .do method combined with the .every method and others to choose when the cronjob should be run.

The methods for scheduling cronjobs are pretty intuitively named, and more information on them can be found on the schedule package documentation.

After setting up your cronjob(s), create an infinite loop to run the cronjob(s) that are scheduled.

You can also schedule multiple cronjobs if you'd like by adding them with the .do method, just like how the initial cronjob was created.

import schedule
from time import sleep

def cronjob():
    print("Hello, World!")

# create the cronjob
schedule.every(5).minutes.do(cronjob) # runs cronjob every 5 minutes

# run the cronjob
while True:
    schedule.run_pending()
    sleep(10) # check to run the cronjob every 10 seconds

More `.do` Method Examples

schedule.every(15).minutes.do(cronjob) # every 15 minutes
schedule.every().hour.do(cronjob) # every 1 hour
schedule.every().day.at("07:00").do(cronjob) # every day at 7:00 AM
schedule.every(2).days.at("18:30").do(cronjob) # every other day at 6:30 PM
schedule.every().friday.at("17:00").do(cronjob) # every Friday at 5:00 PM
schedule.every().minute.at(":17").do(cronjob) # every minute at 17 seconds
schedule.every(10).seconds.do(cronjob) # every 10 seconds

Conclusion

I hope this helps. I've found Python cronjobs like these particularly useful in a few of my projects. For example, I use cronjobs to periodically update data on the COVID-19 pandemic for my site Coronavirus Live Monitor, and daily cronjobs are used to publish new posts for Daily Developer Jokes, a project of mine which publishes programming humor every day at 8 AM (ET).

Thanks for scrolling.

— Gabriel Romualdo, December 12, 2020

How to Generate the Sierpinski Triangle in Vanilla JavaScript with HTML5 Canvas

Gabe Romualdo — Sat, 21 Nov 2020 04:15:36 +0000

The Sierpinski triangle is a famous mathematical figure which presents an interesting computer science problem: how to go about generating it. In this article I'll explain one method of generating the Sierpinski triangle recursively, with an implementation written in Vanilla JavaScript using HTML5 canvas. I'll also explain how to you'd go about downloading the contents of an HTML5 Canvas element as a PNG.

First, here's what the Sierpinski triangle looks like:

What is the Sierpinski Triangle?

The Sierpinski Triangle is a Fractal, Making it Naturally Recursive

One initial thing to notice about the Sierpinski triangle is that every triangle is composed of smaller, identical triangles. Those triangles are also made up of even smaller, identical triangles, which are also made up of more triangles, and so on.

This property in which the Sierpinski triangle is made up of identical, scaled-down copies of itself makes it a fractal in mathematics. Fractals are shapes that are made up of scaled down copies of themselves. The Sierpinski triangle is actually arguably one of the most famous fractals that exist, along with Pythagoras Trees, the Mandelbrot set, and more.

The fact that fractals are made up of copies of themselves makes them naturally recursive, and it tends to be simpler to programmatically generate fractals recursively as supposed to using an iterative approach.

The Sierpinski Triangle Only Uses Equilateral Triangles

Next, notice how the Sierpinski triangle is made up of a single shape: the equilateral triangle. This is not a coincidence, and it is in fact one of the reasons the Sierpinski triangle is a notable mathematical figure.

The Sierpinski triangle takes advantage of a property of equilateral triangles: that they are one of the only shapes that can be made up solely by scaled down versions of itself, where a large equilateral triangle can be made by tesselating four equally smaller equilateral triangles. This makes them uniquely positioned to be the centerpiece of simple fractals, since it is intuitive to encompass smaller copies of an equilateral triangle inside a larger one.

This also makes it possible for fractals based on equilateral triangles, like the Sierpinski triangle, to be composed of only one shape. Other polygon-based fractals that don't use equilateral triangles often include several different shapes.

Generating the Sierpinski Triangle in JavaScript with HTML5 Canvas

Setting Up the HTML and Canvas Element

Let's start by setting up the canvas element and basic HTML markup:

<!DOCTYPE html>
<html>
  <head>
    <title>Sierpinski Triangle</title>
  </head>
  <body>
    <canvas id="canvas" width="1000" height="1000"></canvas>

    <!-- JavaScript Code Here -->
    <script></script>
  </body>
</html>

Note that the width and height variables in the canvas represent the inner dimensions of the canvas, not necessarily its size on the page. This means it can be resized in the future to fit different screen sizes, while maintaining its inner dimensions of 1000px by 1000px.

Creating Equilateral Triangles on the Canvas in JavaScript

Since equilateral triangles are the only shape used in the Sierpinski triangle, it makes sense to write a utility function to draw a given equilateral triangle on the canvas at a specified position and of a specified size.

This function will take in two arguments: the position of the bottom left vertex on the triangle (pos), and the length of the sides of the triangle (sidelen).

To create polygons in HTML5 canvas, there are several functions to move to positions on the canvas, draw a path around an area of the canvas, and fill in that area. These include:

context.beginPath() and context.closePath() — create and close a path; commonly used with context.fill() after closing the path
context.moveTo(x, y) — move to a position on the canvas.
context.lineTo(x, y) — move to a position on the canvas while drawing a line from the current position.
context.fill() — fill the most recent canvas path.

Creating a triangle simply means identifying the positions of the three vertices, drawing a path around those vertices, and filling the drawn area with a color. Identifying the positions of the vertices is pretty intuitive. Below is a visual showing the positions of the vertices. Note that the height of an equilateral triangle is mathematically equal to as sin(Pi/3) * sidelen.

With the positions of the vertices done, here's what the function to create an equilateral triangle on the canvas would look like:

const c = document.getElementById("canvas");
const ctx = c.getContext("2d"); // context variable is used to draw on a 2D plane

const createTriangle = (pos, sidelen) => {
  ctx.beginPath();
  ctx.moveTo(...pos); // go to the left vertex

  // note that (0,0) in canvas is the top left, so 'up' on the vertical component would use substraction.
  ctx.lineTo(pos[0] + sidelen / 2, pos[1] - sidelen * Math.sin(Math.PI/3)); // draw line from left vertex to top vertex
  ctx.lineTo(pos[0] + sidelen, pos[1]); // draw line from top vertex to right vertex
  ctx.lineTo(...pos); // draw line from right vertex back to left vertex
  ctx.closePath();
  ctx.fill(); // fill triangle
};

Implementing an Algorithm to Generate the Sierpinski Triangle

Now that the canvas and HTML has been set up and the createTriangle utility function has been written, we can start implementing an algorithm to generate the Sierpinski triangle.

Since fractals are naturally recursive, we'll use a recursive approach to generate the entire triangle.

First, recall that every triangle in the Sierpinski triangle is made up of three smaller triangles, one on the left, another on the right, and a final one on the top. Each smaller triangle is a copy of the outer triangle, the Sierpinski triangle. So, simply create a smaller Sierpinski triangle inside of each of the three triangles, and then more smaller Sierpinski triangles inside of those, and so on. Technically, the Sierpinski triangle repeats forever, but for visualizations like this, a stopping point should be defined when there have been enough repeats that the smallest triangles are hard to make out. At this point, filling in the smallest triangles acts as an effective substitution of repeating further.

To create this stopping condition, a variable called depth can be used. depth would represent the amount of times the program should continue repeating the fractal. depth should start at a certain value and decrease for every repeat, and every smaller Sierpinski triangle created. Once depth reaches zero (the base case), the program would stop and fill in the three triangles instead of continuing to repeat the fractal.

To create this functionality, let's create a function called createSierpinskiTriangle which takes the position of the Sierpinski triangle to generate, its side length, and the depth. The function should identify the positions of the three inner triangles, draw them if depth is equal to zero, or call createSierpinskiTriangle on the three inner triangles if the depth is greater than zero.

Here's what this would look like:

const createSierpinskiTriangle = (pos, sidelen, depth) => {
  const innerTriangleSidelen = sidelen / 2; // side length of inner triangles is half the side length of the outer triangle
  const innerTrianglesPositions = [
    pos,
    [ pos[0] + innerTriangleSidelen, pos[1] ],
    [ pos[0] + innerTriangleSidelen / 2, pos[1] - Math.sin(Math.PI/3) * innerTriangleSidelen ]
  ]; // these positions are the same as what was used in the createTriangle function
  if(depth === 0) {
    innerTrianglesPositions.forEach((trianglePosition) => {
      createTriangle(trianglePosition, innerTriangleSidelen);
    });
  } else {
    innerTrianglesPositions.forEach((trianglePosition) => {
      createSierpinskiTriangle(trianglePosition, innerTriangleSidelen, depth - 1);
    });
  }
}

To call the function, draw the Sierpinski triangle at the bottom left of the canvas ((0, 1000)) with a side length of 1000px (the width of the canvas) and a depth of 5.

createSierpinskiTriangle([0, 1000], 1000, 5);

Here's the result:

Try increasing the depth, and you should see that the triangle gets more and more detailed. Increasing the depth by one will result in three times the amount of total triangles to be drawn, so very high depths like 20 might not be performant since the canvas would have to draw 3^20 (~3.5 billion) triangles.

Downloading the Generated Triangle From the Canvas as a PNG

Now that we've generated the triangle recursively, one thing you may want to do is download the generated Sierpinski triangle as an image on your computer. Luckily, this is very simple to do in HTML5 Canvas.

First, the canvas must be converted to a data URL. If you're not familiar with data URLs, here's a simple definition:

A data URL is a URL scheme that allows data and files (images, audio files, etc.) to be respresented in a single URL containing all of the data. For example, if one wanted to include an image on a website, you would add the image to the web server and link to it in the HTML. With data URLs, the data URL contains the contents of the entire file, so it can simply be put into the HTML directly. This is useful in canvas because we want to export the image without it having a specific public URL, and data URLs allow that to be done.

The contents of the canvas element can be converted to a data URL with the .toDataURL method.

Next, let's download the data URL into the user's machine. In HTML, downloading a file is done by clicking a link and specifying the download attribute. For example, here's how someone would download an image as myimage.png when the user clicks a link: <a href="image.png" download="myimage.png">download!</a>.

Downloading a file through JavaScript is as simple as creating a link element with the specified href and download attributes, and artificially clicking on it.

Here's what this would look like:

const downloadCanvasContents = () => {
  const link = document.createElement('a'); // create link element
  link.download = 'Sierpinski Triangle.png'; // set download attribute
  link.href = c.toDataURL(); // set the link's URL to the data URL to be downloaded
  link.click(); // click the element and download on the user's browser
}

Try running downloadCanvasContents() in the JavaScript console after the Sierpinski triangle has been generated! An image should be downloaded to your machine with the contents of the canvas element.

To create a download button, adding a simple HTML button with the onclick attribute set to the downloadCanvasContents function should suffice.

<button onclick="downloadCanvasContents()">Download Generated Sierpinski Triangle</button>

Final Code and Conclusion

I hope you enjoyed this article, and found it interesting in generating the Sierpinski triangle with HTML5 canvas. For more mathematical background on the Sierpinski triangle and its history, I would recommend taking a look at the Sierpinski Triangle Page on Wolfram MathWorld and the Sierpinski Triangle Wikipedia Page.

Feel free to take a look at the final code.

Thanks for scrolling.

— Gabriel Romualdo, November 20, 2020

Performance of AI Algorithms in Playing Games — Empirical Evidence From Jupiter, My 2048 AI

Gabe Romualdo — Sun, 11 Oct 2020 18:48:47 +0000

I recently worked on an open source project called Jupiter, an online AI written in JavaScript to beat the popular online game 2048.

The AI uses the Monte Carlo Tree Search (MCTS) algorithm, which makes moves based on the results of many simulations of random games, also known as Monte-Carlo simulations.

I've written an article on how this algorithm works, how it can be implemented, and where MCTS can be useful. I highly recommend reading that article:

Here's a brief summary of the algorithm that you can feel free to skip if you've read the above article or you understand it already:

To find the optimal move at any given position, the program conducts a set of simulations for each possible move in that position (ex: left, right, up, or down). For each set of simulations, the algorithm starts by playing the move for that set first.

After that, the rest of the game can be played completely randomly until it is over. The algorithm can then gather the total final game scores (sum of all the tiles on the board) of all the simulations, and average them for each set. We can then find the optimal move by optimizing for the highest final game score.

For example, there could be 50 simulations where the first move was left, in which the average score for those simulations was 250. Support there were 50 simulations for each of the right, up, and down moves, and the average score for the 50 simulations in each of those was only 225. In this case, the optimal move would be left since the algorithm optimizes for the move that yields the highest final game score.

In this article, I'll be analyzing the performance and speed of Jupiter's algorithm with empirical data, and note potential improvements made to the algorithm and its JavaScript implementation on the web.

Let's start with a few definitions that are relevant to the rest of the article:

Performance: how well the AI performs at the end of each game, in which a higher final game score would be better
Speed: how fast the AI performs in real-world speed running on the web in JavaScript, in which a higher speed to perform moves would be better
Game State: a set of tiles on the board which represents the board at a specific time
Game Score: the sum of all the tiles on the board
Real Game: the game that is being played and shown on the browser, not a simulation
Landmark Score/Tile: a high tile or score of a power of two like 512, 1024, 2048, or 4096

Analyzing the Performance of the Algorithm

I ran 50 trial games with the AI at 200 simulations per move in about 34 minutes (avg. 40.8s/trial), storing data after every move, including:

Current Game Score
Best Tile in the Board
Average Score of Simulations
Average Move Count of Simulations
Milliseconds Taken to Calculate Optimal Move
The Move Made

The default 200 simulations per move used is meant to be a baseline so that the AI runs a decent speed at all tiers of devices including phones and tablets as well as desktops and laptops. I have personally done runs with 1500 simulations per move and have achieved much better results there while sacrificing speed in the process.

Game Score and Best Tiles

In all of the 50 simulations done, 96% reached at least the 1024 tile, 62% reached at least the 2048 tile and 2% reached the 4096 tile. None of the simulations reached a tile beyond 4096.

For game score, all trials reached at least 1024, including the two trials which didn't get the 1024 tile itself.

In fact, there's a clear trend in which games reach a landmark game score like 2048 or 4096, but don't survive long enough to get the tile itself.

I hypothesize this is because the game begins to get very cluttered with tiles right before a landmark tile is reached. For example, one move before getting 4096, the game board must already include at least 11 tiles: 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, and 2. In this case, the placement of the tiles could not be ideal, or a 4 tile may appear where a 2 tile was needed. As a result, the board could have all the tiles it needs to achieve a landmark tile, but is too cluttered and the game ends up ending before the landmark tile is reached.

Another trend here is in trials which ended between the 2048 and 4096 game scores. There are several of these and this is likely because of board clutter. The algorithm doesn't have a built-in heuristic for tile placement, so tiles aren't perfectly lined up in increasing order like other strategies use.

This becomes a problem for very high tiles, depending on the total simulations per move. For 200 simulations per move, it looks like 4096 is the most common to cause cluttering problems.

Jupiter is Very Different to Other AIs and Strategies

One of the most interesting things about Jupiter's algorithm is that it doesn't follow a particular strategy. Watching Jupiter play 2048, it's hard to see any sort of pattern in its moves, other than the fact that it wins most of the time.

The most common winning strategy among humans is a system where all tiles are lined up in increasing order along rows, alternating the direction in each row so that tiles can easily be added as new ones appear. Jupiter does not follow this type of strategy; in fact, it has no built-in strategy or heuristics at all.

I personally see this as an advantage which makes Jupiter a more creative AI. Jupiter's algorithm typically leads to more interesting and less predictable 2048 gameplay than other 2048 AIs or strategies. However, Jupiter's algorithm has a lack of precision that can lead to the issues with board clutter, because tiles are not algorithmically placed in a logical pattern.

The common human strategy mentioned also depends on the idea that tiles are concentrated on a particular corner, which results in two of the possible moves (up and right in the above visualization) being used much less than their counterparts. Jupiter is not like this, and makes all moves an equal fraction of the time.

What a Single Trial Game Looks Like

Let's take a look at a single game trial, trial #50, which got to the 4096 tile.

As we can see, the current game score is almost linear, with an approximate 2.2 slope. This is because in 2048, a new tile is added after each move. This new tile is typically a 2 tile, but has a 10% chance of being a 4 tile instead. Thus, the expected value of the new tile is 2.2 (2 × 90% + 4 × 10%), which increases the game score by an average of 2.2 after every move.

The average game score of all the simulations is always slightly above the current game score, because random moves incur a few tile combinations and increase the score before the simulated game ends.

And as noted previously, game score is directly connected to current game move count, where game score can be calculated by multiplying current game move count by 2.2. Therefore, spikes in average move count of simulations occur identically in the average score of simulations as well.

Notice how all three of these things occur at the same time:

Increase in best tile
Spike in average move count of simulations
Spike in average score of simulations

In the graph, average score of simulations is scaled to be much smaller than average move count of simulations, so you may have to look closely to see spikes there.

As we can also see, the game score reaches a landmark before the corresponding landmark tile is actually reached — when the orange best tile line jumps up, the blue game score line has already surpassed the value of the orange best tile line.

Finally, possibly the most interesting insights we can gain from this graph are from the yellow average move count of simulations variable.

In the beginning, the average move count starts very high because there are very little tiles on the board, and the ones that are there are tiles 2 or 4. This means that simulations can survive pretty long by just playing randomly.

As higher tiles are created, the average move count starts getting lower and lower because there is more clutter and therefore a higher chance of the game ending in a shorter period of time.

The less clutter there is on the board, the higher the average move count is. Clutter is reduced by combining larger and larger tiles.

As a result of this relationship with tile combination, the amount of board clutter, and thus the average move count, we can see a clear fractal-like repeating shape, in which the average move count spikes up, goes down over time, spikes up again, goes down over time, and repeats.

These spikes are always when large tiles are created by combining smaller ones. This is corroborated by the fact that several of these spikes occur at the same time as new best tile being created (see 512, 1024, 2048 for example).

In the middle of each new best tile being created, there is another smaller spike, which we can assume is the tile half of the next best tile. For example, we can see right in the middle of 1024 and 2048 being reached, there is a large spike. This is likely when a new 512 tile was created. Subsequently we can see even smaller spikes between all adjacent spikes, corresponding to tiles being created with even smaller powers of two.

Speed Improvements for Running on the Web, in JavaScript

Speed was a key issue I faced while developing Jupiter, particularly because it runs on the web with frontend JavaScript code. Because it runs on the web, I had to make sure it could run well on lower-end devices including phones.

I made several speed improvements, starting by refactoring code in my 2048 game implementation. I made changes to the gameover checking method and move methods to make them more efficient, resulting in a ~25% increase in speed. One immediate problem I faced was that code was running on the main thread. The main thread is not only responsible for running JavaScript code, but also dealing with various events such as mouse clicks. When other JavaScript code is currently running on the main thread, it can sometimes block events from being picked up and run. To remove this blocking, I had defer code to different threads.

On the web, this is done by using Web Workers. Each Web Worker runs on a separate thread, and I found that the optimal number of Web Workers is typically eight. I divided simulations and tasks among all eight of these workers equally to optimize speed. Concurrency with workers in JavaScript is thankfully very simple and works with message passing, so this took little effort to implement.

I kept the original implementation without workers in the code to run for browsers like Opera Mini that don't support the Web Workers specification.

This increased performance greatly. On a mid-tier laptop running on battery power, I was able to run 50 trials of full games on 200 simulations per move in approximately 34 minutes. This meant that I was able to run one full game of 2048 with approximately 1600 moves in about 40.8 seconds on average. This means the AI played ~39 moves per second, with each move taking ~25 ms to calculate.

Overall, the speed improvements made in both optimizing existing JavaScript code and using Web Workers greatly improved the speed of the program, and allowed it to calculate millions of simulations for hundreds of thousands of moves in just minutes.

Conclusion

I hope you enjoyed this post, and found it interesting in analyzing performance and improving the speed of Jupiter, my 2048 AI.

Go check out Jupiter and its source code on GitHub.

Thanks for scrolling.

— Gabriel Romualdo, October 11, 2020

I Built Jupiter – A Machine Learning Based 2048 AI that Runs on the Web

Gabe Romualdo — Sun, 13 Sep 2020 03:16:00 +0000

Today I'm proud to release my online 2048 AI, Jupiter. Jupiter uses a machine learning method called the Monte Carlo Tree Search (MCTS) algorithm.

Check it out:

A Quick Preview of the AI

This is a snippet of some of what you'll see when you go to the Jupiter website.

Relevant Links

Jupiter (Website) — run the AI on your browser and see realtime AI statistics.
Jupiter GitHub Repo and Source Code — check out the code and feel free to submit a PR or issue.

More About This Project

Jupiter (formerly known as Jacob) started as a small AI project in January 2018. I got the idea of using Monte Carlo simulations and search trees as a method to play 2048 from this StackOverflow answer.

I wrote a basic clone of what was described in the answer and built on the idea with an interactive console and my own 2048 game implementation, in contrast to the existing open sourced game code used in other AI projects. At this time, Jupiter ran on the main JavaScript thread, and had decent performance and speed: it was able to run ~800 Monte Carlo simulations of possible games per second. Running the game at 200 simulations per move gave roughly 4 moves per second. This amount of simulations reaches the winning 2048 tile about 65-75% of the time.

In August 2020, I took a look at the project once again and noticed the potential to improve both performance and speed of the AI. I did some more research on Monte Carlo simulations and search trees, notably watching a great lecture by MIT Prof. Guttag in MIT's 6.0002 undergraduate course. In the one and a half years since I had first started the project, I'd also learned and used numerous modern JavaScript features, frameworks, and libraries. This put in me the unique position to use these new skills to extend this project vastly from performance, speed, bundle size, and design perspectives.

So, I spent time refactoring existing code and replacing older algorithms with newer and more performant ones. In particular, I took advantage of modern JavaScript features like Web Workers to differ tasks to new threads and utilize concurrency capabilities. I also added Webpack to the project for the automated speed and bundle size optimizations built into many of its loaders. With new CSS and design skills I had learned over the past one and half years, I built a new design for the site, with a clearer console and mobile responsiveness. And finally, among many other features, I added "tile milestones" to let users know how fast the AI had reached certain tiles in the game.

With the numerous updates to the project in 2020, Jupiter was now able to run ~2650 simulations of possible games per second. Running the game at 200 simulations per move gave around 13 moves per second. This indicated that performance had more than tripled with the new updates. Moreover, a new addition to the code allowed for performance to grow and scale horizontally by adding Web Workers and threads as general computing speed increases over time.

All in all, the two year gap in which I learned invaluable frontend development and programming skills allowed me to improve the AI drastically in many areas while maintaining the original, extremely effective Monte Carlo based algorithm which stayed the same throughout the development process.

I hope you find this project interesting and take the time to check it out!

If you liked this post, consider following me on DEV.

Thanks for scrolling.

— Gabriel Romualdo, September 12, 2020

Using the Monte Carlo Tree Search Algorithm in an AI to Beat 2048 (and other games)

Gabe Romualdo — Sun, 13 Sep 2020 02:13:27 +0000

I recently worked on an open source project called Jupiter, an online AI to beat the popular online game 2048.

Go try out the AI:

In writing this AI, I decided to use a machine learning method called the Monte Carlo Tree Search (MCTS) algorithm. Monte Carlo algorithms like the one used in Jupiter have been used in several notable AIs, including DeepMind's AlphaGo, which famously beat the Go world champion in May 2017.

In this article, I'll explain:

How and why the Monte Carlo method works
When and where Monte Carlo algorithms can be useful
How I used the Monte Carlo method in an AI to beat 2048
How to implement Monte Carlo algorithms in JavaScript and other languages

Note: I got the idea of using a Monte Carlo method to beat 2048 from this StackOverflow answer.

What is the Monte Carlo Method?

The Monte Carlo method is the idea of using a large number of random simulations of an experiment to gain insights into the experiment's end results. Random simulations of an experiment are frequently referred to as Monte Carlo simulations.

For example, let's say that you were flipping a coin, and trying to figure out the probability of the coin landing heads. With the Monte Carlo method, we could simulate 10,000 coin tosses, and calculate the percentage of coins that landed heads.

Here's what that would look like.

As can be seen, the result converges to the expected value, 50%. A notable feature of Monte Carlo simulations is that a higher number of simulations is correlated with higher accuracy. For example, if we only performed two simulations, there is a high (25%) probability of heads landing in both simulations, giving a result of 100%. This is very inaccurate in comparison to the expected result of 50%.

Monte Carlo simulations work because of the Law of Large Numbers, which says:

If you simulate the same experiment many times, the average of the results should converge to the expected value of the simulation.

In other words, Monte Carlo simulations are a way to estimate what will happen in a given experiment without having to implement any specific algorithms or heuristics.

When and Where the Monte Carlo Method Can Be Useful

The Monte Carlo method is used in a variety of fields, including game AI development, finance and economics, and evolutionary biology to name a few.

The Monte Carlo method can be useful in any experiment with a random factor, where end results cannot be predicted algorithmically. For example, in 2048, a new tile at a random location is added after every move, making it impossible to calculate the exact location of upcoming tiles and subsequently the end result of the game as well.

In these types of experiments, running a large number of Monte Carlo simulations can help get a sense of the average end results, the probability of various events occurring, and the relationship between the variables in the experiment.

For example, using the Monte Carlo method to in Jupiter allowed me to better understand how variables like starting move, number of moves in a game, and best tile in the board affected the end results of the game.

How I Used the Monte Carlo Method in Jupiter, an AI to Beat 2048

Let's start with a few definitions:

Board and Tiles: a 4x4 grid with tiles optionally placed on each grid spot
Game State: a set of tiles on the board which represents the board at a specific time
Game Score: the sum of all the tiles on the board
Real Game: the game that is being played and shown on the browser, not a simulation

At any given game state, let's assume that four possible moves can be made: left, right, up, or down.

There are indeed cases where a certain move is not possible in a given game state. Removing impossible moves can be easily added to the algorithm later.

With the Monte Carlo method, we can run a set of game simulations for every move.

For each possible move, the program simulates a set of simulations which start by playing the move for that set first. After that, the rest of the game can be played completely randomly until it is over.

In JavaScript, this algorithm looks something like:

// assume Game object exists
// assume currentGame variable exists as the real game

const totalSimulations = 200; // 50 simulations are played for each move 

const possibleMoves = ["left", "right", "down", "up"];
possibleMoves.forEach((move) => { // simulations for all four possible starting moves
  for(let i = 0; i < totalSimulations / 4; i++) {
    const simulation = new Game(); // create simulation
    simulation.board = currentGame.board; // copy current game state to simulation
    simulation.makeMove(move); // make initial move
    while(!simulation.gameover()) {
      simulation.makeMove(possibleMoves[Math.floor(Math.random() * 4)]);
    } // make random moves until simulation game is over
  }
});

After all the simulations are completed, the program can gather the total final game scores of all the simulations, and average them for each move. We can then find the optimal move by optimizing for the highest final game score.

For example, if the simulations which started by playing left had an average final score of 250, whereas the ones which started by playing the other moves had an average final game score of 225, then left is the optimal move.

In this program, the optimal move is the one with simulations with the highest average final game score.

Note: I could have chosen to optimize for a different value such as the number of moves in the game.

However, this would actually make no difference in how the algorithm functions, because the number of moves in the game almost exactly predicts the game score. In 2048, the new tile added after each game move is normally a 2 tile, but has a 10% chance of being a 4 tile instead. This means the expected value of the new tile is 2.2 (2 × 90% + 4 × 10%). The total value of tiles is also preserved after every tile combination (ex: 2 tile combined with another 2 tile gives a 4 tile). As a result, game score can be calculated by multiplying the expected value of the new tile by the number of moves in the game, or with this formula: 2.2 × (real game move count + average move count).

To add this functionality of optimizing for highest score to our current code: add an array of total final scores for the simulations for each possible move, and choose the move with the highest value in that array to play like so:

const possibleMoves = ["left", "right", "down", "up"];
const totalSimulations = 200;

let moveSimulationTotalScores = [0, 0, 0, 0];

possibleMoves.forEach((move, moveIndex) => { // simulations for all four possible starting moves
  for(let i = 0; i < totalSimulations / 4; i++) {
    const simulation = new Game(); // create simulation
    simulation.board = currentGame.board; // copy current game state to simulation
    simulation.makeMove(move); // make initial move
    while(!simulation.gameover()) {
      simulation.makeMove(possibleMoves[Math.floor(Math.random() * 4)]);
    } // make random moves until simulation game is over
    moveSimulationTotalScores[moveIndex] += simulation.getScore();
  }
});

// make best move with highest total simulation scores
let topScore = Math.max(...moveSimulationTotalScores);
let topScoreIndex = moveSimulationTotalScores.indexOf(topScore);
let bestMove = possibleMoves[topScoreIndex];

currentGame.makeMove(bestMove);

In the end, this algorithm is simple to implement given a well-written 2048 game class. In JavaScript, there are a number of performance upgrades that can be made, starting by adding concurrency with Web Workers and pruning moves with very low final game scores.

Conclusion

I hope you enjoyed this post, and found it useful in helping you understand and implement the Monte Carlo method in your own projects.

Go check out Jupiter and its source code.

Thanks for scrolling.

— Gabriel Romualdo, September 12, 2020

How to Parse XML in Python

Gabe Romualdo — Sun, 16 Aug 2020 02:40:27 +0000

TL;DR

from xml.dom import minidom

parsedXML = minidom.parseString("[your xml here]")

elements_by_tag = parsedXML.getElementsByTagName('[tagname here]') # get list of elms with tagname
print(elements_by_tag[0].firstChild.nodeValue) # print inner text value of an element

Introduction

I recently spent a few hours refactoring some of the backend code on my personal website. In changing the backend, I wanted to make sure the refactored code worked the same way as my old code.

To do this, I wrote a unit test in Python that sent a request to every URL on my site running the old backend code and the corresponding URL with my local server running the new code, to make sure they worked exactly the same.

As with many other sites, I have a sitemap which lists all of the URLs on the site with their titles and other information for search engines and other bots. Since this sitemap is programmed to output all of the URLs on my site (excluding error pages like the 404 page), this seemed like a perfect way to get a list of URLs on my site to test the new backend code.

Sitemaps are written in XML, a language very similar to HTML, with the same tag and element based syntax.

So, to go about getting all the URLs from my sitemap, I had to get the raw XML from the sitemap, and then parse that XML to get items of a particular tag name (loc in this case).

1. Parse XML with XML.DOM Minidom

To parse the XML, we'll use Python's default xml.dom.minidom module.

The minidom module has a handy .parseString method to parse XML from a Python string. The method returns an object with other methods for getting information from the parsed XML, and selecting various elements.

from xml.dom import minidom

parsedXML = minidom.parseString("""
<urlset xmlns="http://www.sitemaps.org/schemas/sitemap/0.9">
    <url>
        <loc>https://gabrielromualdo.com/</loc>
        <changefreq>weekly</changefreq>
        <priority>0.9</priority>
    </url>
    <url>
        <loc>https://gabrielromualdo.com/about/</loc>
        <changefreq>monthly</changefreq>
        <priority>0.6</priority>
    </url>
</urlset>
""")

Now we can call various functions on the parsedXML variable to get information from elements in the XML.

2. Get Elements by Tag Name

Getting elements by tag name from parsed XML in xml.dom.minidom is pretty simple: use the getElementsByTagName function.

For example, in my case I want a list of elements with the tag name of loc:

elements = parsedXML.getElementsByTagName('loc') # any tag name in place of 'loc' is valid

3. Get the Inner Text of a Particular Element

Now that I had a list of loc elements, I needed to get text of each of those elements and add those to their own list.

To get text from an element in xml.dom.minidom, use the firstChild.nodeValue property of the element, like this: element.firstChild.nodeValue.

In my case, here's how I looped through each element and added the text content to a variable:

elements = parsedXML.getElementsByTagName('loc')

locations = []

for element in elements: # loop through 'loc' elements
    locations.append(element.firstChild.nodeValue); # get innertext of each element and add to list

print(locations) # https://gabrielromualdo.com/ https://gabrielromualdo.com/about/

In getting the text of an element, the firstChild property gets the text node from the element, and the nodeValue property gets the value of that particular text node.

Conclusion

You can see the final source code of this article here at my tutorials repo.

I hope you enjoyed this post and found it useful in parsing XML from a URL in Python. I spent some time reading documentation myself to get this working myself, so I thought I'd make this post to help anyone out.

Thanks for scrolling.

— Gabriel Romualdo

Build and Deploy a Discord Bot with Node and Discord.js in 5 minutes

Gabe Romualdo — Sat, 08 Aug 2020 01:54:42 +0000

Title assumes 265 words per minute reading time, as used by Medium and others.

Discord bots can be useful in doing a variety of things like playing music in a voice chat, or sending automated announcements when a Youtuber releases a new video.

I'm active on several Discord servers myself and have always wanted to build my own Discord bot. After building, deploying, and using my own bot for over a month now, I've written this article as a starting point in building a basic bot and moving from there.

We'll be building a bot that does something pretty simple: solves math equations. Users will be able to send a message on any channel that looks like !solve [math equation] and receive a response with the calculated result. For example:

Before Reading, You Should:

Know basic JavaScript and Node.js (with Node and NPM installed)
Have a Discord account (create one here)

1. Create a Discord API Application and Bot

Go to discord.com/developers/applications and click 'New Application' on the top right. Let's call the app 'Solver Bot'.

By creating an app, you'll be able to get a unique API key to connect to the Discord API, create a bot, and do things like send and receive messages with that bot.

Now click on the 'Bot' tab on the right sidebar and click 'Add Bot'.

Add a profile picture to the bot by importing a file from your local machine.

I'll be using an icon which you can download here (this icon is CC0 Licensed, and you can use it without attribution).

2. Add Your Bot to a Server!

Now that we've created a Discord API App with a bot account, we can add the bot to a server. I recommend making your own server to test your bots.

To add a bot to a server, all we need is an Discord OAuth2 URL. Upon opening this URL, any Discord user can add your bot to a server they own, and grant it permissions.

To generate the URL, open up the OAuth2 tab.

You'll see a grid of checkboxes, and here, select the 'bot' option. Another grid should appear, and here is where you'll select bot permissions. For this basic bot, we'll just need to manage and read messages.

Given these selected options, Discord automatically generates an OAuth2 URL, which you can see in the input box under the first grid. The URL should look something like https://discord.com/oauth2/....

Try copying and opening the URL! You should be able to add the bot to any servers you own.

3. Create the Functionality of Your Bot With Node and Discord.js

Let's start building the functionality of the bot in Node.

Make a new folder (or Git repository if that's what you prefer) on your machine called discord-solver-bot.

On your Terminal or Command Line, navigate to the folder and run npm init, adding any the necessary details when you see fit.

Now, let's add our dependencies. We'll be using Discord.js, a package which simplifies connecting and using the Discord API. For solving math equations, we'll use the useful Equations module.

Run npm install discord.js equations --save to install these packages.

Okay, now we can create an index.js file in the folder and start writing some code.

We can start by importing any necessary packages.

const Discord = require('discord.js');
const Equation = require('equations').default; // .default to fix a problem I encountered while importing without it

Connect to Your Bot With Your Bot Token and Login to Discord

To connect to your bot with Discord.js, we initialize Discord.js Client object to connect to the Discord API.

To login with our bot with the client, we need the bot token. Copy the token by going to your app in the developer portal > bot > token > copy.

Now we can login to our bot by calling the Client login function and passing the copied token.

const client = new Discord.Client();
client.login("[your bot token here]");

Don't share your bot token with anyone else. It can be used to take complete control over your bot.

Check if Your Bot is Logged In

To check if your bot is logged in and ready to do things on Discord, use the Client ready event:

client.on('ready', async () => {
  console.log(`Logged in successfully as bot!`);
});

Try running the bot by running node index.js. You should see that your bot is logged in. In Discord, you should also be able to see that the bot is marked as online.

Listen for a Message and Respond

Use the client message event to listen any time a user sends a message anywhere on any server the bot is on. The event comes with a message object which contains the content (text content of the message) property among others.

The object also has a .reply method, for your bot to reply to the message directly to the user that sent it.

Typically a message we're looking for looks like !solve [equation here].

So, all we have to do is check if the message starts with '!solve ', and then solve the equation written afterwards. We can do this with the JavaScript string .startsWith and .slice functions respectively.

For solving the equation the equations package has a .solve function to solve any given equation. .solve throws an error if the equation is not valid, and we can catch that error to reply saying the equation could not be solved.

Here's what this code looks like:

client.on('message', (msg) => {
    msg.content = msg.content.trim(); // remove extra whitespace
    const flag = '!solve ';
    if (msg.content.startsWith(flag)) {
        const toSolve = msg.content.slice(flag.length, msg.content.length);
        try {
            const solved = Equation.solve(toSolve);

            msg.reply(`${toSolve} = ${solved}`); // backticks (TLs) are used to embed variables in strings like `${var}`
        } catch (err) {
            msg.reply(`Could not solve the equation '${toSolve}'.`);
        }
    }
});

4. We're Done! Let's Test the Bot

After running node index, go to a server with the bot (in my case my bot testing server), and try sending a message like !solve 2 + 2. You should see a response like 2 + 2 = 4. You can additionally try more complex equations, and test the error checking with a malformed equation.

5. Deploying Your Bot and Next Steps

Deploying your bot is pretty simple. All you have to do is keep the index file (in this case node index) running whenever you want your bot to be online, typically 24/7. You can choose to run it on an old computer or Raspberry Pi, your own server, or you can choose to deploy on a platform like Heroku.

In terms of next steps in building a more complex bot, the Discord.js documentation can be really useful in using the Discord API to perform functions on text and voice channels, multiple servers, direct messages, and more.

In sharing your bot, there are many websites dedicated to listing Discord bots, including bots.ondiscord.xyz, discord.bots.gg, and top.gg. Building a website for your bot can be useful in showcasing its features and linking the URL to add the bot to a server. Sharing the bot among servers you own are know the owner of can also be useful.

Thanks for Reading

View the source code and assets here, at my tutorials repo.

I hope you enjoyed this post and found it useful in creating your own Discord bots with Node and Discord.js.

Thanks for scrolling.

— Gabriel Romualdo

Forem: Gabe Romualdo

Random Seed in JavaScript and Node.js

Introduction

Code

Dependencies

Conclusion

An Algorithm to Swap Two Variables Synchronously, Without Creating a Temporary Variable

Introduction

The Algorithm

Conclusion

How to Set Up Rate Limiting and Rate Slowing Down in Express.js

Rate Limiting in Express

Rate Slowing Down in Express

Rate Limiting vs Rate Slowing Down

Conclusion

Programs to Compute Trig Functions in Python, JavaScript, & Perl (with Maclaurin Series)

Introduction

How the Programs Work

In Python

In JavaScript

In Perl

Conclusion

How to Use the HTML5 Gamepad API (with complete examples)

Checking if Your Gamepad is Connected and Troubleshooting Potential Issues

Get a List of Connected Gamepads

The Gamepad Object

Detect When a Gamepad Has Been Connected

A More Complicated Example

Browser Support

Conclusion

How to Schedule Cronjobs in Python

More .do Method Examples

Conclusion

How to Generate the Sierpinski Triangle in Vanilla JavaScript with HTML5 Canvas

What is the Sierpinski Triangle?

The Sierpinski Triangle is a Fractal, Making it Naturally Recursive

The Sierpinski Triangle Only Uses Equilateral Triangles

Generating the Sierpinski Triangle in JavaScript with HTML5 Canvas

Setting Up the HTML and Canvas Element

Creating Equilateral Triangles on the Canvas in JavaScript

Implementing an Algorithm to Generate the Sierpinski Triangle

Downloading the Generated Triangle From the Canvas as a PNG

Final Code and Conclusion

Performance of AI Algorithms in Playing Games — Empirical Evidence From Jupiter, My 2048 AI

Analyzing the Performance of the Algorithm

Game Score and Best Tiles

Jupiter is Very Different to Other AIs and Strategies

What a Single Trial Game Looks Like

Speed Improvements for Running on the Web, in JavaScript

Conclusion

I Built Jupiter – A Machine Learning Based 2048 AI that Runs on the Web

A Quick Preview of the AI

Relevant Links

More About This Project

Using the Monte Carlo Tree Search Algorithm in an AI to Beat 2048 (and other games)

What is the Monte Carlo Method?

When and Where the Monte Carlo Method Can Be Useful

How I Used the Monte Carlo Method in Jupiter, an AI to Beat 2048

Conclusion

How to Parse XML in Python

TL;DR

Introduction

1. Parse XML with XML.DOM Minidom

2. Get Elements by Tag Name

3. Get the Inner Text of a Particular Element

Conclusion

Build and Deploy a Discord Bot with Node and Discord.js in 5 minutes

Before Reading, You Should:

1. Create a Discord API Application and Bot

2. Add Your Bot to a Server!

3. Create the Functionality of Your Bot With Node and Discord.js

Connect to Your Bot With Your Bot Token and Login to Discord

Check if Your Bot is Logged In

Listen for a Message and Respond

4. We're Done! Let's Test the Bot

5. Deploying Your Bot and Next Steps

Thanks for Reading

The `Gamepad` Object

More `.do` Method Examples