Is my single layer perceptron getting biased input some way or the other?

Question

I was working a little bit on a school project my team and I decided to do for submission in the year-end. It's a small game which I call 'Quattro', and its rules are as follows:

1. The game is played on an 8 x 8 square grid and each player (both the human and the computer) have sixteen pieces on their side (just the same layout as in chess, but here all pieces are identical for each player).
2. Only vertical moves,(i.e., one can move only one square forward at a time and that too in the forward direction/along a column) as long as no other piece stands before the piece to be moved.
3. However, one can cross over to a square present in the north-west or north-east (when you look around a 3 x 3 grid with the piece under consideration at the centre) if the north and west/east boundary of the piece when in the 3 x 3 grid are held by the enemy's pieces, as in the case of the move 'en passant' in chess. In the process, the enemy piece in the square just below the square the player has crossed over to is lost by the enemy.
4. The players involved can either be an attacker or a defender (if one choses the former, the other takes the latter). The attacker wins if he/she successfully takes at least four of his/her pieces(hence the name Quattro) to the enemy's side (that is, to the last row counting from that player's side) while the defender wins if the attacker is prevented from doing so.

You can request me to add screenshots in case the rules are very vague (even my teammates were confused 😅).

Okay, so I'm doing this on Python 3.9.6 and I have somehow made the board layout and movement rules (except for rule 2 and rule 4, which are supposed to be added once the primary workings of the game is completed). I had somehow made the AI player (which is based on a single-layer perceptron), but I doubt if it is working right or not. The problem is that when I make a random move, the AI player starts always at the same column and moves pieces in some order I can't clearly remember(in the primary stage of creation, it all seemed to work fine, but as time progressed, I began to see indexing errors so I tried to adjust things somehow) and then it wanders off into an infinite loop. From a debug message I set up to observe the change in weights, I saw that at times one weight it growing while the other few would either be shrinking or remaining constant. As of now, I set up a variable to give the model a random target value (or may not be random, it seems) to train with and still the problem continues. I doubt if the input data is biased someway or the other. Here's how the input is taken:

1. The model first checks through each column, and the input corresponding to each column will be a vector containing 0's and 1's with the 1's indicating the enemy's presence and 0 for the else case. The model thus generates a 'preference score' (equivalent to the activation function of the sum of the weighted inputs, as how it is in any other perceptron).
2. The same is done for rows as well and the list of values in both cases are passed to a dictionary, from which the player choses the row and column index with the highest scores and moves the piece there.

I also set up an InvalidMove exception so as to make sure that the machine doesn't play blankly.

So here's the code:

• MarchOfTheFinalFour.py - the module containing the required exception and the board.

# MarchOfThFinalFour.py

from time import *

# 'March of The Final Four' - a clone of chess

player_piece = 'Φ' # player's piece
computer_piece = 'τ' # computer's piece

class InvalidMove(Exception):
    '''error when you/ the computer takes an invalid move'''
    def __init__(self, coords):
        self.stmt = "invalid move from:"
        self.coords = coords

class PlayTable:
    def __init__(self, table_side):
        ''' generates the game board, empty and with no pieces '''
        self.length = table_side
        self.table = [[0]*table_side]*table_side

    def __repr__(self):
        '''prints the table'''
        print()
        table_str = ''
        num = 0
        for row in self.table:
            table_str += str(num) + " \t"
            for piece in row:
                table_str += str(piece) + "|"
            table_str += "\n"
            num += 1
        return table_str + "\t0 1 2 3 4 5 6 7"
        
    def reset(self):
        ''' resets the board/ places pieces on it '''
        for row in [0, 1] :
            self.table[row] = [computer_piece]*self.length

        for row in [self.length-2, self.length - 1] :
            self.table[row] = [player_piece]*self.length
        
        for row in range(2, self.length-2):
            self.table[row] = [0]*self.length
    def move_piece(self, coord, turn = 'player'):
        '''moves the piece at coord '''
        if self.table[coord[1]%self.length][coord[0]%self.length] != 0 and self.table[(coord[1] + (1 if turn == 'computer' else -1))%self.length][coord[0]%self.length] == 0:
            temp = self.table[coord[1]][coord[0]]
            self.table[coord[1]][coord[0]] = 0
            direction = 1 if turn == 'computer' else -1
            self.table[coord[1]+direction][coord[0]] = temp
            print(f"Moved {temp} from {(coord[0] if coord[0] >= 0 else 8 + coord[0],coord[1] if coord[1] >= 0 else 8 + coord[1])}") # msg
        elif self.table[coord[1]%self.length][coord[0%self.length]] == 0 or self.table[(coord[1] + (-1)**(1 if turn == 'player' else 1))%self.length][coord[0]%self.length] != 0:
            raise InvalidMove(coord)
        elif turn == 'player' and self.table[coord[1]%self.length][coord[0]%self.length] == computer_piece:
            raise InvalidMove(coord)
        elif turn == 'computer' and self.table[coord[1]%self.length][coord[0]%self.length] == player_piece:
            raise InvalidMove(coord)
        
        
