CAD Spring 92 Project
A CIRCLES Player on a CHIP
A circles game consists of three rows of circles.  The first row contains 5 circles, the second row 3 circles, and the third row contains 2 circles.  A move consists of crossing out 1 or 2 circles (only two adjacent circles may be crossed out).  The player who has to cross out the last circle looses.
The CAD project for this semester is implement a circles game on a chip in which a ”human” can play the ”computer”.  This is very similar to last semester’s TicTacToe project except the logic is considerably more complex (and hence more interesting!!!).   Even though the logic is more complex, the number of standard cells should end up roughly being the same.    The reasons for doing a game as a CAD project are:
1.	The building blocks needed for this game are the same as those found in most digital designs - memory, random logic, and sequential control.
2.	It gives you practice in taking an abstract concept and mapping it to digital hardware.  This is a talent you will need if you are to become a digital designer.
3.	Once the chip is finished it makes a great gadget to show on the drill field during career day to impress parents and to convince high school students that they should become electrical engineers.
Preliminaries
Two person teams are required for this design; one person will do the Standard cell implementation and one person will do the Actel implementation.  This design entails a lot of ”grunt” work as well as ”think” work and you will need all the help you can get.  Also, two heads are much better than one at figuring out a problem if you get stuck.
You will be given a design strategy via several lectures.  This should help you in designing the chip. However, if you discover a better way of doing something, then DO IT.   This might help you make the design smaller which may end up getting you some extra points.  However, don’t get carried away and completely ignore the design hints given in class.  You may end up in a blind alley and not be able to finish the design which would be disastrous to your project grade.  It is of UTMOST important that you finish the project; it is not sufficient to just give it a good ol’ college try (when you go to work as an engineer your boss will want results - not excuses).  By starting this early on the project you should have plenty of time to finish it if you START NOW.  
To guarantee that you start on the design, several lab checkoffs relating to portions of the project will be assigned.  These checkoffs will count as part of your project grade and are designed to lead to a working VHDL simulation of your design.  Once you are confident that your VHDL simulation performs as expected, you will then transform your VHDL into a digital circuit using the VHDL synthesis tool. 
Board
A circles board is shown below:

We will use both the position numbers and row names to describe locations on the board.
Interface
The chip interface is given below:
1.	Vdd - power supply (not needed on M model)
2.	GND - ground (not needed on M model)
3.	board[10] - ten outputs, one for each board location.  A high means the position is still available for crossing out (i.e., initially, all board lights will be on, as a player crosses out locations the board lights go off).
4.	loss - signals a loss for the human player
5.	win - signals a win for the human player
6.	pready - the player’s move is latched in on the rising edge.  When this returns low, the computer makes its move (will be implemented by a pushbutton operated by the player).
7.	clk  - system clock for the chip.
8.	reset - low true reset.  A low on this input will clear all internal flip-flops and start a new game.
9.	inA[5] - player’s switch inputs for row A. A high means to cross out the corresponding circle.
10.	inB[3]  - player’s switch inputs for row B. A high means to cross out the corresponding circle.
11.	inC[2]- player’s switch inputs for row C. A high means to cross out the corresponding circle.
Total number of signal pins (not counting Vdd/GND) required are 25 ( a MOSIS TinyChip has 34 signal pins available).  We are NOT going to check for illegal moves on part of the human because of lack of space on the chip (we will have to trust him!!).  Also, the human will always get the first move ( there will not be an option for the computer to move first).
Strategy
Successful play at circles is simply a matter of pattern recognition.  Faced with a particular board pattern you will need to recognize it as either a winning pattern or a losing pattern.  A losing pattern is one in which it does not matter what move you make; the opposing player will be able to make a move which causes you to be faced with yet another losing pattern.  A winning pattern is one in which you can make a move which leaves your opponent with an losing pattern.  The figure below shows a winning pattern and the correct move needed to change it into a losing pattern for your opponent: 

