Implementation of the simple 2D Schelling model

This is an implementation of a simple version of the 2D Schelling model. We solve it as follows:

  • We create a 2D Numpy array that is 20x20 cells. In our implementation, the number 0 will represent an empty cell, 1 will represent a triangle, and 2 will represent a square.
  • We initialize the array with approximately 1/3 empty cells, 1/3 triangles, and 1/3 squares, all of which are placed in random cells.

Then, we evolve this model using the following rules:

  • Neighbors are defined as polygons that are in any cell that's immediately adjacent (either left/right/up/down or diagonal) to a given polygon.
  • A polygon (triangle or square) is happy if at least 1/3 of its neighbors are like it
  • A polygon is meh if all of its neighbors are like it, or if it has no neighbors.
  • A polygon is considered to be segregated if all of its neighbors are like it, or if it has no neighbors. The "segregation measure" is the fraction of polygons that are considered to be segregated.

We evolve the board forward by randomly selecting a single unhappy polygon and moving it to an empty cell. We continue doing so until every polygon is either meh or happy. We keep track of how your segregation index evolves with each step, as well as the fraction of polygons that are meh and happy. Finally, we plot both the board and (separately), the evolution of the segregation, meh fraction, and happy fraction over time.


In [ ]:
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import random
import time

# USER PARAMETERS

square_frac = 1./3.     # fraction of cells that are squares
triangle_frac = 1./3.   # fraction of cells that are triangles
happy_min_frac = 1./3.  # unhappy if less than this fraction
happy_max_frac = 1.0   # unhappy if more than this fraction
board_size = 20         # size of board (NxN).  Board assumed to be a square.
random_seed = 8675309   # random seed for the simulation

In [ ]:
# put your code here.  Add additional cells as necessary!

def generate_board(tri_frac=1./3., square_frac=1./3., board_size=20, random_seed=8675309):
    '''
    Generates a game board.  Optionally takes in a fraction of cells that are triangles, 
    fraction that are squares, a board size (board assumed to be square), and a random seed.
    Returns a games board.
    
    Note: in the returned game board, empty spaces have a value of zero, triangles are 1, 
    and squares are 2.
    '''
    random.seed(random_seed)

    # create a board that's entirely empty.
    game_board = np.zeros([board_size,board_size],dtype='int64')
    
    # loop over game board and fill it in.
    for i in range(game_board.shape[0]):
        for j in range(game_board.shape[1]):
            val = random.uniform(0.0,1.0)

            if val <= square_frac: 
                game_board[i,j] = 2
            elif val > square_frac and val <= tri_frac+square_frac: 
                game_board[i,j] = 1
            else:
                game_board[i,j] = 0  # empty is zero
    
    return game_board

In [ ]:
def is_happy_or_meh(game_board, happy_min_frac, happy_max_frac):
    '''
    This function takes in the game board and the bounds for happiness (i.e., at least
    a fraction happy_min_frac of your neighbors must be like you, and at most happy_max_frac 
    must be like you in order for you to be happy.)  The happy_max_frac is not necessary for the 
    baseline version of the game, but I put it in b/c it's necessary for the later versions.  
    The function returns 'True' if the cell is either (1) happy, (2) meh, or (3) empty - in other words,
    the only cells marked 'False' are truly unhappy.
    '''

    # create an empty array
    happy_board = np.zeros_like(game_board)
    
    # loop over board
    for i in range(game_board.shape[0]):
        for j in range(game_board.shape[1]):
            happy = False
            
            # guess at bounds of neighborhood (this cell +/- in each direction)
            xstart=i-1
            xend=i+2
            ystart=j-1
            yend=j+2
            
            # do some bounds-checking to ensure that we don't overrun the ends of the array
            if xstart < 0:
                xstart = 0
            if xend > game_board.shape[0]:
                xend = game_board.shape[0]
            if ystart < 0:
                ystart = 0
            if yend > game_board.shape[1]:
                yend = game_board.shape[1]
            
            # calculate the number of neighbors (not counting me, hence the -1)
            num_neighbors = game_board[xstart:xend,ystart:yend].size - 1
            
            # how many of my neighbors are like me?  (subtract 1 b/c I'm always like me)
            like_me = (game_board[xstart:xend,ystart:yend]==game_board[i,j]).sum()-1
            
            # how many of my neighbors are empty cells?
            empty = (game_board[xstart:xend,ystart:yend]==0).sum()
            
            frac_like_me = like_me/num_neighbors
    
            frac_empty = empty/num_neighbors
    
            # start off assuming each cell is 'happy', which really means empty, meh, or happy 
            # (in other words, assume that each cell is "not unhappy")
            happy = True
        
            # not happy if too many neighbors are like me (not important for baseline version)
            if frac_like_me > happy_max_frac:
                happy=False
            
            # not happy if too many neighbors are *unlike* me
            if frac_like_me < happy_min_frac:
                happy=False
    
            # assign values to the board
            happy_board[i,j] = happy
    
    return happy_board