board = PlayTable(8)
board.reset()
print(board)

• TestGameML.py - sample game, NPC, single-layer perceptron, etc. all lies here:

from math import *
from random import *
import MarchOfTheFinalFour as mff

######################

## Math functions for our use in here
    
def multiply(list_a, list_b):
    '''matrix multiplication and addition'''
    list_res = [list_a[n] * list_b[n] for n in range(len(list_a))]
    return fsum(list_res)

def sig(x):
    '''logistic sigmoid function'''
    return exp(x)/(1+ exp(x))

##############################

## Neighbourhood search

def neighbourhood(coords, board_length):
    '''generates the 3 x 3 grid that forms the neighbourhod of the required square'''
    axial_neighbours =  [(coords[0] + 1, coords[1]),(coords[0] - 1, coords[1]),
                        (coords[0], coords[1] + 1), (coords[0], coords[1] - 1)] # neighbours along NEWS directins
    diagonal_neighbours = [(coords[0] + 1, coords[1]+1),(coords[0] - 1, coords[1] - 1),
                           (coords[0]-1, coords[1] + 1), (coords[0]+1, coords[1] - 1)] #diagonal neighbours
    neighbours = axial_neighbours + diagonal_neighbours # supposed neighbours
    ## purging those coordinates with negative values in them:
    for i in range(len(neighbours)):
        if (neighbours[i][0] < 0 or neighbours[i][0] > board_length - 1) or (neighbours[i][1] < 0 or neighbours[i][1] > board_length - 1):
            neighbours[i] = 0
    while 0 in neighbours:
        neighbours.remove(0)
    
    return neighbours

########################

# The NPC's brain

class NPC_Brain:
    '''brain of the NPC ;), actually a single-layer perceptron '''
    def __init__(self,board_size):
        ''' Initialiser'''
        self.inputs = board_size # no. of input nodes for the neural network
        self.weights = [random() for i in range(self.inputs)] # random weights for each game
        self.column_scores = [] # column scores (for each column) - the 'liking' of the computer to move a piece in a column as the output
                                # of the neural network's processing
        self.row_scores = [] #same here
        self.inputs_template_columns = [] # a container to hold the inputs to the neural network
        self.inputs_template_rows = [] # same here but for rows
    def process(self, board, threshold):
        '''forward-feeding'''
        # we begin by setting the lists to zero so as to make the computer forget the past state of the board and to look for the current state
        self.inputs_template_columns = []
        self.inputs_template_rows = []
        self.column_scores = []
        self.row_scores = []
        self.row_scores = []
        for column in range(self.inputs):
            scores = [1 if row[column] == mff.computer_piece else 0 for row in board] # checking for enemies in each column
            self.inputs_template_columns.append(scores) 
            score = sig(multiply(scores, self.weights)/threshold) # using the logistic sigmoid function to generate a liking for columns :D
            self.column_scores.append(score) # each column score is appended
        for row in range(self.inputs):
            scores = [1 if board[row][i] == mff.player_piece else 0 for i in range(self.inputs)] # checking for enemies in each column
            self.inputs_template_rows.append(scores) 
            score = sig(multiply(scores, self.weights)/threshold) # using the logistic sigmoid function to generate a liking for columns :D
            self.row_scores.append(score) # each column score is appended
        return {'columns':self.column_scores, 'rows':self.row_scores}
    def back_prop(self, learning_rate, target = 1):
        '''Back-propagation, with error function as squared-error function (target - error)**2'''
        for j in range(len(self.inputs_template_columns)):
            for i in range(self.inputs):
                '''overfitting can occur, but still let's try this'''
                self.weights[i] +=  learning_rate * 2 * (self.column_scores[j] - target) * (self.column_scores[j]*(1-self.column_scores[j])) * self.inputs_template_columns[j][i] #backprop formula
        for k in range(len(self.inputs_template_rows)):
            for i in range(self.inputs):
                '''overfitting can occur, but still let's try this'''
                self.weights[i] += learning_rate * 2 * (self.row_scores[k] - target) * (self.row_scores[k]*(1-self.row_scores[k])) * self.inputs_template_rows[k][i] #backprop formula
                
    
        

