Author Archives: kang & atul

Functional programming paradigm

Functional programming is based on Lambda Calculus, a computational model proposed by Alonzo Church in the 1930’s. This paradigm falls under the declarative umbrella rather than imperative, meaning, programming is done with expressions or declarations instead of statements. (Relax… See below the properties and you will understand what this means)

Note: We can do programming in a functional style in languages that are not specifically designed for functional programming. C++, Java, Python etc. all added constructs to facilitate the functional style. So, programmers using “mostly imperative” languages may have utilized some of the functional concepts.

Pros: more concise, more predictable, and easier to test than imperative or object-oriented code only if you understand.

Main Concepts of Functional Programming:

Pure Functions: A pure function is a function which follows given properties like

For the same input, it always returns the same output.
Has no side effects(For details check the link).
Referential Transparency.

Although, these properties are somehow correlated. Like, a function can only return the same output for the same input, only if it has no side effects. Let’s see by examples

def square(x):
    return x*x

1 2	def square(x): return x*x

The square function always gives the same output for the same x .

def random_num():
    return np.random.randn()

1 2	def random_num(): return np.random.randn()

Even though we didn’t pass any arguments to the random_num function, it gives different output, meaning that random_num is not pure.

Now, let’s look at the side effect property.
Side effect is any state(value of the variable) change outside the called function scope. In simple terms, if a function changes the state/value of the variable that is outside function scope or local environment then the function/unit of code is said to have a side effect.

x=3
def square(x):
    x=x*x
    return x
def square_side():
    global x
    x=x*x
    return x
print(x)                 # 3
print(square(x))         # 9
print(x)                 # 3 
print(square_side())     # 9
print(x)                 # 9

x=3

def square(x):

x=x*x

return x

def square_side():

global x

x=x*x

return x

print(x) # 3

print(square(x)) # 9

print(x) # 3

print(square_side()) # 9

print(x) # 9

Clearly, the x value changes after square_side() function which means that this function has side effects. The x in the square() function is local to its scope so no change in outside x. Global in square_side() makes x global so any change in x will change it in whole code (outside function scope) so the square_side function is not pure(has side effects).

Another important property of pure functions is Referential Transparency means we can replace a function call with its resulting value without changing the meaning of the program. Let’s see by an example

def double(x):
    return x*2
y = double(2) # or y = 4

def double(x):

return x*2

y = double(2) # or y = 4

In the above example, we can easily replace double(2) by 4 because we know that this function always gives the same result for the same input(No side effects). This is Referential Transparency.

First Class functions: “first-class” is a computer science term that describes something that has no restriction on its use. Thus, first-class functions mean it can appear anywhere in the program like as arguments to other functions and as their return values.
Recursion: Recursion means letting an operation be repeated until it reaches the base case. In the functional paradigm, we do not use the loops and all the work is done by recursion.

Python

def factorial(n): if n == 1: return n else: return n*factorial(n-1)

1
2
3
4
5

def factorial(n):
   if n == 1:
       return n
   else:
       return n*factorial(n-1)
Avoid Shared State: A shared state is a state that is shared between more than one function or more than one data structure and you should avoid creating functions that rely on the same variable.

Now, you might have got some feeling about the Functional programming. Hope you enjoy reading.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Procedural Programming paradigm

Leave a reply

Procedural programming, as the name suggests, is based on the concept of procedural call. To understand it more deeply, we should first know what procedural call means.

Procedures, also known as routines, subroutines, or functions, simply contain a series of computational steps to be carried out. Let’s see an example of the procedure

#Procedure
def add_list(my_list):
    Total = 0
    for x in my_list:
       Total += x  
    return Total        
# Procedure Call
add_list([1,2,3,4])

#Procedure

def add_list(my_list):

Total = 0

for x in my_list:

Total += x

return Total

# Procedure Call

add_list([1,2,3,4])

Procedure calls are modular and are bound by scope. It means we break the program into independent, interchangeable small pieces known as modules such that each module contains everything necessary to execute. Each module is composed of one or more procedures.

Procedural programs may possibly have multiple levels or scopes, with subprograms defined inside other subprograms. Scoping helps to keep the procedures modular and prevents/allows the procedure, from accessing the variables of other procedures.

Procedural programming falls under the imperative umbrella which means that procedural inherits the properties of the imperative paradigm. Procedural programming uses a linear or top-down approach.

Pros: easier to read and more maintainable, more flexible, allows modules to be used again in the form of code libraries.

Cons: this approach may not use hardware efficiently when tackling complex problems because of side effects (may not run parallelly)

In short, procedural programming means breaking the program into modules and using the imperative approach. If we take away the imperative nature from procedural, then it becomes same as Functional.

Now, you might have got some feeling about the Procedural programming. Hope you enjoy reading.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Imperative vs Declarative programming paradigm

Leave a reply

In this post, we will be looking at the major differences between imperative and declarative programming paradigms.

Imperative Programming paradigm: The languages that fall into this category have 2 main properties:

Control flow is explicit meaning how the operation took place, step by step or more naively “First do this then do that”.Thus, the order of steps is crucial.
Allow side effects.

To understand side effects, first, we should know what “state” is. In layman terms, the state refers to the value of the variable at any given point in the program like x=2.

Side effect is any state change outside the called function scope. In simple terms, if a function changes the state that is outside function scope or local environment then the function/unit of code is said to have a side effect.

Examples of function side effect include modifying any external variable or object property, performing I/O, calling functions having side effects etc.

Total = 0
Fare=[10,20,30,40]
for x in Fare:
    Total += x
