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.
;