class NPC:
    ''' non-playable character / computerized player class '''
    def __init__(self):
        self.mind = NPC_Brain(mff.board.length) # the model
        self.piece_lower = 0; self.piece_upper = 1 # initial row numbers of the computer's pieces
        self.row_expanse = 2
        
    def make_move(self):
        moved = False
        req_target = 0.5
        counter = 1
        while not moved:
            if counter % 50 == 0:
                req_target += log(req_target**(counter%25))
                print("New target set:", req_target)
            score_board = temp = self.mind.process(mff.board.table, 0.5) # feeding forward
            x_coord = score_board['columns'].index(max(score_board['columns'])) # choosing the column the compute likes the most
            y_coord = score_board['rows'].index(max(score_board['rows'])) % self.row_expanse # a random y coordinate is chosen
            try:
                if y_coord < mff.board.length - 1: 
                    if mff.board.table[int(y_coord) + 1][int(x_coord)] == 0 and (mff.board.table[int(y_coord)][int(x_coord)] not in  [0, mff.player_piece]):
                        mff.board.move_piece((int(x_coord), int(y_coord)), turn = 'computer')
                        self.piece_upper += 1 #increasing the upper limit of the y coordinate by 1
                        moved = True
                        req_target += 0.0001
                        self.row_expanse += 1
                        counter += 1
                    else:
                        raise mff.InvalidMove((x_coord,y_coord))
                    counter += 1 
            except mff.InvalidMove:
                # trying to avoid the computer's confusion
                self.mind.back_prop(1/pi, target = req_target) # making the computer learn from its decision
                req_target -= 0.0001
                counter += 1
                    
            
                
            
                


npc = NPC() # creating the NPC

## Sample gamplay
## The following gameplay will be a bit smooth in the beginning but turns into a confusion later
all_gone_good = True
while True:
    all_gone_good = True 
    # infinite loop here till errors occur
    player_mv = eval(input("Enter your move:")) # waiting for the player's move
    try:
        mff.board.move_piece(player_mv)
    except mff.InvalidMove:
        print("Invalid move")
        all_gone_good = False
    # next we check if the player's move was valid
    if all_gone_good:
        print(mff.board)
        npc.make_move()
        print(mff.board)
        

I am sorry that haven't been able to comment in certain regions of the code, in which case you can ask me for clarification.

My main doubts are : is my data acquisition method biased? Is the training part also little bit wacky? Or is it that I programmed it all without knowing what I am doing? What's actually causing such an infinite loop?

---

Edit: : I have edited TestGameML.py and it's down here:

from math import *
from random import *
import MarchOfTheFinalFour as mff

######################
##Bug fixes required:

##1. The machine is making multiple moves unknowingly

######################

## Some variables for global use

my_move = (0,0)

## Math functions for our use in here
    
def multiply(list_a, list_b):
    '''matrix multiplication and addition'''
    list_res = [list_a[n] * list_b[n] for n in range(len(list_a))]
    return fsum(list_res)

def sig(x):
    '''logistic sigmoid function'''
    return exp(x)/(1+ exp(x))

##############################

## Neighbourhood search

def neighbourhood(coords, board_length):
    '''generates the 3 x 3 grid that forms the neighbourhod of the required square'''
    axial_neighbours =  [(coords[0] + 1, coords[1]),(coords[0] - 1, coords[1]),
                        (coords[0], coords[1] + 1), (coords[0], coords[1] - 1)] # neighbours along NEWS directins
    diagonal_neighbours = [(coords[0] + 1, coords[1]+1),(coords[0] - 1, coords[1] - 1),
                           (coords[0]-1, coords[1] + 1), (coords[0]+1, coords[1] - 1)] #diagonal neighbours
    neighbours = axial_neighbours + diagonal_neighbours # supposed neighbours
    ## purging those coordinates with negative values in them:
    for i in range(len(neighbours)):
        if (neighbours[i][0] < 0 or neighbours[i][0] > board_length - 1) or (neighbours[i][1] < 0 or neighbours[i][1] > board_length - 1):
            neighbours[i] = 0
    while 0 in neighbours:
        neighbours.remove(0)
    
    return neighbours

########################
# The NPC's brain

