Nepali baghchal game

The twist is that the model has a bottleneck as a hidden layer. So, it learns to represent the input in a smaller amount of data compressed form. Generative modeling is a task that involves learning the regularity or patterns in the input data so that the model can generate output samples similar to the input dataset.

Since my project does not use unsupervised learning, we won't go into its details in this blog. Check out the following to learn more about unsupervised learning:. Reinforcement Learning RL is the type of Machine Learning where an agent learns how to map situations to actions so as to maximize a numerical reward signal from the environment.

At any time step, the agent in state S 1 takes an action A 1. Based on this action, the environment provides the agent with reward R 1 and a new state S 2. A reward is a scalar feedback signal which indicates how well an agent is doing. The agent's goal is to maximize the reward signal. For instance, in the example of flying stunt maneuvers in a helicopter,.

What makes the reinforcement learning problem so much harder is that the agent will initially be clueless about how good or bad its actions are. Sometimes, even the environment might be only partially observable. The agent has to perform hit and trial until it starts discovering patterns and strategies.

Moreover, the agent cannot act greedily on the reward signal. The agent has to learn to maximize the reward signal in the long term. So, sometimes the agent must be willing to give up some reward so as to gain more rewards in the long run.

One such example would be to sacrifice a piece in chess to gain a positional or tactical advantage. The exploration vs exploitation trade-off is the central problem in RL where the agent with incomplete knowledge about the environment has to decide whether to use strategies that have worked well so far exploitation or to make uncertain novel decisions exploration in hopes to gain more reward. To learn more about Exploration vs Exploitation and some solutions, visit Intuition: Exploration vs Exploitation.

Some classical solutions to the reinforcement learning problem are Dynamic Programming, Monte Carlo Methods, and Temporal-difference learning. You can visit RL Course by David Silver to learn more about reinforcement learning problems and solutions. AlphaGo was the first computer program to beat a professional human Go player and the first to defeat a Go world champion.

It was first trained on professional human games and then learned to improve by itself. To learn more, read the AlphaGo Research Paper. AlphaZero was an improved and more general version of AlphaGo that learned to play Go, Chess and Shogi without any human knowledge. It surpassed its predecessor and defeated AlphaGo in games of Go.

To learn more, read the AlphaZero Research Paper. My self-learning AI project is also inspired very closely by AlphaZero. Numerous artificial intelligence projects have tried to hard-code knowledge about the world in formal languages. This approach is known as the knowledge base approach to AI.

However, none of these projects have led to major breakthroughs. Then, machine learning was introduced so that the AI systems could acquire their own knowledge from the data.

The performance of these simple machine learning algorithms depends heavily on the representation of the data and the use of important features. Imagine that we have developed a logistic regression model regression for binary data such as True or False to detect Diabetic Retinopathy diabetes complication that affects eyes.

To use this model, a doctor has to manually observe the retina image and put relevant pieces of information into the model, such as the number and type of retinal lesions damaged regions and where they appear in the image.

If the model was directly given the retina image as shown above, rather than the formalized report from the doctor, it would not be able to make predictions.

It is because the individual pixels of the retina image have a negligible correlation with the presence or absence of Diabetic Retinopathy. Let's look at one more example where the representation of the data plays an important role in the performance of the ML model. Here, it is impossible to separate the two sets of data in cartesian coordinates with a linear model. However, just changing the representation of data to polar coordinates makes this task an easy one.

For many tasks, it is actually very difficult to know what features should be extracted. Suppose we want to write a program that detects cars in images. Since cars have wheels, we might like to use their presence as a feature. However, it is embarrassingly difficult to describe wheels in terms of pixel values. Even though wheels have simple geometric shapes, the real-life images of wheels are complicated by shadows, glaring sunlight, masking of the wheels by other objects, and so on.

One solution to the problem of finding the right feature is representation learning. In this approach, the human intervention is further reduced by replacing the hand-designed features with learned representations by the model itself. In other words, the model not only learns the mapping from features to the output but also learns to choose the right features from the raw data.

Whenever we go from one technique to another, we substitute one problem for another one. Now, the major challenge in representation learning is to find a way for the model to learn the features by itself.

However, it is very difficult to extract high level, abstract features from raw data directly. This is where deep learning comes to the rescue. Deep Learning is a type of representation learning where the representations are expressed in terms of other simpler representations.

This allows the computer to build complex features from simpler features. The quintessential example of a deep learning model is the multilayer perceptron that maps the input to the output. Let's look at an illustration of how a deep learning model learns to recognize complex patterns by building upon simpler concepts in the data. Even though each pixel value of the image has no correlation with identifying the object in the image, the deep learning model builds a hierarchical structure to learn representations.

It first learns to detect edges that makeup corners and contours which in turn gives rise to the object parts. These object parts are then finally able to detect the object in the image. Visit Deep Learning Book Website to read a free online version of the book.

It is an excellent material to get started with Deep Learning. Back in the summer of , I had a few months break before starting my junior year in high school. At that point, I was not new to programming but I barely had any idea about Artificial intelligence AI.

Inspired by AlphaZero, I thought of making a chess engine but the complexity of the game and the amount of training it would require set me back even before I got started. During my senior year, I tried making a similar engine as a science fair project but for a much simpler game of Bagh Chal.

Even then, I had underestimated the difficulty of the project and the time scramble led to the project failure without yielding any results. I stopped working on it for a while until I finished high school and gave it another shot.

Before discussing how reinforcement learning and deep learning was used in the agent's architecture, let's first acquaint ourselves with the game of Bagh Chal. In the upcoming sections, I will also discuss how I built a game library and introduced game notations to record the moves for this traditional and somewhat obsolete game. Bagh Chal is one of the many variants of the tiger hunting board games played locally in South East Asia and the Indian subcontinent.

This ancient Nepali game shares many resemblances to other traditional games like Komikan, Rimau, and Adugo in terms of board structure and player objectives. The strategic, two-player board game is played on a 5x5 grid. The pieces are positioned at the intersection of the lines where adjacent lines from the intersection define the legal moves for a piece.

Throughout the game, tigers also have a special Capture move, where they can jump over a goat along the grid lines to an empty slot, thereby removing the goat from the board.

This asymmetric game proceeds with tigers trying to capture goats and goats trying to trap tigers without any legal moves. The game is over when either the tigers capture five goats or the goats have blocked the legal moves for all tigers. In some rare cases, tigers can also win by blocking all the legal moves for goats.

Games are an important part of any culture, and Nepal has some very interesting and unique ones, of which Baghchal is a good example.

Seemingly simple, this board game nevertheless requires strong tactical play as well as deep positional insights for its mastery. In this project, we have created a Baghchal game for 2 players, as well as a Baghchal engine with AI for playing Baghchal with the computer under various difficulty settings.

Download the game here. One of the players chooses Tiger Bagh and the other chooses Goat Bakhra. There are 4 tigers and 20 bakhras when the game starts. The objective for each player is different. The goat side tries to trap all the tigers and prevent their movement. When the tigers have no legal move remaining, the goats win.

On the other hand, the tigers have to capture 5 goats in order to win. Can capture goats during any of the two phases. In each turn only one goat can be captured.

Can't jump over another tiger. Rules for goats Goats can't move until all goats have been placed on the board.

Can move to any adjacent free position in second phase. Can't jump over tigers or other goats. Credits: Animal Icons by Vecteezy.