mean_fare=Total/len(Fare)
print(mean_fare)

Total = 0

Fare=[10,20,30,40]

for x in Fare:

Total += x

mean_fare=Total/len(Fare)

print(mean_fare)

Let’s see how this code follows the properties of imperative paradigm. First, the order of steps is crucial because if we implement “mean_fare” statement before the loop, it will give a different result. Second, the unit of code i.e. loop, has side effects as it changes the state of the “Total” variable which is outside its scope.

I hope this might have given you the insight of the imperative programming paradigm.

Now, let’s look at some contradictions that I found while searching for this stuff

Some people might argue that the above code belongs to structured programming which is a kind of imperative programming. The main difference between these two is that in the imperative, control flow is defined by the collection of “goto” statements while in the structured, control flow is defined by nested loops, conditionals, and subroutines with no “goto” statements. okay that’s good I said, but then they categorized “Python” into imperative paradigm knowing that it doesn’t have “goto” statement.

So, what I found is that there are terms like structured and non-structured imperative programming. Above code falls into the structured imperative paradigm while if we use the goto statement to define control flow then it falls under the non-structured imperative paradigm.

Declarative Programming paradigm: This is defined as any style of programming that is not imperative. So, the properties will just be the opposite of imperative.

Sequence of the steps is not crucial.
Don’t allow Side effects.

In general, the imperative focuses on “how to do” while declarative focuses on “what to do”meaning logic of software without actually describing its flow. Let’s look at the code below to get more insights into this:

def Mean_list(lst):
    return sum(lst)/len(lst)

1 2	def Mean_list(lst): return sum(lst)/len(lst)

Using reduce() and lambda functions

from functools import reduce
def Mean_list(lst):
    return reduce(lambda a, b: a + b, lst) / len(lst)

from functools import reduce

def Mean_list(lst):

return reduce(lambda a, b: a + b, lst) / len(lst)

Note: Since python in no sense is declarative, the above examples are more towards functional side than declarative. But since functional also falls under the declarative umbrella, above examples can serve as a good platform for understanding declarative concepts.

Explanation: In the above examples, we are describing “WHAT” we want to do rather than HOW (we don’t know HOW lambda and reduce are implemented, we also don’t care). We’re not mutating any state. All of the mutations are abstracted inside of “lambda” and “reduce“. It’s also more readable (once you get used to “lambda” and “reduce“, of course).

Now, you might have got some feeling about the “How to do” and “What to do” approach. Later, this will become more clear when we will go through Functional and other paradigms. Till then, Enjoy.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Programming paradigms

1 Reply

In this posts series, we will be looking at the major programming paradigms and then, at last, we will see which paradigm does python follow.

Hi, have you ever wondered how many programming languages are there? Surfing through the net I found out that there are approx. 256 programming languages till now and still people are working. These languages may have their own pros based on code readability, efficiency or these may be good for different purposes.

But there is one similarity between these languages, that they follow some programming paradigm. We can classify these languages based on which programming paradigm they follow(although many people don’t agree as most of the languages include features from several paradigms so, difficult to classify).

A programming paradigm refers to the style of programming, meaning how you are building the structure and elements of the program. (ufff… Don’t panic from this innocent looking definition, for now just remember that this means some model with a set of rules/features ).There are several features that determine a programming paradigm such as modularity, objects, interrupts or events, control flow etc.

Everyone has an opinion on which programming paradigm/coding style is the best. Sometimes, a single style doesn’t truly solve the problem and you may have to combine different styles on the same problem.

The languages that follow a single paradigm are called “Pure” like Haskell while others are multi-paradigm like python, Java etc.

Common programming paradigms can be “roughly” categorized as:

Although this is not the right way to categorize paradigms. Only for understanding, these paradigms are grouped based on some similar properties. You can see the detailed classification given by Peter Van Roy.

In the next posts, we will look at these paradigms one by one. Till then, Enjoy.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Neural Arithmetic Logic Units

Leave a reply

In this tutorial, you will learn about neural arithmetic logic units (NALU).

You can see full TensorFlow implementation of neural arithmetic logic units in my GitHub Repository.

In Present time you can see neural network has wide application area from simple classification problem to complex self-driving cars problem. And neural network is doing very well in these fields. But can you think a neural network can’t count. Even animals as simple as bees can do that.

The problem is that a neural network can not perform numerical extrapolation outside training data. It will not be able to learn even a scalar identity function outside it’s training set. Recently DeepMind researchers released a paper in which they have generated a function which tries to solve this problem.

Failure Of Neural Network Learning a scalar identity function

The problem of neural nets not able to learn identity relations is not new. But in paper they tried to show this using an example.

They used an autoencoder of 3 layers each of 8 units and tried to predict identity relations. As an example if input is given as 4 then output should also be 4. They used different non-linear functions in this network like sigmoid and tanh but they all fail to extrapolate identity relation outside training data set.

They also saw that some highly linear function like PReLU are able to reduce the error but you can see even neural nets have function that are capable of extrapolation, they fail to do it.

To solve this problem they proposed two models:

NAC (Neural Accumulator)
NALU (Neural Arithmetic Logic Units)

NAC (Neural Accumulator)

Neural accumulator is able to solve problem of addition and subtraction.

NAC is a special case where transformation matrix W of a layer consists of [-1, 0,1]. This makes output from W as addition or subtraction of rows of input vector rather than arbitrary re scaling produced by non-linear functions. As an example if our input layer consists of X₁and X₂ then output from NAC will be linear combinations of input vectors. It will make numbers consistent throughout the model no matter haw many operations are applied there.