class NPC_Brain:
    '''brain of the NPC ;), actually a single-layer perceptron '''
    def __init__(self,board_size):
        ''' Initialiser'''
        self.inputs = board_size # no. of input nodes for the neural network
        #self.weights = [random() for i in range(self.inputs)] random weights for each game
        self.weights = [0.5]*self.inputs
        self.column_scores = [] # column scores (for each column) - the 'liking' of the computer to move a piece in a column as the output
                                # of the neural network's processing
        self.row_scores = [] #same here
        self.inputs_template_columns = [] # a container to hold the inputs to the neural network
        self.inputs_template_rows = [] # same here but for rows
        
    def process(self, board, threshold):
        '''forward-feeding'''
        # we begin by setting the lists to zero so as to make the computer forget the past state of the board and to look for the current state
        self.inputs_template_columns = []
        self.inputs_template_rows = []
        self.column_scores = []
        self.row_scores = []
        for column in range(self.inputs):
            scores = [(1/8)**(row + 1 if row == my_move[1] else 1) if board[row][column] == mff.player_piece else -1/8 for row in range(self.inputs)] # checking for enemies in each column
            self.inputs_template_columns.append(scores) 
            score = sig(multiply(scores, self.weights)/threshold) # using the logistic sigmoid function to generate a liking for columns :D
            self.column_scores.append(score) # each column score is appended
        for row in range(self.inputs):
            scores = [(1/8)**(i + 1 if i == my_move[0] else 1) if board[row][i] == mff.player_piece else -1/8 for i in range(self.inputs)] # checking for enemies in each column
            self.inputs_template_rows.append(scores) 
            score = sig(multiply(scores, self.weights)/threshold) # using the logistic sigmoid function to generate a liking for columns :D
            self.row_scores.append(score) # each column score is appended
        return {'columns':self.column_scores, 'rows':self.row_scores}
    
    def back_prop(self, learning_rate, target = 1):
        '''Back-propagation, with error function as squared-error function (target - error)**2'''
        for j in range(len(self.inputs_template_columns)):
            for i in range(self.inputs):
                '''overfitting can occur, but still let's try this'''
                self.weights[i] +=  -learning_rate * 2 * (self.column_scores[j] - target) * ((self.column_scores[j]**2)*(1-self.column_scores[j])) * self.inputs_template_columns[j][i] #backprop formula
        for k in range(len(self.inputs_template_rows)):
            for i in range(self.inputs):
                '''overfitting can occur, but still let's try this'''
                self.weights[i] += -learning_rate * 2 * (self.row_scores[k] - target) * ((self.row_scores[k]**2)*(1-self.row_scores[k])) * self.inputs_template_rows[k][i] #backprop formula
                
    
        

class NPC:
    ''' non-playable character / computerized player class '''
    def __init__(self):
        self.mind = NPC_Brain(mff.board.length) # the model
        self.piece_lower = 0; self.piece_upper = 1 # initial row numbers of the computer's pieces
        self.row_expanse = 2
        
    def make_move(self):
        moved = False
        req_target = 0.5
        counter = 1
        print("Thinking...")
        while not moved:
            score_board = temp = self.mind.process(mff.board.table, 0.5) # feeding forward
            x_coord = score_board['columns'].index(min(score_board['columns'])) # choosing the column the compute likes the most
            y_coord = score_board['rows'].index(max(score_board['rows'])) % self.row_expanse # a random y coordinate is chosen
            try:
                if y_coord < mff.board.length - 1: 
                    if mff.board.table[int(y_coord) + 1][int(x_coord)] == 0 and (mff.board.table[int(y_coord)][int(x_coord)] not in  [0, mff.player_piece]):
                        mff.board.move_piece((int(x_coord), int(y_coord)), turn = 'computer')
                        self.piece_upper += 1 #increasing the upper limit of the y coordinate by 1
                        moved = True
                        self.row_expanse += 1
                        counter += 1
                    else:
                        raise mff.InvalidMove((x_coord,y_coord))
                    counter += 1 
            except mff.InvalidMove:
                # trying to avoid the computer's confusion
                self.mind.back_prop(0.5, target = req_target) # making the computer learn from its decision
                counter += 1
                    
            
                
            
                


npc = NPC() # creating the NPC

## Sample gamplay
## The following gameplay will be a bit smooth in the beginning but turns into a confusion later
all_gone_good = True
while True:
    all_gone_good = True 
    # infinite loop here till errors occur
    player_mv = eval(input("Enter your move:")) # waiting for the player's move
    try:
        mff.board.move_piece(player_mv)
    except mff.InvalidMove:
        print("Invalid move")
        all_gone_good = False
    # next we check if the player's move was valid
    if all_gone_good:
        my_move = player_mv
        print(mff.board)
        npc.make_move()
        print(mff.board)

