Cars Guessing Game NetLogo Model

Produced for the book series "Artificial Intelligence";

Author: W. J. Teahan; Publisher: Ventus Publishing Aps, Denmark.

powered by NetLogo

view/download model file: Cars-Guessing-Game.nlogo

WHAT IS IT?

This model plays a simple game trying to guess the colour of cars as they drive past. Various agents maintain probability distributions that they use to predict the arrival of the cars. The source distribution is a fixed distribution that is used to generate the cars, so is the most accurate, and therefore its entropy is the source entropy and corresponding code length is the lowest (the code length is the optimal cost of encoding the sequence of cars given its probability distribution).

Agents 01 to 03 maintain fixed distributions which the user can adjust as they see fit by changing the slider values to the left of the Interface. An adaptive agent also maintains a dynamic distribution by updating counts of cars that have previously been seen. These counts are shown in the Interface by monitors under the heading "Adaptive Agent's distribution". The entropy and code length calculations are shown by monitors at the middle top of the Interface. The adaptive entropy and code length is the one that usually gets close to the source entropy and code length, whereas the other agents' entropy and code lengths reflect how different the slider settings are from the source distribution.


WHAT IS ITS PURPOSE?

The purpose of this model is show how entropy and code length calculations are made given a probability distribution.


HOW IT WORKS

A car turtle agent is used to represent the cars in the environment. These are created with colours distributed according to the source distribution. The arrival of the next car to the left of the environment is determined by a random number generated according to the slider next-car-random-tick-interval.

Turtle agents called "agents" are also present, but are not shown in the animation. These can be considered to be observers watching the cars go past. Each owns a distribution which is a list of counts that are used to calculate the probabilities in order to guess the upcoming cars.


HOW TO USE IT

Setting the values on the sliders for the Source Distribution will determine the distribution for the cars that appear in the animation. Setting the next-car-random-tick-interval will control how often the cars appear. The user can then set the slider values for the three Agent distributions on the left to see how this affects the entropy and code lengths for these distributions.


THE INTERFACE

The model's Interface buttons are defined as follows:

- setup: This resets the animation and initialises the counts, entropy and code length values.

- animate-cars: This starts the animation in the environment (the light blue rectangle shown middle bottom of the Interface).

The model's Interface sliders have the following naming convention:
<agent-name>-<colour>.
This sets the count for the specified colour in the list of counts maintained for the agent whose name is <agent-name>. These counts are used to determine the probability for a specific colour using the following formula:

P(colour) = C(colour) / C_total

where C(colour) is the count for the colour and C_total is the sum of all counts for all colours.

The model's Interface monitors are defined as follows:

- adaptive-<colour>: This is the count of the number of cars observed in the animation of the respective colour that is adaptively updated as the animation proceeds.

- <agent-name> Entropy : This is the entropy of the probability distribution maintained by the agent whose name is <agent-name>.

- <agent-name> Code Length : This is the cost of optimally encoding the sequence of observed cars given the agent's probability distribution.

The model's plot is defined as follows:
- The distributions are converted to a number that uniquely represents the values of the counts in the distribution. (For example, the number 1234 can be thought of as representing four separate counts - 1, 2, 3 and 4 - that combine to produce a unique number. In this case, the separate counts do not range from 0 to 9; they can range from 0 to 1000). The number that uniquely represents the distribution is then plotted versus ticks to show how the distributions evolve over the simulation.


THINGS TO NOTICE