Since W is having hard constraints that every element of W should be one of {-1, 0, 1}. It makes learning difficult. The problem of difficult learning is that hard constraints creates difficulty in updating weights during back propagation. To solve this they proposed a continuous and differentiable parameterization of W.

W = tanh(w_hat) * sigmoid(m_hat)

1	W = tanh(w_hat) * sigmoid(m_hat)

w_hat and m_hat are randomly initialized weights and be convenient to learn with gradient descent. This guarantees that W will be in range of {-1, 1} and be close to {-1 , 0 ,1}. Here ” * ” means element-wise multiplication.

NALU (Neural Arithmetic Logic Units)

NAC is able to solve problem of addition/subtraction but also to solve problem of multiplication/division they came up with NALU which consists of two NAC sub cells, one capable of addition/subtraction and other for multiplication/division.

It consists of these five equations:

NAC: a = matmul(x, W), 
     W = tanh(w_hat) * sigmoid(m_hat)

NALU: y = g*a + (1-g)*m, 
      m = exp(matmul(W, log(|x|+ϵ)), 
      g = sigmoid(matmul(G, x)

NAC: a = matmul(x, W),

W = tanh(w_hat) * sigmoid(m_hat)

NALU: y = g*a + (1-g)*m,

m = exp(matmul(W, log(|x|+ϵ)),

g = sigmoid(matmul(G, x)

Where,

w_hat, m_hat and G and randomly initialized weights,
ϵ is used to get away with problem of log(0),
x and y are input and output layer respectively,
g is the gate which will be between 0 and 1.

Here the concept of gate is being added as variable ” g ” , such that if output value is applied with g = 1(on) then multiply/divide sub cell is 0 (off) and vice-versa.

For addition and subtraction (a = matmul(x, W) ), is identical to original NAC while for multiply/divide NAC operates in log space and capable of learning to multiply and divide (m = exp(matmul(W , log(|x|+ ϵ ) ) ).

So, this NALU is capable of both extrapolation and interpolation.

Experiments performed with NAC and NALU models

In paper they have also applied these concepts over different task to see ability of NAC and NALU. They found NALU to be very useful in different problems like:

Learning tasks using different arithmetic functions( x+y, x-y, x-y+x, x*y, etc)
Counting Task using recurrent network in which images of different digits are being fed to model and output should count no of each different type of digits.
Language to number translation task in which expression like ” five hundred fifteen ” is being fed to network and output should return ” 515 “. Here NALU is applied with a LSTM model in output layer.
NALU is also used with reinforcement learning to track time in a grid-world environment.

Summary

We have seen that NAC and NALU can be applied to overcome problem of failure of numerical representation to generalize outside the range observed in training data set. If you have gone through this blog, you have seen that this NAC and NALU concept is very easy to grasp and apply. However, it can not be said that NALU will be perfect for every task, so we have to see where it is giving good results.

Referenced Research Paper : Neural Arithmetic Logic Units

Neural Network Architecture Selection Using Genetic Algorithm

9 Replies

In the previous blog, I have discussed the genetic algorithm and one of its application in the neural network (Training a neural network with a genetic algorithm ). In this blog, I have used a genetic algorithm to solve the problem of neural network architecture search.

You can find full code here .

Genetic Algorithm is really helpful if you do not want to waste your time in using brute force trial and error method for selecting hyperparameters. To know more about the genetic algorithm you can read this blog.

In this tutorial, to demonstrate the use of genetic algorithm I have used Snake Game with Deep Learning where it’s been difficult to find out which neural network architecture will give us the best results. So, the genetic algorithm can be used to find out the best network architecture among the number of hyperparameters.

Different values of hyperparameters are used to create an initial population. I have used the following parameters in the genetic algorithm to find the best value for them.

Number of hidden Layers.
Units per hidden layer
Activation function
Network optimizer

def hyperparameters():
    parameters = []
    units_per_layer = [20,25,30,35,40]
    layers = [1, 2, 3, 4, 5,6,7]
    activation = ['relu', 'tanh', 'sigmoid']
    optimizer = ['adam', 'rmsprop']
    parameters.append(units_per_layer)
    parameters.append(layers)
    parameters.append(activation)
    parameters.append(optimizer)
    
    return parameters

def hyperparameters():

parameters = []

units_per_layer = [20,25,30,35,40]

layers = [1, 2, 3, 4, 5,6,7]

activation = ['relu', 'tanh', 'sigmoid']

optimizer = ['adam', 'rmsprop']

parameters.append(units_per_layer)

parameters.append(layers)

parameters.append(activation)

parameters.append(optimizer)

return parameters

Creating Initial Population

Random parameters are used to create the Initial population. For creating the population first, you have to decide population size. Each individual in the population will have four values.

I have taken 20 chromosomes in the population.

def generate_population(size):
    parameters = hyperparameters()
    
    population = []
    i=0   
    while i < size:
        chromosome = [random.choice(parameters[0]), random.choice(parameters[1]),
                    random.choice(parameters[2]), random.choice(parameters[3])]
        if chromosome not in population:
            population.append(chromosome)
            i+=1
    return population

def generate_population(size):

parameters = hyperparameters()

population = []

i=0

while i < size:

chromosome = [random.choice(parameters[0]), random.choice(parameters[1]),

random.choice(parameters[2]), random.choice(parameters[3])]

if chromosome not in population:

population.append(chromosome)

i+=1

return population

Fitness Function

Fitness function can vary as per the need of different genetic algorithms. Here, I have used the average score for different network architectures. Individuals with the highest average score are fittest ones.

Selection

After evaluating each individual in the population, I have selected top 5 fittest individuals from the population. And also selected 3 individuals from the non-top performers. This will keep us away from getting stuck in the local maximum.

Remaining 12 individuals are created from these 8 individuals using Crossover.

Crossover and Mutation

To produce better offspring for the next generation, I have selected two parents randomly from the 8 individuals selected above and generated other 12 individuals.

def children_population(size, population):
    
    child_population = []
    k = 0
    population_size = len(population)
    while k < size :
        i, j = random.sample(range(0, population_size), 2)
        parent1 = population[i]
        parent2 = population[j]
         
        child = new_child(parent1, parent2) 
        if child not in child_population and child not in population:
            child_population.append(child)
            k +=1
            
    for newest_child in child_population:
        population.append(newest_child)
        
    return population

def new_child(parent1, parent2):
    child = []
    parent_size = len(parent1)
    i=0
    while i<parent_size:
        child.append(random.choice([parent1[i],parent2[i]]))
        i += 1
    return child

def children_population(size, population):

child_population = []

k = 0

population_size = len(population)

while k < size :

i, j = random.sample(range(0, population_size), 2)

parent1 = population[i]

parent2 = population[j]

child = new_child(parent1, parent2)

if child not in child_population and child not in population:

child_population.append(child)

k +=1

for newest_child in child_population:

population.append(newest_child)

return population

def new_child(parent1, parent2):

child = []

parent_size = len(parent1)

i=0

while i<parent_size:

child.append(random.choice([parent1[i],parent2[i]]))

i += 1

return child

In certain new children formed, some of their genes can be subjected to a mutation with a low random probability. Mutation is required to maintain some amount of randomness in the genetic algorithm.

def mutation(population):
    parameters = hyperparameters()
    for chromosome in population:
        if random.random() < 0.1 :
            key = random.choice([0,1,2,3])
            parameters = hyperparameters()
            mutate_key = random.choice(parameters[key])
            chromosome[key] = mutate_key
    
    return population

def mutation(population):

parameters = hyperparameters()

for chromosome in population:

if random.random() < 0.1 :

key = random.choice([0,1,2,3])

parameters = hyperparameters()

mutate_key = random.choice(parameters[key])

chromosome[key] = mutate_key

return population

Now we have created all the necessary functions required for a genetic algorithm. Now, we define a model function using keras library. Then we will train this model with different hyperparameters and search for the best using genetic algorithm.

def train_model(parameters):
    units_per_layer = parameters[0]
    layers = parameters[1]
    activation = parameters[2]
    optimizer = parameters[3]

    model = Sequential()
    model.add(Dense(units=9,input_dim=9))

    for _ in range(layers):
        model.add(Dense(units=units_per_layer, activation=activation))
        
    model.add(Dense(units = 3,  activation = 'softmax'))
    return model

population_with_avg_score = []

for chromosome in population:
    model = train_model(chromosome)
    model.compile(loss='mean_squared_error', optimizer=chromosome[3], metrics=['accuracy'])
    model.fit((np.array(training_data_x).reshape(-1,9)),( np.array(training_data_y).reshape(-1,3)), batch_size = 256,epochs= 3)
    max_score, avg_score = run_game_with_ML(model,display,clock)
    chromosome.append(avg_score)
    chromosome.append(max_score)
    population_with_avg_score.append(chromosome)

def train_model(parameters):

units_per_layer = parameters[0]

layers = parameters[1]

activation = parameters[2]

optimizer = parameters[3]

model = Sequential()

model.add(Dense(units=9,input_dim=9))

for _ in range(layers):

model.add(Dense(units=units_per_layer, activation=activation))

model.add(Dense(units = 3, activation = 'softmax'))

return model

population_with_avg_score = []

for chromosome in population:

model = train_model(chromosome)

model.compile(loss='mean_squared_error', optimizer=chromosome[3], metrics=['accuracy'])

model.fit((np.array(training_data_x).reshape(-1,9)),( np.array(training_data_y).reshape(-1,3)), batch_size = 256,epochs= 3)

max_score, avg_score = run_game_with_ML(model,display,clock)

chromosome.append(avg_score)

chromosome.append(max_score)

population_with_avg_score.append(chromosome)

Here, I have used 10 generations and 20 individuals in the population. It can vary according to your need.

Now, you might have got some feeling about how the genetic algorithm can be applied to find neural architecture instead of using the brute-force method. Hope you enjoy reading.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Snake Game with Deep Learning

4 Replies

Developing a neural network to play a snake game usually consists of three steps.

Training data generation
Training neural network
Testing

The full code can be found here

In this tutorial, I will guide you to generate training data. To do this, first, we need to develop a snake game for which you can follow this blog.

Training data consists of inputs and corresponding outputs. Here, I have used the following inputs and outputs.

Input is comprised of 7 nodes:

Is left blocked or is there any obstacle in left ( 1 or 0)
is front blocked or is there any obstacle in front (1 or 0)
Is right blocked or is there any obstacle in right(1 or 0)
Apple direction vector from snake (X)
Apple direction vector from snake (Y)
Snake’s current direction vector (X)
Snake’s current direction vector (Y)

our input data will look like this:

The output is comprised of 3 node:

[1,0,0] will move snake left
[0,1,0] will continue snake in same direction
[0,0,1] will move snake right

Now the big question, how to generate this data? You can sit and play as many games as you can, but it is always good when you can generate data automatically. Let’s see how to do this.

Generating Training Data

Here I have generated training data automatically. To do this I have used angle between snake and apple. On the basis of that angle, I have decided in which direction snake should move. First, let’s calculate these.

Calculating angle b/w snake and apple:

To calculate the angle between snake and apple we only require two parameters, snake position and apple position.

In the following code, I have first calculated the snake’s current direction vector and Apple’s direction from the snake’s current position. Snake direction vector can be calculated by simply subtracting 0th index of the snake’s list from the 1st index. And to calculate apple direction from the snake, just subtract 0th index of snake’s list from Apple’s position.

Then normalize these direction vectors and calculate the angle with the help of the math library. The code is as follows:

def angle_with_apple(snake_position, apple_position):
    apple_direction_vector = np.array(apple_position)-np.array(snake_position[0])
    snake_direction_vector = np.array(snake_position[0])-np.array(snake_position[1])
    
    norm_of_apple_direction_vector = np.linalg.norm(apple_direction_vector)
    norm_of_snake_direction_vector = np.linalg.norm(snake_direction_vector)
    if norm_of_apple_direction_vector == 0:
        norm_of_apple_direction_vector = 10
    if norm_of_snake_direction_vector == 0:
        norm_of_snake_direction_vector = 10
        
    apple_direction_vector_normalized = apple_direction_vector/norm_of_apple_direction_vector
    snake_direction_vector_normalized = snake_direction_vector/norm_of_snake_direction_vector
    angle = math.atan2(apple_direction_vector_normalized[1] * snake_direction_vector_normalized[0] - apple_direction_vector_normalized[0] * snake_direction_vector_normalized[1], apple_direction_vector_normalized[1] * snake_direction_vector_normalized[1] + apple_direction_vector_normalized[0] * snake_direction_vector_normalized[0]) / math.pi
    return angle

def angle_with_apple(snake_position, apple_position):

apple_direction_vector = np.array(apple_position)-np.array(snake_position[0])

snake_direction_vector = np.array(snake_position[0])-np.array(snake_position[1])

norm_of_apple_direction_vector = np.linalg.norm(apple_direction_vector)

norm_of_snake_direction_vector = np.linalg.norm(snake_direction_vector)

if norm_of_apple_direction_vector == 0:

norm_of_apple_direction_vector = 10

if norm_of_snake_direction_vector == 0:

norm_of_snake_direction_vector = 10

apple_direction_vector_normalized = apple_direction_vector/norm_of_apple_direction_vector

snake_direction_vector_normalized = snake_direction_vector/norm_of_snake_direction_vector

angle = math.atan2(apple_direction_vector_normalized[1] * snake_direction_vector_normalized[0] - apple_direction_vector_normalized[0] * snake_direction_vector_normalized[1], apple_direction_vector_normalized[1] * snake_direction_vector_normalized[1] + apple_direction_vector_normalized[0] * snake_direction_vector_normalized[0]) / math.pi

return angle

After calculating the angle, next thing is to decide in which direction snake should move.

Calculating direction according to the angle:

If above-calculated angle > 0, this means Apple is on the right side of the snake. So snake should move to the right. For < 0, move left and =0 means continue in same direction. I have used 1, – 1 and 0 for the right, left and front respectively.

I have used the following steps to get the correct button direction (up, down, right, left or 3, 2, 1, 0 respectively) for the next step of the snake.

First, I have calculated the snake’s current direction.
Then to turn the snake to the left or right direction, I have calculated left direction vector or right direction vector from snake’s current direction vector.
Then I have converted the above-calculated direction vector into the button direction.

def generate_next_direction(snake_position, angle_with_apple):
    direction = 0
    
    if angle_with_apple > 0:
        direction = 1
    elif angle_with_apple < 0:
        direction = -1
    else:
        direction = 0
        
    current_direction_vector = np.array(snake_position[0])-np.array(snake_position[1])
    left_direction_vector = np.array([current_direction_vector[1],-current_direction_vector[0]])
    right_direction_vector = np.array([-current_direction_vector[1], current_direction_vector[0]])
    
    new_direction = current_direction_vector
    if direction == -1:
        new_direction = left_direction_vector
    if direction == 1:
        new_direction = right_direction_vector

    button_direction = generate_button_direction(new_direction)
    
    return direction, button_direction

def generate_button_direction(new_direction):
    button_direction = 0
    if new_direction.tolist() == [10,0]:
        button_direction = 1
    elif new_direction.tolist() == [-10,0]:
        button_direction = 0
    elif new_direction.tolist() == [0,10]:
        button_direction = 2
    else:
        button_direction = 3
        
    return button_direction

def generate_next_direction(snake_position, angle_with_apple):

direction = 0

if angle_with_apple > 0:

direction = 1

elif angle_with_apple < 0:

direction = -1

else:

direction = 0

current_direction_vector = np.array(snake_position[0])-np.array(snake_position[1])

left_direction_vector = np.array([current_direction_vector[1],-current_direction_vector[0]])

right_direction_vector = np.array([-current_direction_vector[1], current_direction_vector[0]])

new_direction = current_direction_vector

if direction == -1:

new_direction = left_direction_vector

if direction == 1:

new_direction = right_direction_vector

button_direction = generate_button_direction(new_direction)

return direction, button_direction

def generate_button_direction(new_direction):

button_direction = 0

if new_direction.tolist() == [10,0]:

button_direction = 1

elif new_direction.tolist() == [-10,0]:

button_direction = 0

elif new_direction.tolist() == [0,10]:

button_direction = 2

else:

button_direction = 3

return button_direction

Now, for every step, angle and corresponding next direction are calculated and snake moves according to that. And for each step inputs and outputs are calculated which are appended to a list of training data.To generate training data, we need to keep a record of 7 inputs and 3 outputs for every step the snake takes. First, let’s see how I have calculated the inputs for every step the snake takes.

To check if the direction is blocked, we look one step ahead in each direction.
Snake direction vector = Snake’s Head (0th index) – Snake’s 1st index
Apple direction from the snake = Apple’s position – Snake’s head position (See the figure below)

For every step, the output is generated by first calculating the direction for the given snake and apple position, using angle between them. Now, we need to convert our directions( -1, 0 or 1 ) to output(Y), a one hot vector. For every predicted direction we need to see that if that direction is blocked or not and according to that create output (Y) for training data. The code given below seems to be a bit longer but it calculates our training data output (Y).

def generate_training_data_y(snake_position, angle_with_apple, button_direction, direction, training_data_y, is_front_blocked, is_left_blocked ,is_right_blocked):
    if direction == -1:
        if is_left_blocked == 1:
            if is_front_blocked == 1 and is_right_blocked == 0:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, 1)
                training_data_y.append([0,0,1])
            elif is_front_blocked == 0 and is_right_blocked == 1:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, 0)
                training_data_y.append([0,1,0])
            elif is_front_blocked == 0 and is_right_blocked == 0:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, 1) 
                training_data_y.append([0,0,1])
             
        else:
            training_data_y.append([1,0,0])

    elif direction == 0:
        if is_front_blocked == 1:
            if is_left_blocked == 1 and is_right_blocked == 0:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, 1)
                training_data_y.append([0,0,1])
            elif is_left_blocked == 0 and is_right_blocked == 1:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, -1)
                training_data_y.append([1,0,0])
            elif is_left_blocked == 0 and is_right_blocked == 0:
                training_data_y.append([0,0,1])
                direction, button_direction = direction_vector(snake_position, angle_with_apple, 1)           
        else:
            training_data_y.append([0,1,0])
    else:
        if is_right_blocked == 1:
            if is_left_blocked == 1 and is_front_blocked == 0:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, 0)
                training_data_y.append([0,1,0])
            elif is_left_blocked == 0 and is_front_blocked == 1:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, -1)
                training_data_y.append([1,0,0])
            elif is_left_blocked == 0 and is_front_blocked == 0:
                direction, button_direction = direction_vector(snake_position, angle_with_apple, -1)
                training_data_y.append([1,0,0])               
        else:
            training_data_y.append([0,0,1])
    
    return direction, button_direction, training_data_y