In [ ]:
def find_unhappy(happy_board):
    '''
    Takes in the game board and finds a random unhappy cell, and returns the indices 
    of that unhappy cell.
    '''
    
    not_done=True
    counter=0

    # loop until we find an unhappy cell or until we iterate for too long
    # In this case, "too long" is 10x the size of the board, and if we reach
    # that we probably don't have any unhappy cells.
    while not_done and counter < 10*happy_board.size:

        # pick random x and y indices
        i = random.randint(0,happy_board.shape[0]-1)
        j = random.randint(0,happy_board.shape[0]-1)

        # if this cell happens to be unhappy, return its indices (which means
        # that we exit the function)
        if happy_board[i,j]==False:
            return i,j
        counter+=1
    
    # if we can't find any unhappy cells, return an invalid value.
    print("can't find an unhappy cell!",counter)
    return -1, -1

In [ ]:
def find_empty(game_board):
    '''
    Takes in the game board and finds a random empty cell, and returns the indices 
    of that empty cell.
    '''
    
    not_done=True
    counter=0

    # loop until we find an empty cell or until we iterate for too long
    # In this case, "too long" is 10x the size of the board
    while not_done and counter < 10*game_board.size:
    
        # pick random x and y indices
        i = random.randint(0,game_board.shape[0]-1)
        j = random.randint(0,game_board.shape[0]-1)

        # if this cell happens to be empty, return its indices (which means
        # that we exit the function)
        if game_board[i,j]==0:

            return i,j
        counter+=1

    # if we can't find any empty cells, return an invalid value.
    print("Can't find an empty cell!",counter)
    return -1, -1

    pass

In [ ]:
def move(game_board, unhappy_cell, empty_cell):
    '''
    Move an unhappy polygon to an empty cell.
    
    Takes in the game board, the indices for the unhappy cell, and the 
    indices for the empty cell.  We do not return anything because
    python directly modifies the game_board array.
    '''
    val = game_board[unhappy_cell[0],unhappy_cell[1]]
    game_board[unhappy_cell[0],unhappy_cell[1]] = 0
    game_board[empty_cell[0],empty_cell[1]] = val