We will classify patterns according to the number of circles left and to the groupings of the remaining circles.  A 2+2 pattern is 4 circles left in 2 groups of 2.  A 3+2+1+1 pattern is 7 circles left; 1 group of 3, 1 group of 2, and 2 groups of 1. And so forth. 
 You will need to build up a ”library” of  winning and losing patterns.  You do this by starting with just one circle and going up.  Obviously, a pattern of one circle is a losing pattern; it is the definition of a loss!  You should easily be able to discover that all patterns of two circles (2+0, 1+1) are winning patterns (i.e., you can make your opponent face a losing pattern by just crossing out one circle).  Valid three circle patterns are 3+0, 2+1, and 1+1+1.  It turns out that 3+0 and 2+1 are winning patterns while 1+1+1 is a losing pattern.  For each winning pattern,  you will need to record the move you would make to convert it to a losing pattern.  
Your ”pattern” library should look like this:

You should discover that the person going first can always win.  However, he can always win ONLY if he keeps making the correct moves.  If he strays off of the winning path then the other player should be able to force a win.  Your design should always win if the human player makes a wrong move. 
Implementation
The chip can be split into three major blocks: board, finite state machine, and move generation.  The board provides the 10 flip-flops for the board locations and some selection logic.  The finite state machine will provide the control for the chip.  The move generation block will be the largest block and will generate the computer’s next move based upon the current board pattern.  We will discuss the move generation block first since it is the most complex.
Move Generation Block
The move generation block is actually several smaller blocks of logic.  The first block we will discuss is the move block.  The move block is the logic which implements the ”knowledge” in your pattern library.  Based upon some input pattern (3+1 or 4+3+1 or 4+2, etc) it will assert an output line which will cause one or two zeros to be deleted.  The input signals to the move block are shown below ( not all are shown; you may discover you will have to add some; you may even be able to delete some). 

The move block operates on two pieces of information: how many circles are left on the board and what groups are present on the board.  The c9 through c1 inputs indicate how many circles are left on the board; only one of these inputs should be asserted at any given time.  The g?? inputs indicate what groups are present on the board.  The g5a input indicates that there is a group of 5 circles on the board. The g4a input  indicates that there is a group of 4 circles on the board.  The g3a input indicates there is one group of 3 circles on the board; g3b asserted would mean there are two groups of 3 circles on the board (only one should be asserted at a time).  The g2a, g2b, g2c, and g2d inputs correspond to 1, 2, 3, and 4 groups of 2 circles left on the board (only one should be asserted at a time).  The g1? inputs function similarly.   Obviously these inputs do not come directly from the board but from other logic blocks between the move block and the board block.
The d?_g? outputs are command outputs to delete specific locations from the board.  The d2_g5 output says to delete 2 circles from a group of 5 circles; the d1_g3 output says to delete 1 circle from a group of three circles, etc.  You may find it necessary to add other ”special” delete outputs such as ”d1_g3m” which might be ”delete 1 zero from the middle of a group of 3” or ”d_p3” which says to delete the zero in position 3.   You should try to make the output commands as general as possible because the inputs do not indicate at all where a particular pattern occurs on the board (i.e., a g2a = HIGH indicates a pattern of two on the board but this could be anywhere; however, g4a = HIGH indicates a pattern of 4 left on the board and we know this has to be on row A).  There will be some additional logic between the move block outputs and the board to ”map” the move block output commands to actual board locations.  If none of the move block outputs are asserted then we will assume that the mapping logic will randomly choose some circle to delete.
A section of code for the VHDL model of the move block might be:

   -- check case of three circles left 
   if (c3 = ’1’) then
    -- check 3 +0 pattern 
     if (g3a  = ’1’) then
	-- we want to delete two circles 
	d2_g3 <= ’1’;
     endif;
    -- check 2+1 pattern 
    if (g2a  =  ’1’ && g1a = ’1’)  then
	-- we want to delete two circles 
	d2_g2 <= ’1’;
    endif;
   -- ignore 1+1+1 pattern since it is a losing pattern 
}
   .... etc and so forth

Note that by defining the inputs and outputs to the move block in this way you can write the move block model code directly from your pattern library. This will simplify debugging of your strategy.
Generation of Move block inputs
The g?? and c? inputs to the move block are generated by some logic that sits between the move block and the board.  This logic is divided into three blocks called patterns, groups, and count.
patterns block
The patterns block classifies the type of patterns found on each row.  The input/output signals of the patterns block are shown below:

