mem·o·ry·less·ness

-[ background ]-
 
In the Spring of 2003, I took a course in stochastic processes. The second exam was take home and it required some coding, which I did in TurboPascal, as in the case of my tic tac toe program one year later (the posting of which reminded me of the code from my stochastic processes class).

-[ assignment and notes ]-

A local store uses an (s, S) inventory policy for a particular product. Every Friday evening after the store closes, the inventory level is checked. If the stock level for the product is greater than s, no action is taken. Otherwise, if the stock on hand is less than or equal to s, an amount S-s is procured over the weekend and is available when the store re-opens on Monday morning.

Let {X_n, n = 1, 2, …} be the stock on hand when the inventory is checked on Friday evening of week n and let {Z_n, n = 1, 2, …} be the demand for product during week n.

Then for any ω ∈ Ω,

   X_n+1(ω) = X_n(ω) - Z_n+1(ω)  if s < X_n(ω), Z_n+1(ω) ≤ X_n(ω)    X_n+1(ω) = S - Z_n+1(ω)  if X_n(ω) ≤ Z_n(ω) ≤ S    X_n+1(ω) = 0  otherwise.

Let s = 3, S = 5, X₀ = 0 and assume customers arrive at the store according to a Poisson process with rate λ = 4 per week. (Each customer wants one unit of product.)

Phase I of the exam required the proof that {X_n, n = 1, 2, …} is a Markov chain and writing its transition matrix. These are intuitive (or you’re looking for the answers to your exam, assuming the prof. still uses this exam), so I won’t include them here.

Phases II and III of the exam required some coding.

Phase II

A) Write a program to generate (i.e., fill in) the one-step transition matrix for a passed value of S. Print the one-step matrices for S = 4.

B) Let π^[0] = (1, 0, …, 0). Write a program to compute the equilibrium probabilities of the Markov chain using Jacobi iteration.
Also, plot π_j^[0] as a function of n, i.e., the number of Jacobi iterations.

…

Jacobi Iteration.

Jacobi Iteration is a simple computational technique for obtaining the equilibrium probabilities of a Markov chain using a series of matrix multiplies rather than solving a system of linear equations.

Let π^[n] be the probability row vector representing the probability of occupying a given state after n transitions. That is, π_j^[n] = P{in state j after n transitions}.

By conditioning on the state occupied at transition n we have

π^[n+1] = π^[n]P  (Eqn 1)

where P is the one-step transition matrix for the Markov chain. In the limit as n goes to ∞, π^[n] goes to π, the vector of equilibrium probabilities. Depending on the system and the desired accuracy, convergence can be quite rapid.

To compute the equilibrium probabilities, start with π^[0], then compute π^[1], then π^[2] and so on using Equation 1 until π^[n+1] is “close” to π^[n]. For this problem, stop iterating when

Max{|π_j^[n+1] - π_j^[n]|, all j in State Space} = 0.0001.

Computational note: Due to round-off error by the computer, it may be necessary to “re-normalize” π^[n] every few iterations so that its elements sum to one. To do this, add up the first m-1 elements of the vector π^[n] (assuming the chain has m states) then set the m^th element equal to one minus the sum. The elements now sum to one.

The source code and binaries for the solutions to these Phase II questions are linked below. I’m not including Phase III’s code because, unlike Phase II’s, it does not have many possible uses outside the context of this exam. Phase II’s code is relevant because somewhere, someone might want to write a simple program to perform Jacobi iterations or to write one-step transition matrices. This code could easily be extended for other (non-Poisson) arrival distributions and/or for generation of the n-step transition matrix.

-[ license ]-
 
The code and the accompanying binaries are distributed with NO LICENSE; don’t blame me if this messes up your computer. Please do let me know if you find an error, though.

-[ downloads ]-

• Phase II, Part A - [ source ] | [ binary ] | [ source + binary (.zip) ]
• Phase II, Part B - [ source ] | [ binary ] | [ source + binary (.zip) ]