Notice how well the adaptive distribution does compared to the source distribution. The source distribution will have the lowest code length total compared to the others, but usually the nearest distribution will be the adaptive one (unless the counts for one or more of the Agent's distribution exactly match the source distribution counts).

If the source distribution has equal counts, then the adaptive counts will rise at a similar rate, and as a consequence, the red line in the plot will rise diagonally from bottom-left to top-right. (Why?)

A horizontal line in the plot indicates a fixed distribution. Modifying the distribution counts in the middle of the animation will result in the lines in the plot changing to reflect this.


THINGS TO TRY

Try changing the distribution counts in the sliders to see what affect this has on the entropy and code length calculations, and on what happens in the plot. Note that the lower colours (blues and pinks) will cause the greatest shifts in the line plots. (Why?)

Can you achieve a situation where the code length of one of the three non-adaptive Agents is better than the Adaptive Agent? (i.e. the code length is smaller and closer to the source agent's code length total).


CREDITS AND REFERENCES

This model was created by William John Teahan.

To refer to this model in publications, please use:

Cars Guessing Game NetLogo model.
Teahan, W. J. (2010). Artificial Intelligence. Ventus Publishing Aps


PROCEDURES

; Cars Guessing Game model.
; 
; Three agents try to guess the probabilities of cars passing by.
;
; Copyright 2010 William John Teahan. All Rights Reserved.

extensions [ array ]

breed [cars car]     ;; represents cars that the agents observe going past
breed [agents agent] ;; represents the agents guessing what car will come next
;; the process generating the arrival of the cars is also considered as an 'agent' here

agents-own
[ agent-id           ;; identification number associated with the agent
  distribution       ;; probability distribution (represented using frequency counts) that
                     ;; the agent is using to predict or generate the colour of the cars
  dist-total         ;; the total of the distribution's counts
  dist-entropy       ;; the entropy of the distribution
  codelength-total   ;; total code length for the sequence
]

globals
[ next-car-tick      ;; tick when the next car arrives
  source-agent       ;; source 'agent' that is generating the cars
  adaptive-agent     ;; adaptive agent that adapts distribution to the cars as they appear by counting them
  car-colours        ;; colours of the upcoming cars
  car-colours-index  ;; position in car-colours array
  cars-dist-total    ;; source distribution's total used to generate the cars
]

to setup
  ca ;; clear everything
  
  ask patches with [ pycor > -9 ] [ set pcolor 88 ] ; make everything light blue for the "sky"
  ask patches with [ pycor = -9 ] [ set pcolor black ] ; draw the road surface

  let id 0
  create-agents 5
  [
    set agent-id id
    set id id + 1
    set codelength-total 0
    set dist-total 0
    set dist-entropy 0
  ]
  setup-distributions

  set source-agent one-of agents with [agent-id = 0]
  set adaptive-agent one-of agents with [agent-id = 4]
  
  create-car-colours
  set car-colours-index 0
  
  set-current-plot "Distributions versus tick"
end

to setup-distributions
;; sets the distributions for each agent

  reset-distributions
  if (ticks = 0)
  [ ask agents with [agent-id = 4] ; initialise the adaptive distribution
    [ set distribution (list 1 1 1 1 1) ]] ; all colours are equiprobable at the beginning for the adaptive agent
  ;; the adaptive agent's distribution counts are updated susequently elsewhere in update-adaptive-count

  ask agents
  [ set dist-total 0
    set dist-entropy 0
    foreach distribution [ set dist-total dist-total + ?] ; calculate total first
    foreach distribution [ set dist-entropy dist-entropy + (? / dist-total) * neg-log-prob ? dist-total]]
end

to reset-distributions
;; resets the distribution counts (the user may have altered the slider values mid-stream)

  ask agents with [agent-id = 0] 
  [ set distribution (list source-white source-black source-red source-blue source-pink) ]
  ask agents with [agent-id = 1]
  [ set distribution (list agent-01-white agent-01-black agent-01-red agent-01-blue agent-01-pink) ]
  ask agents with [agent-id = 2]
  [ set distribution (list agent-02-white agent-02-black agent-02-red agent-02-blue agent-02-pink) ] 
  ask agents with [agent-id = 3]
  [ set distribution (list agent-03-white agent-03-black agent-03-red agent-03-blue agent-03-pink) ]
end

to-report neg-log-prob [p q]
;; returns the negative of the log to base 2 of the probability p/q.
  report (- log (p / q) 2)
end

to-report distribution-as-a-point [agent]
; return the agent's distribution represented as a single point

  report ;; note that maximum count for non-adaptive distributions is 1000
         ;; so make sure that max-count does not exceed 1000 for adaptive distribution
    (remainder (item 0 [distribution] of agent) 1000) +
    (remainder (item 1 [distribution] of agent) 1000) * 1000 + 
    (remainder (item 2 [distribution] of agent) 1000) * 1000 * 1000 +
    (remainder (item 3 [distribution] of agent) 1000) * 1000 * 1000 * 1000 +
    (remainder (item 4 [distribution] of agent) 1000) * 1000 * 1000 * 1000 * 1000
end

to plot-distributions
;; Plots the distributions as points to show how they vary with time.
  set-current-plot-pen "Agent 01"
  plot distribution-as-a-point one-of agents with [agent-id = 1]
;  type "Agent 01 point = " print distribution-as-a-point one-of agents with [agent-id = 1]
  set-current-plot-pen "Agent 02"
  plot distribution-as-a-point one-of agents with [agent-id = 2]
;  type "Agent 02 point = " print distribution-as-a-point one-of agents with [agent-id = 2]
  set-current-plot-pen "Agent 03"
  plot distribution-as-a-point one-of agents with [agent-id = 3]
;  type "Agent 03 point = " print distribution-as-a-point one-of agents with [agent-id = 3]
  set-current-plot-pen "Adaptive"
  plot distribution-as-a-point one-of agents with [agent-id = 4]
;  type "Adaptive point = " print distribution-as-a-point one-of agents with [agent-id = 4]
  set-current-plot-pen "Source"
  plot distribution-as-a-point one-of agents with [agent-id = 0]
;  type "Source point = " print distribution-as-a-point one-of agents with [agent-id = 0]
end

to create-car-colours
;; creates the colours of the upcoming cars

  let d 0 let i 0 let k 0
  let total ([dist-total] of source-agent)
  let colour black

  set car-colours array:from-list n-values total [ 0 ] ; initialise array to 'black'

  set d 0
  set cars-dist-total [dist-total] of source-agent
  foreach [distribution] of source-agent ; generate car colours according to current source distribution
  [ ; create ? amount of colors
    ifelse d = 0
      [set colour white]
   [ifelse d = 1
      [set colour 1] ; almost black to make doors and windows of the car visible
   [ifelse d = 2
      [set colour red]
   [ifelse d = 3
      [set colour blue]
      [set colour pink]]]]
    
    set k 0
    set i 0
    while [k < ?]
    [ ; insert new colour in a random location
      set i i + random-poisson (round (total / ?)) + 1
      if (i >= total) [set i (remainder i total)]
      while [array:item car-colours i != black]
      [ set i i + 1
        if (i >= total) [set i 0]
      ]
      array:set car-colours i colour
      set k k + 1
    ]
    set d d + 1
  ]
end

to-report next-car-colour
;; Returns the colour of the next car. Creates the colours of the upcoming cars
;; in advance according to the source distribution until it runs out, then creates a
;; whole new bunch again and again.

  let total [dist-total] of source-agent

  if (car-colours-index >= total) or (total != cars-dist-total)
  [ ; we've run out of cars or user has changed source distributions counts
    create-car-colours ; create next lot of upcoming cars in advance
    set car-colours-index 0
  ]
  set car-colours-index car-colours-index + 1 ; move onto next colour for next time
  
  report array:item car-colours (car-colours-index - 1)
end

to-report source-entropy
  report [dist-entropy] of source-agent
end
to-report adaptive-entropy
  report [dist-entropy] of adaptive-agent
end
to-report agent-01-entropy
  report [dist-entropy] of one-of agents with [agent-id = 1]
end
to-report agent-02-entropy
  report [dist-entropy] of one-of agents with [agent-id = 2]
end
to-report agent-03-entropy
  report [dist-entropy] of one-of agents with [agent-id = 3]
end

to-report source-codelength
  report [codelength-total] of source-agent
end
to-report adaptive-codelength
  report [codelength-total] of adaptive-agent
end
to-report agent-01-codelength
  report [codelength-total] of one-of agents with [agent-id = 1]
end
to-report agent-02-codelength
  report [codelength-total] of one-of agents with [agent-id = 2]
end
to-report agent-03-codelength
  report [codelength-total] of one-of agents with [agent-id = 3]
end

to-report adaptive-white
  report item 0 ([distribution] of adaptive-agent)
end
to-report adaptive-black
  report item 1 ([distribution] of adaptive-agent)
end
to-report adaptive-red
  report item 2 ([distribution] of adaptive-agent)
end
to-report adaptive-blue
  report item 3 ([distribution] of adaptive-agent)
end
to-report adaptive-pink
  report item 4 ([distribution] of adaptive-agent)
end

to-report create-new-car
;; creates a new car that enters screen from the left and
;; reports its colour
  let this-colour black
  
  create-cars 1
  [ set color next-car-colour
    set shape "car"
    set heading 90
    set size 10
    set xcor (- max-pxcor)
    set ycor -5
    set this-colour color
  ]
  
  report this-colour
end

to update-adaptive-count [colour]
;; updates the colour's count for the adaptive agent
  let index 0
  let this-count 0
  
  ask adaptive-agent
  [
    ifelse colour = white
      [set index 0]
   [ifelse colour = 1 ; almost black to make doors and windows of the car visible
      [set index 1] 
   [ifelse colour = red
      [set index 2]
   [ifelse colour = blue
      [set index 3]
      [set index 4]]]]

    set this-count (item index distribution)
    set distribution replace-item index distribution (this-count + 1)
    set dist-total dist-total + 1
    set dist-entropy 0
    foreach distribution [ set dist-entropy dist-entropy + neg-log-prob ? dist-total]
  ]
end

to encode-this-car [colour]
;; returns the cost of encoding this car's colour according to the agent's distribution
  let codelength 0
  ask agents
  [
    set codelength 0
    ifelse colour = white
      [set codelength neg-log-prob (item 0 distribution) dist-total]
   [ifelse colour = 1 ; almost black to make doors and windows of the car visible
      [set codelength neg-log-prob (item 1 distribution) dist-total] 
   [ifelse colour = red
      [set codelength neg-log-prob (item 2 distribution) dist-total]
   [ifelse colour = blue
      [set codelength neg-log-prob (item 3 distribution) dist-total]
      [set codelength neg-log-prob (item 4 distribution) dist-total]]]]
    set codelength-total codelength-total + codelength
  ]
end

to animate-cars
; move the cars across the screen from left to right
  let colour black

  setup-distributions ; reset the distributions (in some cases user might have changed one of the counts)
  if (ticks = next-car-tick)
    [ set colour create-new-car
      encode-this-car colour
      update-adaptive-count colour
      set next-car-tick ticks + random next-car-random-tick-interval + 12] ; make sure cars are apart
  ask cars
  [ if (xcor + 1 > max-pxcor)
      [ die ] ; move this car off the screen
    set xcor xcor + 1 ; move this car to the right by 1
  ]
  reset-distributions
  plot-distributions

  tick
end
;
; Copyright 2010 by William John Teahan.  All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
;    from William John Teahan.
; Contact William John Teahan for appropriate licenses for redistribution for
; profit.
;
; To refer to this model in publications, please use:
;
; Teahan, W. J. (2010).  Cars Guessing Game NetLogo model.
;   Artificial Intelligence. Ventus Publishing Aps.
;