Changelog:

• Change data distribution method in lines 71 and 76
• Asked NPC to choose the column with the least column score and max row score.

Answer 1

The direct reason that your AI always moves the top-left piece first (assuming the computer pieces take up the bottom 2 rows) is the way your model interacts with the environment.

Because you score every column separately, identical columns will always have identical scores. The way that you pick the best score means that if several columns have the same score, you will pick the left one, and if several rows have the same score, you will pick the top one. At the start of the game, since all the column scores are forced to be the same, that means it will always pick the first column. And since the AI pieces are in two rows, and those two rows are the same, and therefore must have the same scores, that means it will always pick the first row.

(Note: I didn't actually run your code so my understanding could be slightly different from what actually happens, like if the AI is at the top of the screen or if the game starts with the player moving first. The same principles should still apply)

---

Additionally, I don't think this is a good way to have the AI model interact with the environment. Imagine you are playing with your friends Billy and Sally. Every time you want to make a move, you print out two copies of the game board, cut one up into rows and give the rows to Billy, cut one up into columns and give the columns to Sally. Then you ask Billy to pick his favourite column and Sally to pick her favourite row and if there isn't a valid piece to move in that row and column, you slap them both.

At best, they're just going to learn to try not to get slapped. Probably by liking the rows and columns with the most pieces in them, which gives them the greatest chance that there is a piece at the location the other one picks.

And it's even worse because Billy and Sally are the same person and they don't know which cutouts are rows and which cutouts are columns.

This is clearly not a good way to play.

---

Your board game falls into the same category as Chess, Go and Tic-Tac-Toe - it has a game board with a finite (but large) number of states, a finite number of moves that the player can do according to the current state of the game board, you can win or lose or draw, and so on. There are not many moves or board states in Tic-Tac-Toe, more in Chess, and even more in Go.

Board games of this type are traditionally played with any kind of minimax algorithm, which looks at all the possible moves the computer could do, all the possible moves the player could do after that computer move, all the possible moves the computer could do next, and so on. Because there are way too many possible moves to check all of them (except in Tic-Tac-Toe), the computer has to skip most of the possibilities, and after looking a certain number of moves ahead it has to estimate how likely it is to win, instead of searching even farther ahead.

Both of these are where a perceptron could come in. If you can train a perceptron to predict how likely the computer is to win, you can ignore computer moves that make it unlikely to win, player moves that make the computer likely to win, and you can use it as your estimate when you decide to stop searching deeper.

The simplest version of this tree search algorithm just searches one move ahead and there is no reason to discard anything:

def get_next_move(board):
    best_move, best_score = None, -Infinity
    for move in all_valid_moves_for_computer(board):
        board.do(move) # only "pretending" to do the move, because we undo it afterwards
        move_score = call_perceptron(board) # if we did this move, how good is our situation?
        if move_score > best_score:
            best_move, best_score = move, move_score
        board.undo(move)
    if best_move is None:
        # stalemate - no valid moves! game ends. do something about it here
    return best_move

A "move" means something you can do in the game, like moving a piece from a2 to a3. You could represent it in your program as {"from": (0,1), "to": (0,2)}. all_valid_moves_for_computer is a function that returns a list of all the moves the computer is allowed to make according to the rules of the game.

---

Because your game has two different goals, you might want to train a different perceptron for each. Or, you can use the same one in reverse: if you only have a perceptron that tells you whether the computer will win as a defender, but the computer is playing as the attacker, then you can pretend the attacker is the computer (by turning the player pieces into computer pieces, computer pieces into player pieces, and turning the board upside down), check how the perceptron would like to win, and then do the opposite of what it says (do the lowest scored move).

You might get away with using the same one for both, but I expect the gameplay is quite different as attacker and defender and the computer needs to be able to learn that.

---

Whatever algorithm you use, don't forget that you have to train it to win the game, not just to make valid moves. Actually in the tree search algorithm (see above), you have normal code that figures out what the valid moves are. Normal computer programming is already pretty good at that. The perceptron's job is to see how good the computer's situation is if it does the move. You want it to have a high score when the computer is going to win and a low score when the computer is going to lose.

You can do this by playing and recording a whole bunch of games against human friend or against yourself. Then you train the perceptron to predict whether the attacker will win or lose, just by looking at the board. Each time one player makes a move, that's a piece of training data, and at the end of the game you find out whether the labels for all those pieces of training data were 1 (more likely to win the game) or -1 (more likely to lose the game).

---

If you are brave, you can also try a multi-layer perceptron. It will need more and better-quality training data.