def generate_training_data_y(snake_position, angle_with_apple, button_direction, direction, training_data_y, is_front_blocked, is_left_blocked ,is_right_blocked):

if direction == -1:

if is_left_blocked == 1:

if is_front_blocked == 1 and is_right_blocked == 0:

direction, button_direction = direction_vector(snake_position, angle_with_apple, 1)

training_data_y.append([0,0,1])

elif is_front_blocked == 0 and is_right_blocked == 1:

direction, button_direction = direction_vector(snake_position, angle_with_apple, 0)

training_data_y.append([0,1,0])

elif is_front_blocked == 0 and is_right_blocked == 0:

direction, button_direction = direction_vector(snake_position, angle_with_apple, 1)

training_data_y.append([0,0,1])

else:

training_data_y.append([1,0,0])

elif direction == 0:

if is_front_blocked == 1:

if is_left_blocked == 1 and is_right_blocked == 0:

direction, button_direction = direction_vector(snake_position, angle_with_apple, 1)

training_data_y.append([0,0,1])

elif is_left_blocked == 0 and is_right_blocked == 1:

direction, button_direction = direction_vector(snake_position, angle_with_apple, -1)

training_data_y.append([1,0,0])

elif is_left_blocked == 0 and is_right_blocked == 0:

training_data_y.append([0,0,1])