The inputs to the patterns block are just the board locations.  The outputs of the patterns block can be divided into ra?, rb? and rc? which tell what type of pattern is present on that row.  For each set of row outputs (ra?, rb? and rc?) only output can asserted a time.  For row C, rc1 indicates there is one circle left on the row and rc2 indicates there are two circles left on the row (rc1 and rc2 cannot both be asserted at the same time).  Note that rc1 does not indicate which circle is left; you can use the board outputs to determine that if needed. For row C, rb3 indicates three circles left, rb2 indicates two circles left (one group of two), rb1_1 indicates two circles left (two groups of 1), and rb1 indicates one circle left.  For row A, ra5 indicates five circles left, ra4 indicates four circles left (one group of 4), ra3_1 indicates four circles left (one group of 3, one group of 1), ra2_2 indicates four circles left ( two groups of 2), etc....
It turns out that the outputs of the patterns block are useful to more than one block of logic inside the total move generation logic. 
groups block
The groups block produce the g?? inputs needed by the move block. The inputs to the groups blocks are simply the r?? outputs produced by the patterns block.

Having the inputs to the groups block coming from the patterns block instead of directly from the board greatly simplifies the logic needed in the groups block.  For example, the g3b output is just:

	g3b = (ra3 && rb3) || (ra3_1 && rb3);

Another hint: Use of nested if-then statements is justified inside of the groups block.
count block
The count block produces the c9-c1 inputs for the move block. The inputs to the count block are simple the r?? outputs produced by the patterns block.

I made use of a four-bit full adder in my count block; however, it can also be done via straight combinational logic.  I am unsure as to which approach will take less silicon area.
Input side of move block
The path from the board to the move block then looks like:

The logic between the move block and the board attempts to map the generic delete commands of from the move block to specific board locations.   I am going to explain one way to do this; there several ways of doing this and I really don’t know which is better.  If you come up with a better way then please do it.
I am going to call the logic between the move outputs and the board inputs the mapping logic since it maps delete commands from the move logic into specific delete commands for the board.  I broke this mapping logic into multiple parts as shown below.  

This particular breakup of the logic was my third try at this logic and I determined that a significant number of gates could be saved if it was done this way.   Unfortunately this implementation is not the simplest to understand - my first two tries were much more straightforward (more brute-force) and easier to understand but used a lot more gates.   
The movemap/mux is the most complicated block and does most of the work.   I have called this block the movemap/mux block because in my implementation I actually broke this into two separate blocks called movemap and mux.  However,  I want to talk about their operation together because it makes much more sense that way.  When you implement this block you may choose to do it with one block of logic  or multiple blocks of logic; the choice is up to you. The movemap/mux block is responsible for choosing valid board locations to delete to based upon the delete command from the move block.  The movemap block may actually choose multiple valid locations to delete; it is up to the priority block to only choose one location to delete.  Note that the output of the movemap/mux block is a 10 bit bus; each bit corresponds to a board location.  A logic 1 means to delete that location from the board (cross out the circle); a logic 0 means to keep that location unchanged. 
To illustrate the operation of the movemap block, assume the current board setup is as shown below:

In the above example the delete command from the move block is to delete one circle from a group of two.  The job of the movemap/mux block is to look at the current board locations and ONLY pass through groups of two.  It will then be the job of the priority circuit to choose one of the circles to delete. Note that the priority circuit only has to know to delete one or two circles; it doesn’t need to know any other information.  It specifically does NOT need to know it is deleting one circle from a group of two; the movemap/mux logic is only feeding it groups of two so it only has to know that it has to deletes one circle.
The example shown below has two zeros being deleted from a group of three.  Note that the priority circuit has to delete two circles.  You should write your priority circuit code to make sure it only can delete two contiguous circles on the same row.

Some delete commands from the move block may cause special problems.   For example, lets assume that the delete command is d1g3m (delete one circle from the middle of a group of three) and that the current board configuration is as shown below (Example 3).  In this particular case, we cannot pass through the two groups of three circles to the priority circuit because it will delete a circle from the END of one of the groups of three, not from the middle.  In this case, the movemap/mux block must just pass through the explicit circles which can be deleted (in this case, the middle circle from the group of three on row A and the middle circle from the group of three on row B).  These special cases require more logic to take care of but there are not very many of them.