-[ background ]-
 
For a class I took during the Spring of 2004, I had to write a program that plays tic tac toe. Technically, I should say “we,” since I had a partner, but I wrote the program and he did the manual enumeration of a tic tac toe decision tree. I think I picked the easier half of the assignment. If you want to see the tree, you’ll have to do that part of the assignment yourself.

The class was “Cognitive Engineering;” it was all about Turing machines and Turing tests such. This assignment related to the cognitive aspects of problem solving and whether or not a machine could duplicate them. It’s a very (extremely amazingly ultra) simple AI.

-[ actual assignment ]-
 

PART A

Draw the state transition tree for playing tic-tac-toe. This diagram should outline all of the possible states of the game; starting with a blank diagram and moving to all possible ends. Note that who goes first (X or O) doesn’t really matter because when we get done, we can just replace all X’s with O’s and O’s with X’s to get the other tree. Because your program (see below) will have X go first, do this tree. Also, when making your tree realize that many different configurations are the same. For instance, there are only 3 possible initial moves (middle, side or corner) even though there are 9 spaces. If you can rotate the game to get an identical configuration, these are the same in terms of strategy (i.e. if you are playing tic-tac-toe, nobody cares if you rotate the paper before making your move).

PART B

Design and construct a computer program to play tic-tac-toe. Assume that ‘X’ always goes first, and that your opponent can be either ‘X’ or ‘O’. You may use any computer language you wish, within reason.

Material turned in for this assignment should include: an enumeration of the problem space; a written verbal description of your computer algorithm, and a disk containing your program.

-[ algorithm ]-
 
From the document we turned in:

This tic tac toe program was written in Turbo Pascal for Windows version 1.5. The algorithm that the program uses to play tic tac toe is rather simple. First, the program allows the user to choose if s/he wants to be play as X or O. If the user chooses O (and thus chooses to allow the computer to play first), the computer’s first move is to randomly select one of the corners. If the user chooses X (and thus, chooses to go first him/herself), the program chooses a space based on the user’s choice. If the user has selected a corner, the program chooses the middle. Otherwise, the program chooses a corner at random. After the first turn, the program is designed to play strategically.
The strategy employed by the program is used until a winner is determined. The program is designed to first try to win. It examines all of the squares, and if it is capable of winning (having three X’s or O’s in a row, depending on whether it is X or O), it does so. If it cannot win, it again examines all nine squares and attempts to block the user from winning. If the user has two in a row and can win on the next turn, the program will block the user. If the program cannot win or block, it will attempt to play offensively. If either pair of side squares is free (e.g. above and below the middle or to the left and right of the middle), it will randomly pick one of these free sides. If no pair of side squares is free, it will try to take the middle square. If the middle square has already been taken, it will randomly choose a free corner. If no corner is free, it will randomly choose a free side.
The program allows the user to play multiple times without exiting. Additionally, it keeps track of how many times it has won, how many times the user has won, and how many tie (or cat) games there have been. For more detail about how the program works, please see the source code.

-[ notes ]-
 
This was written in Turbo Pascal, for that ultra-retro feel (actually, because that was the only compiler I had at the time), but the executable file should work on most (all?) Win32 installations. All ASCII art included is believed to be in the public domain. If you use the code for anything, please let me know by leaving a comment. Thanks.

This needs work, but it can beat me. Of course, I always sucked at tic tac toe. According to the professor, there’s a flaw in the logic that allows the user to always win. I’ve been unable to find it, though. Please let me know if you find it.

We got a 100 on this project, despite the “flaw,” in case you’re wondering. I still got a B in the class, though.

-[ license ]-
 
The code and the accompanying binary are distributed with NO LICENSE; don’t blame me if this messes up your computer. Please do let me know if you find an error, though.

-[ download ]-
 
[ source ] | [ binary ] | [ source + binary (.zip) ]