direction, button_direction = direction_vector(snake_position, angle_with_apple, 1)

else:

training_data_y.append([0,1,0])

else:

if is_right_blocked == 1:

if is_left_blocked == 1 and is_front_blocked == 0:

direction, button_direction = direction_vector(snake_position, angle_with_apple, 0)

training_data_y.append([0,1,0])

elif is_left_blocked == 0 and is_front_blocked == 1:

direction, button_direction = direction_vector(snake_position, angle_with_apple, -1)

training_data_y.append([1,0,0])

elif is_left_blocked == 0 and is_front_blocked == 0:

direction, button_direction = direction_vector(snake_position, angle_with_apple, -1)

training_data_y.append([1,0,0])

else:

training_data_y.append([0,0,1])

return direction, button_direction, training_data_y

Here, I have used 1000 games for generating training data, each of which consists of 2000 steps. For every game, I have re-initialized snake position, apple position, and score. Then, created two empty lists, one for input training data(X) and another output training data(Y), those will contain our whole training data.The code is as follows:

def generate_training_data(display,clock):
    
    training_data_x = []
    training_data_y = []
    training_games = 1000
    steps_per_game = 2000
    
    for _ in tqdm(range(training_games)):
        snake_start, snake_position, apple_position, score = starting_positions()
        prev_apple_distance = apple_distance_from_snake(apple_position, snake_position)
        
        for _ in range(steps_per_game):
            angle, snake_direction_vector, apple_direction_vector_normalized, snake_direction_vector_normalized = angle_with_apple(snake_position, apple_position)
            direction, button_direction = generate_random_direction(snake_position, angle)
            current_direction_vector, is_front_blocked, is_left_blocked ,is_right_blocked = blocked_directions(snake_position)
            
            direction, button_direction, training_data_y = generate_training_data_y(snake_position, angle_with_apple, button_direction, direction, training_data_y, is_front_blocked, is_left_blocked ,is_right_blocked)
            
            if is_front_blocked == 1 and is_left_blocked == 1 and is_right_blocked == 1:
                break

            training_data_x.append([is_left_blocked, is_front_blocked, is_right_blocked,apple_direction_vector_normalized[0], \
                        snake_direction_vector_normalized[0], apple_direction_vector_normalized[1], \
                        snake_direction_vector_normalized[1]])
            
            
            
            
            snake_position, apple_position, score = play_game(snake_start, snake_position, apple_position, button_direction, score,display,clock)   

    return training_data_x, training_data_y