In [ ]:
def calc_segregation_metric(game_board):
    '''
    Calculates the segregation metric for the game board.  Takes in 
    the game board, returns a fraction that corresponds to the fraction 
    of segregated polygons. (Note that "segregated" corresponds to polygons that
    are surrounded entirely by some combination of polygons like them and empty
    cells - polygons that are adjacent to unlike polygons are not segregated.)
    '''
    
    num_filled_cells = 0
    num_segregated = 0

    # loop over the entire game board
    for i in range(game_board.shape[0]):
        for j in range(game_board.shape[1]):
            
            # only look at non-empty cells
            if game_board[i,j] > 0:
                
                num_filled_cells += 1
                
                # calculate neighborhood
                xstart=i-1
                xend=i+2
                ystart=j-1
                yend=j+2

                # check to make sure bounds are sensible
                if xstart < 0:
                    xstart = 0
                if xend > game_board.shape[0]:
                    xend = game_board.shape[0]
                if ystart < 0:
                    ystart = 0
                if yend > game_board.shape[1]:
                    yend = game_board.shape[1]

                # calculate number of cells in this polygon's neighborhood
                num_total = game_board[xstart:xend,ystart:yend].size
                
                # how many adjacent cells are like me?  (including me)
                num_like_me = (game_board[xstart:xend,ystart:yend]==game_board[i,j]).sum()

                # how many adjacent cells are empty?
                num_zeros = (game_board[xstart:xend,ystart:yend]<1).sum()

                #print("zeros,like me, total:", num_zeros,num_like_me,num_total,i,j)
                #print(game_board[xstart:xend,ystart:yend])
                #if (num_zeros+num_like_me) == num_total:
                #    print("SEGREGATED")
                #print("\n\n")

                # if all adjacent cells are either filled with polygons like me or
                # empty cells, this cell is segregated
                if (num_zeros+num_like_me) == num_total:
                    num_segregated += 1

    # return the fraction of polygons that are 'segregated'
    return num_segregated/num_filled_cells

In [ ]:
def plot_board(myarray):
    '''
    This function takes in a 2D array and uses pyplot to make a matplotlib
    plot.  It returns no value.
    '''
    
    
    # first create two vectors based on the x and y sizes of the grid
    x_range = np.linspace(0, myarray.shape[0], myarray.shape[0]) 
    y_range = np.linspace(0, myarray.shape[1], myarray.shape[1])
    
    # use the numpy meshgrid function to create two matrices 
    # of the same size as myarray with x and y indexes
    x_indexes, y_indexes = np.meshgrid(x_range, y_range)
    
    # make a list of all the x and y indexes that are either squares or triangles.
    # the notation below is relatively new to us; it means that when myarray==(value),
    # only record those values.
    sq_x = x_indexes[myarray == 1]; 
    sq_y = y_indexes[myarray == 1]; 
    tr_x = x_indexes[myarray == 2]; 
    tr_y = y_indexes[myarray == 2]; 
    
    # plot the squares and triangles.  make the size of the polygons 
    # larger than the default so they're easy to see!
    plt.plot(sq_x,sq_y, 'bs',markersize=10)   
    plt.plot(tr_x,tr_y, '^g',markersize=10)  
    
    #Set the x and y limits to include half a space overlap so we don't cut off the shapes
    plt.ylim([-0.5,myarray.shape[1]+0.5]) 
    plt.xlim([-0.5,myarray.shape[0]+0.5])

In [ ]:
# This cell runs the entire program, calling the functions defined above.

# generate game board
gb = generate_board(triangle_frac, square_frac, board_size)

# plot initial configuration
plot_board(gb)

step_counter = 0

# create empty lists to keep track of steps and segregation metric
segregation = []
step = []

# this is a timer so that I know how long the loop runs.
start_time = time.time()

max_steps = 10000

# move polygons until everybody's happy/meh or we reach max_steps
for i in range(max_steps):
    
    # for this step, find out who is unhappy
    happy_or_meh = is_happy_or_meh(gb,happy_min_frac,happy_max_frac)

    # get the indices of an unhappy polygon
    uhx,uhy = find_unhappy(happy_or_meh)
    
    # break if there are no unhappy polygons
    if uhx<0:
        break
    
    # get the indices of an empty cell
    emptyx,emptyy = find_empty(gb)
    
    # break if there are no empty cells (should never happy)
    if emptyx<0:
        break
        
    # move unhappy polygon to empty cell
    move(gb,[uhx,uhy],[emptyx,emptyy])

    step_counter += 1

    # keep track of segregation metric and number of steps
    step.append(step_counter)
    segregation.append(calc_segregation_metric(gb))

stop_time = time.time()

print("time elapsed:", stop_time-start_time,"seconds.  Steps:", step_counter, 
      "time/step:", (stop_time-start_time)/step_counter,"seconds.")

In [ ]:
# plot the final state of the game board
plot_board(gb)

In [ ]:
# plot the evolution of the segregation metric
plt.plot(step,segregation)