Priority Circuit Implementation
We will first talk about the implementation of the priority circuit since it is so simple.  

The din[10] input is the 10 bit bus from the movemap/mux block; a logic 1 means the location location contains a circle.   The dout[10] output goes to the board; a logic 1 means to delete (cross out) that circle from the board (we will talk about the board logic later).  If the onep input is ’1’, then delete one zero else delete two zeros. 
The code for the priority block is just two chains of nested if-else statements; one chain for deleting one zero and one chain for deleting two zeros.  Some sample code is show below:
	dout <= ’0’;
	if (onep = ’1’) then
	  -- delete one zero 
	  if (din[0] = ’1’ )  then
	    dout[0] <= ’1’;
	   elsif (din[1] = ’1’) then
	    dout[1] <= ’1’; 
	     elsif (din[2] = ’1’) then
	     dout[2] = 1;
	      etc...
	  end if;
 	 else 
	  -- delete two zeros 
	  if (din[0] = ’1’ and din[1] = ’1’) then
	    dout[0] <= ’1’; dout[1] <= ’1’;
	  elsif (din[1] = ’1’ and din[2] = ’1’) then
	    dout[1] <= ’1’; dout[2] = 1;
	    etc...
	   end if;
	end if;

The code shown above will work -- however, it can be improved upon.  I will let you figure out the improvements.
movemap/mux Circuit Implementation
It is fairly easy to implement this block in straight forward manner.  Unfortunately, you will end up with a very large number of gates and I can almost assure you that your design will not fit in a Tiny Chip frame.  I suggest that you go ahead and write your model in the brute-force manner just to go ahead and get your model working; this will also allow you work on the other parts of the chip.  However, during implementation you may want to consider re-implementing this block along the lines suggested below.
The reason the brute force approach uses a lot of gates is that you are trying to assign values to a 10-bit bus and each bit requires considerable logic.  You can save gates by trying to ”reuse” information from the board whenever possible.  To do this, I split my implementation into a movemap block and a mux block as shown in the figure below.  The mux block mixes the dout outputs from the movemap block with the board outputs to form the dout bus which feeds the priority block.  The passa, passb, passc and zeroa signals determine how the dout bus from the movemap block and board values are mixed.   The default action of mux block is to just assign the dout outputs the value of the din inputs from the movemap block.  The passa, passb, passc, and zeroa signals are used override this default action for groups of board locations. The passa input to the mux block says to pass row A outputs from the board to the dout outputs unchanged (similarly for the passb, passc inputs).  The zeroa input to the mux block says to zero out all of row A ( I did not find a need for zerob, zeroc signals). 
Why does this approach use less logic?   You end up making much less assignments inside of movemap to the 10-bit dout output than with the brute-force approach.  The mux block can be implemented with as few as one standard cell per bit (or just 10 gates).   Thus, by ”re-using” information from the board you save gates.  

Example #4 shows a current board location, the outputs of the movemap block, and the output of the mux block (see below).
Random Moves
What happens if none of the d?? outputs from the move block are asserted?  We had said before that this happens if we are faced with a losing pattern and that we should just randomly delete one circle from the board.   Because of lack of space, I implemented a VERY simple psuedo random move strategy for this case.  I tied a flip-flop to the clock and set it up to toggle every clock period.  If the flip-flop is ON and I have to make a random move, then I delete one zero in a fixed priority starting from position 0 (start with first circle in row A,  the priority circuit looks at positions 0-9 for a circle to delete).  If the flip-flop is OFF and I have to make a random move, then I delete one zero in a fixed priority starting from position 5 (start with the first circle in row B, the priority circuits looks at positions 5-9, 0-4 for a circle to delete).   The end result is that there are two possible moves the computer can make when faced with a losing pattern; the choice is determined by the current value of the flip-flop.  To the human player, it looks like the chip doesn’t play exactly the same game every time but it will be very close.  
You can easily elaborate on this to make a much better ”psuedo-random” choice;  because the gate count was getting fairly high I decided to keep it simple.    This logic can implemented in either the movemux block or the priority block; the choice is up to you.
I definitely want to you to implement some sort of psueodo-random move;  how you do it is up to you.