def generate_training_data(display,clock):

training_data_x = []

training_data_y = []

training_games = 1000

steps_per_game = 2000

for _ in tqdm(range(training_games)):

snake_start, snake_position, apple_position, score = starting_positions()

prev_apple_distance = apple_distance_from_snake(apple_position, snake_position)

for _ in range(steps_per_game):

angle, snake_direction_vector, apple_direction_vector_normalized, snake_direction_vector_normalized = angle_with_apple(snake_position, apple_position)

direction, button_direction = generate_random_direction(snake_position, angle)

current_direction_vector, is_front_blocked, is_left_blocked ,is_right_blocked = blocked_directions(snake_position)

direction, button_direction, training_data_y = generate_training_data_y(snake_position, angle_with_apple, button_direction, direction, training_data_y, is_front_blocked, is_left_blocked ,is_right_blocked)

if is_front_blocked == 1 and is_left_blocked == 1 and is_right_blocked == 1:

break

training_data_x.append([is_left_blocked, is_front_blocked, is_right_blocked,apple_direction_vector_normalized[0], \

snake_direction_vector_normalized[0], apple_direction_vector_normalized[1], \

snake_direction_vector_normalized[1]])

snake_position, apple_position, score = play_game(snake_start, snake_position, apple_position, button_direction, score,display,clock)

return training_data_x, training_data_y

You might have got some feeling about the training data generation for the snake game with deep learning. In the next blog, we will use this data to train and test our neural network. Hope you enjoy reading.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Snake Game with Deep Learning Part-2

2 Replies

This is the second part of the snake game with deep learning series. In my previous blog, we have seen that how to generate training data for the neural network. In this tutorial, we will see training and testing of the neural network from generated training data.

The full code can be found here.

Our neural network is comprised of 7 nodes in the input layer, 3 node in the final layer and some hidden layers.

Network Architecture:

Now, it’s time to choose hidden layers and corresponding hyperparameters. Its always been difficult to find the perfect neural network architecture. There are some algorithms that can help to find the best network architecture for a neural network like a genetic algorithm, NAS, autoML etc. I have explained neural architecture search using the genetic algorithm in this blog.

In this blog, I have used hit and trial method to find network architecture. After some hit and trials, I have found a workable architecture, which consists of 2 hidden layers one of 9 units and other of 15 units. For the hidden layer, I have used the non-linear function ‘relu’ and for the output layer, I have used ‘softmax’.

You can use different libraries to train this model like keras, tflearn, etc. Here I have used keras. Our network architecture is as follows:

model = Sequential()
model.add(Dense(units=9,input_dim=7))

model.add(Dense(units=15, activation='relu'))
model.add(Dense(output_dim=3,  activation = 'softmax'))

model = Sequential()

model.add(Dense(units=9,input_dim=7))

model.add(Dense(units=15, activation='relu'))

model.add(Dense(output_dim=3, activation = 'softmax'))

Train Neural Network

Our model is prepared, now it’s time to train this. For training, we first need to compile this model then call a method model.fit() which will do the rest. Since our training data is a list, we first need to change it into numpy array and then reshape it. The reason for this is, a sequential model from keras expects numpy array or sparse matrix of shape [n_samples,n_features].

model.compile(loss='mean_squared_error', optimizer='adam', metrics=['accuracy'])
model.fit((np.array(training_data_x).reshape(-1,7)),( np.array(training_data_y).reshape(-1,3)), batch_size = 256,epochs= 3)

1 2	model.compile(loss='mean_squared_error', optimizer='adam', metrics=['accuracy']) model.fit((np.array(training_data_x).reshape(-1,7)),( np.array(training_data_y).reshape(-1,3)), batch_size = 256,epochs= 3)

Now, our model is trained with generated training data. Next thing is to test it and see how much is learned.

Test Snake Game

Now it’s time to test our trained snake. To predict the direction we have fed our model with input values. Then used the predicted direction(Left, Straight or Front) to take the next step in our test games. For the new position, again predict the direction and move the snake. This continues until the snake dies or steps are over.

At last, we have calculated the maximum and average score for all the games in our test set.

def run_game_with_ML(model,display,clock):
    max_score = 3
    avg_score = 0
    test_games = 1000
    steps_per_game = 2000
    
    for _ in range(test_games):
        snake_start, snake_position, apple_position, score = starting_positions()
        
        count_same_direction = 0
        prev_direction = 0

        for _ in range(steps_per_game):
            current_direction_vector, is_front_blocked, is_left_blocked ,is_right_blocked = blocked_directions(snake_position)
            angle, snake_direction_vector, apple_direction_vector_normalized, snake_direction_vector_normalized = angle_with_apple(snake_position, apple_position)
            predictions = []

            predicted_direction = np.argmax(np.array(model.predict(np.array([is_left_blocked, is_front_blocked, \
                                    is_right_blocked,apple_direction_vector_normalized[0], \
                                    snake_direction_vector_normalized[0], apple_direction_vector_normalized[1], \
                                            snake_direction_vector_normalized[1]]).reshape(-1,7))))-1
            
            
            if predicted_direction == prev_direction:
                count_same_direction+=1
            else:
                count_same_direction = 0
                prev_direction = predicted_direction
            
            new_direction = np.array(snake_position[0]) - np.array(snake_position[1])
            if predicted_direction == -1:
                new_direction = np.array([new_direction[1],-new_direction[0]])
            if predicted_direction == 1:
                new_direction = np.array([-new_direction[1],new_direction[0]])
            
            button_direction = generate_button_direction(new_direction)
            
            next_step = snake_position[0]+ current_direction_vector
            if collision_with_boundaries(snake_position[0]) == 1 or collision_with_self(next_step.tolist(), snake_position) == 1:
                break
            snake_position, apple_position, score = play_game(snake_start, snake_position, apple_position, button_direction, score,display,clock)  
            
                                         
            if score > max_score:
                max_score = score
                
        avg_score += score
       
    return max_score, avg_score/1000

def run_game_with_ML(model,display,clock):

max_score = 3

avg_score = 0

test_games = 1000

steps_per_game = 2000

for _ in range(test_games):

snake_start, snake_position, apple_position, score = starting_positions()

count_same_direction = 0

prev_direction = 0

for _ in range(steps_per_game):

current_direction_vector, is_front_blocked, is_left_blocked ,is_right_blocked = blocked_directions(snake_position)

angle, snake_direction_vector, apple_direction_vector_normalized, snake_direction_vector_normalized = angle_with_apple(snake_position, apple_position)

predictions = []

predicted_direction = np.argmax(np.array(model.predict(np.array([is_left_blocked, is_front_blocked, \

is_right_blocked,apple_direction_vector_normalized[0], \

snake_direction_vector_normalized[0], apple_direction_vector_normalized[1], \

snake_direction_vector_normalized[1]]).reshape(-1,7))))-1

if predicted_direction == prev_direction:

count_same_direction+=1

else:

count_same_direction = 0

prev_direction = predicted_direction

new_direction = np.array(snake_position[0]) - np.array(snake_position[1])

if predicted_direction == -1:

new_direction = np.array([new_direction[1],-new_direction[0]])

if predicted_direction == 1:

new_direction = np.array([-new_direction[1],new_direction[0]])

button_direction = generate_button_direction(new_direction)

next_step = snake_position[0]+ current_direction_vector

if collision_with_boundaries(snake_position[0]) == 1 or collision_with_self(next_step.tolist(), snake_position) == 1:

break

snake_position, apple_position, score = play_game(snake_start, snake_position, apple_position, button_direction, score,display,clock)

if score > max_score:

max_score = score

avg_score += score

return max_score, avg_score/1000

Now let see how neural network plays snake game.

Summary

I have used 1000 training games and 2000 steps per game. From this, I have generated 1633235 training examples. Then I have tested it on 1000 games and 2000 steps per game. Got the highest score of 61 and got an average score of 23.091. This score can vary since we are using random positions for food and also no of steps are fixed. You can also vary your clock speed as per your need.
You can try with the different number of games but then you have to change your network architecture in order to prevent the model from biasing and overfitting.

Now you might have got some feeling about how neural network plays a snake game. In the next blog, we will use a neural network trained with a genetic algorithm to play snake game. Hope you enjoy reading.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Download Data from Kaggle

Leave a reply

In this tutorial, I will guide you to download kaggle dataset from your python notebook directly or from your command shell(to download from command shell remove the exclamation mark(!) from start). Here are the necessary steps to follow:

Sign in to your kaggle account and enter into the competition by accepting its rules for which you need data to be downloaded.
Firstly, install kaggle cli using pip by writing following command into python notebook:
!pip install kaggle-cli
If you get any error while executing the previous step try the following command instead:
!pip install kaggle-cli –upgrade
Then configure your kaggle account with your username, password and competition name from which data to be downloaded. Your username and password should be inside inverted comma. The command is as follows:
!kg config -u ‘username’ -p ‘password’ -c competitonName
competition name for downloading dataset can be extracted from competition’s URL e.g if competition’s URL is https://www.kaggle.com/c/imagenet-object-detection-challenge then competition name would be imagenet-object-detection-challenge.
And finally, write following command to download data:
!kg download
Then you can extract dataset into the particular folder by using the following command:
!unzip –q filename.zip -d folderName
You can also download particular data file from kaggle using following command:
!kg download -u ‘username’ -p ‘password’ -c competitonName -f fileName

Enjoy!!!

TheAILearner

Mastering Artificial Intelligence

Author Archives: kang & atul

Functional programming paradigm

Procedural Programming paradigm

Imperative vs Declarative programming paradigm

Like this:

Programming paradigms

Like this:

Neural Arithmetic Logic Units

Neural Network Architecture Selection Using Genetic Algorithm

Creating Initial Population

Fitness Function

Selection

Crossover and Mutation

Snake Game with Deep Learning

Generating Training Data

Like this:

Snake Game with Deep Learning Part-2

Test Snake Game

Summary

Like this:

Download Data from Kaggle

Like this: