2006-04-30

Mu Torere, a digression

In this entry the number of possible combinations of playing pieces will be determined. What will be done is to find the Generating Function given by Burnside's Lemma, which is a special case of Polya's enumeration theorem. Before anyone asks, the only thing that I could determine about Generating Functions is that they are a way to encode sequences (and not a decent how-to in the description either.) Examples are better.

First off, Permutation Groups are collection of permutaion operations (element swapping) on the elements of a set. They can be denoted by cycle decompositions of the swaps being made. For instance;
A 2-element swap on a 6 element Set
123456
153426
=
(1)(3)(4)(6)(25)
has 4 1-element cycles and 1 2-element cycle
While
Rotation on the same 6 element Set
123456
234561
=
(123456)
ha only 1 cycle of 6 elements.

Polya's enumeration theorem uses equivalent decompositions, i.e. (1)(2)(3)(4)(56) and (1)(3)(4)(5)(26) having 4 1 elements cycles and 1 2 element cycles are equivalent, to
create the generating function. Each permutation operation is weighted according to the number of equivalents and then the average is taken.
As an example the number of distinct ways to add edges to a 3 vertice graph can be found as follows. The permutations on a 3 element set is (second example);
[1 2 3] = (1)(2)(3)
[1 3 2] = (1)(2 3)
[2 1 3] = (1 2)(3)
[2 3 1] = (1 2 3)
[3 1 2] = (1 3 2)
[3 2 1] = (1 3)(2)
Which creates the function; 1/6 ( x1^3 + 3 a1 a2 + 2 a3 ). The translation is that there is one equivalent of 1-cycle * 1-cycle * 1-cycle plus three equivalents of 1-cycle * 2-cycle plus two of 3-cycle operations.
The generating function is then created using (z+1), where z denotes an edge and 1 denotes no edge. This produces ((z+1)^3 +3 (z+1)(z^2+1)+(z^3+1))/6.
Or rather, z^3 + z^2 + z^1 + 1. Which can be read as there is only one way to add three edges to the graph, only one way to add 2 edges, only one way to add 1 edge and only one way to add no edges. Only considering rotations will procude the same results.

For Mu Torere, only the rotation permutations will be used. This allows us to equate, for instance, all swaps that are 2 places apart. Ignoring teh central location, means that only 8 locations need be considered. From this, the permutaion groups are;
[12345678] = (1)(2)(3)(4)(5)(6)(7)(8)
[23456781] = (12345678)
[34567812] = (1357)(2468)
[45678123] = (14725836)
[56781234] = (15)(26)(37)(48)
[67812345] = (16385274)
[78123456] = (1753)(1864)
[81234567] = (18765432)
Being 4 permutations 8-element cycles, 1 permutation group of 1-element cycles, 1 permutation group of 2-element cycles, and 2 groups of 4-element cycles. This gives the preliminary function of 1/8 (g1^8 + g2^4 + 2 g4^2 + 4 g8).
For the generating function, we will use (c+u+1) where c will denote a piece owned by the Computer, u will denote one owned by the User, and 1 will be a empty location. This creates the generating function ((c+u+1)^8 + (c^2+u^2+1)^4 + 2 (c^4+u^4+1)^2 + 4(c^8+u^8+1))/8.

HomeWork: What terms will we need to examine? And what will be final number?

Update:
The terms to examine are C^4 U^4, C^4 U^3, and C^3 U^4.
The numbers are 10, 35, and 35, which totals 80.

2006-04-29

Mu Torere AI

While I recover the Undo functionality, I will go over the background of the program's AI in the meanwhile.

Essentially, the program can use one of 3 kinds of decision making routines to simulate a proper AI. (This is in addition to the random move routine.)
The first is the basic tree graph to layout what move lead to which moves and an evaluation of that move. For this version I will only evaluate the NEXT Computer's move and the following User's move (one ply each) for the winning move.
Another is to use pattern recognition. The program can check the current positions of the playing pieces and find out if a winning move is possible.
The related routine (the third one) is to use a state machine. The program will not need to decipher the game to find the proper state, but the current state of the game will need to be stored to determine the next game state. The trade-offs are pretty much obvious, program complexity (deciphering the game to a state value) versus footprint (storing the current state and the next-state table.)

The pattern matching and the state machine routines are possible because of the limited distinct positions of the playing pieces. (At least the computer can calculate them).

Poggle update

OK, I found the references I wanted to prove that Poggle can be solved. It seems that this game was marketed under the name Merlin's Machine, Lights Out and Orbix. The obly difference it seems is that the neighbourhood of cells along the edge and corners of the game wrapp around to the other side. (Which should suggest ideas.)
The only issue is that this kind of problem has only been looked at using wrap-around neighbourhoods.

SoI need to apply a little mental knuckle-work.

Now I just need to read the chapter.

2006-04-28

Mu Torere, the AI II

Step 12.
Given all the de-allocation problems with CMoveGenerator as a Singleton, I decided to toss it over and just use a pointer within the Computer's move function (see update in last step.)

So there are only three functions that need to be constructed at this time, in addition to the constructor (which preps the RNG.) The public functions are the getMove(void) returning the CBoard location the Computer moves to and setGame(const CGame* data). The private function, randomMove(const COwner::Player& tag), just grabs an availible move at random. The decision tree part for the AI will be added later. This is enough to start play testing the program.

The only thing really unusual about the comstructor is that it requires an integer. This will be for the AI part.
The Constructor
CMoveGenerator::CMoveGenerator(const int& aiL)
Enforce limits on the chosen AI level.

If debugging, seed Random Number Generator with specific value.
Otherwise, use the value returned from time() as the seed.
In case this is new, the standard headers for doing this are time.h, math.h, and stdlib.h.

Updating the CMoveGenerator instance with the current game is straight forward.
void CMoveGenerator::setGame(const CGame* aGame)
Pre-Condition:
That aGame is valid.
Set private CGame variable to COPY aGame.
This point is one that is debatable. Just how much data is needed to determine the next move? Here the costs on system resources from multiple copies of the CGame object were balanced against the straight-forwardness of only one operation needed to list the possible moves.

The interface of getMove() allows the program to hide all the messy details of actually determing the next move.
int CMoveGenerator::getMove(void)
Call the private move generator for the Computer's move.
Post-Condition:
That the returned move is valid.


The only move generator right now is purely random (as much as a ccomputer can get anyway.)
int CMoveGenerator::randomMove(const COwner::Player& tag)
Allocate memory to store the possible moves.

Get the possible moves based on the store data.
Perform reality checks on data. (Not much to this one. The only biggie is the possiblity that this function is called when there are no moves left.)

Get a random possible move. I used a while loop (with an emergency limiter) to extract a non-CBoard::OFF_BOARD value.

Clean-up and return the move.

2006-04-24

Complaint, MS de-allocation.

Every once in a while the Microsoft compiler will complain when de-allocating memory. It seems that the guard space allocated along with that allocated by new has been altered. From comments within the provided code, the only other explaination for this is that the de-allocation is being done on the 'wrong' heap.

Solution? If your program breaks when de-allocating the same bit of memory over and over again (And I am NOT talking memory leaks.), the best work-around that I have found is to allocate an extra amount of memory for that 'problem' allocation to keep everyone happy.

2006-04-23

Mu Torere, moving the pieces II

Step 11.
Now the User and the Computer needs to move. An enumerated type lSelection needs to be created with Invalid, Valid, ComputerWon, and UserWon as values to allow for CGame to signal the Document.
AND, might as well do this now, a boolean flag needs to be added to the CGame class to denote that there are no more moves to do. This flag will need to be added to the various copying functions.

For the User the CGame adds the function
CGame::lSelection CGame::selectMove(const CPoint& point)
If the finished flag is true, then return a CGame::Invalid signal.

Get a pointer to the CBoard instance.
If this pointer is NULL, return CGame::Invalid.

If there is no valid selection from CBoard's whatIndex(), return CGame Invalid.
Otherwise,
Test the move. If not possible to move, return CGame::Invalid.
If moving is not possible, return CGame::Invalid.

If the User won, set the finished flag to true and return CGame::UserWon.

Get the move from the computer Move function.
ASSERT that this move is not CBoard::OFF_BOARD.

Move the Computer's piece.
ASSERT that this Move was possible.

If the Computer won, set the finished flag to true and return CGame::ComputerWon.

If nothing else, CGame::Valid.
I should point out the issue with the move. (As if you had not noticed.) If the User's move work but the Computer's did not, at this poin the only reasonable action is to exit the program, preffereably with some message to the user. Even then there must be a better way to handle this situation.
The only thing that I can think of is to use the Undo functionality to restore the game, and try again. (Either ask the user to re-do the move, or to loop a few times and THEN ask the user.)

The function for testing who won;
COwner::Player CGame::whoWon(void) const
If the emptyLoc is the center location (8), return COwner::playN.

Get the COwner::Player value of the side that owns the center.

Switch on the value in emptyLoc,
{
If either neighbouring array element (element 7 is next to element 0) is owned by the same side of the center, return that COwner::Player value.
}

Otherwise, just return COnwer::playN.


The function for testing the move;
bool CGame::canMove(const COwner::Player& tag, const int& fromLoc)const
Get the pointer to the CBoard instance.
Pre-Conditions:
That tag is either COwner::playC or COwner::playU.
That fromLoc is greater than or equal to 0 and less than CBoard::NUM_PLACES.
And that fromLoc is NOT equal to emptyLoc.
Get a pointer to the CBoard instance.

If the move from fromLoc to emptyLoc is NOT possible, return false.

Get the COwner::Player value of the opposing side.

If emptyLoc is the center location, test to see if one and / or the other neighbour of fromLoc is owned by the opposing side.
If this is the case, return true.
Otherwise, return false.

And if emptyLoc is NOT the center, return true.


And the function for the computer's move;
int CGame::computerMove(void) const
Get a pointer to the CMoveGenerator instance.
Allocate a CMoveGenerator instance.
Test pointer to see if it is valid.

Setup the MoveGenerator instance with the current CGame.

Get the move.
ASSERT that the move will not be CBoard::OFF_BOARD. (Actually done AFTER releasing the CMoveGenerator instance.)

Release Delete the CMoveGenerator instance.

Return the move


Update: Changed CMoveGenerator instance from Singleton instance to straight pointer allocation.

2006-04-22

Mu Torere, moving the pieces

(I neglected to post this before going on about the AI.)

There are two classes that have information that changes because pieces move. I will cover the user interaction part in the next post.

For the COwner class;
bool COwner::Move(const int& fromL, const int& toL)
Pre-Conditions:
That fromL is greater than 0 and less than CBoard::NUM_PLACES.
That toL is greater than 0 and less than CBoard::NUM_PLACES.
And that fromL is NOT equal to toL.
Get the element in Board's loc array that has the same value as fromL. Return false if this fails.

Then assign toL to this element.
Return true.


And for the CGame class;
bool CGame::Move(const COwner::Player& tag, const int& fromLoc)
Pre-Conditions:
That tag is either COwner::playC or COwner::playU.
That fromLoc is greater than 0 and less than CBoard::NUM_PLACES.
And that fromLoc is NOT equal to emptyLoc.
If tag was COwner::playC
{
If the Computer's Move routine succeeds
{
Change the owned array as appropriate.
Assign fromLoc to emptyLoc.

return true.
}
}
else
{
If the User's Move routine succeeds
{
Change the owned array as appropriate.
Assign fromLoc to emptyLoc.

return true.
}
}

If the program gets this far return false.

2006-04-20

Mu Torere, the AI!

Now we are cooking with gas! The only thing is that this will not be that elaborate, and for that matter the AI will not much more that an Random Number Generator in order to check the rest of hte system. But here goes.

First a few functions are needed to establish the ground work, specifically copy contructors and the like.
While 'friend' classes and functions could have been used, adding a CGame object or pointer directly to the CMoveGenerator allows for the contruction of building hypothetical moves, e.g. 'What Computer moves are availible if the User moved this way?' (And yeah, I do hear the eye-balls rolling at this point.)

So, for the COwner and CGame class the copy constructor looks like;
The Copy Constructor
CXxxxx::CXxxxx(const CXxxxx& obj)
: Copy initialization list
For each element in array, copy obj.array[element]

The '=' operator function works as follows;
The Equal Operator
const CXxxxx& CXxxxx::operator =(const CXxxxx &obj)
If this is NOT equal the address of obj (&obj)then
{
Copy obj's data members.

For each element in array, copy obj.array[element]
}

In anycase, return the object reffered to by this. (*this)
I really recommend reading a good book on C++ to find out WHY operator=() is declared in this manner.

And finally, a kluge to copy from pointers to objects for the CGame class. I went through a bit of hoop-jumping and pointer manipulation and massaging before settling on this to extract pointer data members to copy to temporary objects. (But then I do not know the complete ins-and-outs of C++.) Much like the operator=() function the only difference is that there is no need to return the object to which this reffers;
void setGame(CGame* aGame);
void setGame(const CGame* aGame); // overloaded to copy-from this
If this is NOT equal the address of aGame (&aGame)then
{
Copy aGame's data members.

For each element in array, copy aGame->array[element]
}


Note: that there is NO data validation. While this can be added, it might be better to do that in a separate step.

2006-04-19

Mu Torere, the Stone Singleton

Step 8.
A basic Singleton instance, all that is required of this class is to draw the playing pieces.
Why isn't this folded in with one of the other classes? The basic reason is that this class can be considered a working stub class. If need be, a different drawing routine can be substituted to draw 3-D playing pieces. Or a Sprite class can be used instead. Or the user can decide.

For drawing;
void CStone::Draw(CDC* pDC, const COLORREF& res, const CRect& rect)
Create a 2-pixel wide pen with the colour of the menu text, usu. black.
Create a solid bruch with the provided colour, res.

Select the pen and the brush into the drawing context.
Draw an Ellipse contained by rect.
Select the old pen and old brush back into the drawing context.
Note that all the needed information for drawing the piece is provided. Nothing is stored in the CStone instance.

Mu Torere, the Owner class

Step 9.
The COwner class has only 3 variable to track, and a couple of named constants. One variable res holds the colour for the pieces it manages, an integer array loc (with named constant NUM_PIECES) to store the location on the board, and a variable tagP indicating which side the object is on (using COwner's enumerated Player type).
A couple of in-line functions to get the CBoard and CStone instance are useful. The only in-line function that could be added is one setting the COwner object's colour. Just remember to check that the object has actually been set-up by looking for a proper value in tagP. (No need to colour an un-assigned COwner object.)

Aside from the drawing function, the only thing that needs adding is the set-up function for initalization and the reset function for new games.

The COwner constructor just initializes the class's variables to what are essentially don't-care / error values that will be corrected when the COwner objects are properly initialized. In this case, res and tagP are set to RGB(255,0,0) and COwner::playN, while all elements in loc are set to CBoard::OFF_BOARD.
All the destructor needs to do is to Release any CBoard and CStone instances.

The bare-bones void COwner::setUp(const COwner::Player& tag) just sets the COwner object's tagP variable (only if tag is COwner::playC or COwner::playU) and then calls the reSet() function.

The void COwner::reSet(void) initialization function does have a Pre-condition that the only tagP values are COwner::playC or COwner::playU. Aside from that, the loc array is now initalized for each side. As long as all pieces from the same side are adjoining, placement does not matter. In my program I initialized the User and Computer arrays so that the User had the two places on the left and the two places on the top of the playing field. (From all the examples that I have seen.) The center playing location remains empty.

For drawing;
void COwner::Draw(CDC* pDC)
PreConditions:
That pDC is not-NULL.
That the COwner object's tagP equals COwner::playC or COwner::playU.
That there is a valid (not-NULL) CBoard instance.
That there is a valid (not-NULL) CStone instance.
For each location in loc,
{
Get the board location's CRect.
DEBUG: Is the CRect not-empty (0,0,0,0)?
If the returned CRect is empty, skip this location.

Draw the CStone instance with the returned CRect and the COwner's res colour.
}


Step 10.
All that needs to be done to display the playing pieces is to;

A - Create private COwner objects in CGame for the Computer and the User.
B - Use the setUp() function for each object with the proper COwner::Player value for each.
C - Create an in-line function for CGame to set the colours for the COwner objects. My program set the colours for both COwner objects at the same time. You can try a different approach if you wish.
D - The CGame setColours() is called in the Document's constructor for the initial colour. The function is also called in each of the 'Change Colour' menu item actions.
E - Each COwner object is drawn after the CBoard instance in the CGame's drawing function.
F - (Optional.) A reset funtion can also be added to the CGame at this time, calling each of the COwner objects. This reset function is used in the Document's OnNewDocument(0 function.

Try running the program. The playing pieces should be of the colour that were specified, e.g. they should match the colours displayed in the CInfoDisplay legend. Also the pieces should be in the playing location that were programming in to the COwner reSet() function.

2006-04-18

Mu Torere, changing colours

Step 6.
Given that the program can display colours, might as well go ahead and show how to change those colours. But first, the menu
FileSettingsHelp
New gameUndo About Mu Torere...


  
ExitShow Colour Legend  
 
  
 Change Computer Colour...  
 Change User Colour...  
 
  
 AI LevelOff 
  
 
  Low 
  Medium 
  High 
  
 
  Custom AI Level... 


Step 7.
On changing the colour in the Document;
void CMuTorereDoc::OnSettingsChangeXxxx()
Create CColorDialog object.

Set dialog flags.
dlg.m_cc.Flags |= CC_FULLOPEN | CC_RGBINIT;
dlg.m_cc.rgbResult = ((CMuTorereApp*)AfxGetApp())->getColourXxxx();

If the colour dialog returns IDOK.
{
Set the game's colours.
Set the application's Xxxx colour.

Update View with colour hint.
}


In the View, the Update View function is as follows;
void CMuTorereView::OnUpdate(CView* /*pSender*/, LPARAM lHint, CObject* /*pHint*/)
If lHint equals the Document's colour hint.
{
Set the colours in the CInfoDisplay instance.
}

In all cases, Invalidate the window to re-draw.
In my program I set both the User and the Computer colours at the same time. For efficiency, a different hint from the Document should be used for each colour change.

The addition to the View's Draw function is minor (done after the game is drawn);
If the application's m_Display is true, draw the CInfoDisplay instance.

The CinfoDisplay is set up in the View constructor;
Go to the first element in the CInfoDisplay instance.

Add _T("Computer") and the application's computer colour to the first element.
Add _T("User") and the application's user colour the next element.

2006-04-17

Mu Torere, the Legend

The sole reason for the InfoDisplay class is to show to the user which colour belongs to which player. In this program, the class is draw directly on the window, over-lapping the playing field. If I ever figure out a way to allow a program to close a child modeless window, I'll post it but for now this is it.

A Singleton class, CInfoDisplay contains the following as variables;
variableinital valuecomment
static CString *labelsNULL 
static COLORREF *coloursNULL 
static CPoint topLeftCPoint(0,0)for positioning
static int counter0for the iterator
static int numLabel0 

There are some named constants used for spacing included as well as a limit to the number of array elements.

The functions that will be used are static CInfoDisplay* getInstance(const int& count) and static void Release(void) for the pattern (Note that getInstance requires a parameter), void Draw(CDC* pDC), CSize getLabelSize(CDC* pDC) const, static void First(void) (to reset counter to 0), bool setInfo(const CString& sLabel, const COLORREF& rgbColour), and bool setRGB(const int& index, const COLORREF& rgb). Also note that the setRGB() function requires a index. I would have been better not to depend on such things for synchronization.

Since the labels and the colours are in dynamic arrays, the destructor can be used for the clean-up.
destructor
CInfoDisplay::~CInfoDisplay(void)
If labels is not-NULL, delete it.
If colours is not-NULL, delete it.


The additional code in this class's getInstance involves creating the labels and colours arrays;
CInfoDisplay* CInfoDisplay::getInstance(const int& count)
Pre-condition;
That count is greater than 0.
If instance is NULL and count greater than 0
{
Create new CInfoDisplay and assign to instance.
(Strictly speaking if this fails, the function should return NULL.)

If count is greater than CInfoDisplay::MAX_LABELS, use CInfoDisplay::MAX_LABELS instead.

Try allocating CString[count] memory and assigning it to labels.

Try allocating COLORREF[count] memory and assigning it to colours.

If labels is not-NULL, assign _T(" ") to each element.
If colours is not_NULL, assign RGB(255,0,0), i.e. red, to each element.

Assign (0,0) to topLeft.
}

Return instance.

Note the use of _T() for the CString elements. This Microsoft macro handles the difference between UNICODE and ANSCII at compile-time.

For the iterator function;
bool CInfoDisplay::setInfo(const CString& sLabel, const COLORREF& rgbColour)
Pre-condition;
That instance is not-NULL.
That counter is greater or equal to 0 and less than numLabel.
That labels is not_NULL.
That colours is not-NULL.
If counter equals numLabel, then return false. // no more can be entered

Assign sLabel to labels[counter].
Assign rgbColour to colours[counter].

Increment counter.

Return true.


The index-based colour-setting function works as follows;
bool CInfoDisplay::setRGB(const int& index, const COLORREF& rgb)
Pre-condition;
That instance is not-NULL.
That colours is not-NULL.
That index is greater than or equal to 0 and less than numLabel.
Assign rgb to colours[index].

Return true.


The following function helps the program determine the size of all the text that will be drawn. For now mostly redundant, but if positioning the CInfoDisplay instance is being done it will allow the programmer to compensate for weirdness.
CSize CInfoDisplay::getLabelSize(CDC* pDC) const
Pre-condition;
That instance is not-NULL.
That numLabel is greater or equal to 0 and less than numLabel.
That labels is not_NULL.
That pDC is not-NULL.
Initialize the x and y values to return.

For each label,
{
Get the size of the text of the label. (via GetTextExtent())

If the label's x-extent is greater, assign the value to x.

If the label's y-extent is smaller than the rectangle used to display the colour (CInfoDisplay::CELL_SIZE)
{
Increment y by CInfoDisplay::CELL_SIZE.
}
else
{
Increment y by the label's y-extent.
}

If not at the last label
{
Increment y by CInfoDisplay::SPACING.
}

Return CSize(x,y).


Finally, for drawing the instance;
void CInfoDisplay::Draw(CDC* pDC)
Pre-condition;
That instance is not-NULL.
That labels is not_NULL.
That pDC is not-NULL.
Get the size of the text from getLabelSize().

Create a solid pen with the colour of the menu text.

Initialize dy with the BORDER value + PADDING value + topLeft.y.
For each label,
{
Draw the label.

Get the size of the label.
Adjust like the gatLabelSize() function.

Set up a square CELL_SIZE-by-CELL_SIZE separated from the label by SPACING.
Create a solid brush with the appropriate colour.
Draw the square.

Increment dv by the label height and by the SPACING.
}

Now draw the enclosing box. Remember that the box is reduced by the BORDER value, that topLeft positions the box, and that the box's width is expanded by SPACING and the colour display.

2006-04-16

Mu Torere, the Playing Board II

Step 4.
Once the Board class has been set-up, all that needs to be done is to pass the right values to the right functions in the View class. For the moment, create a Game class and two pass-through function for Draw(CDC* pDC) and getSize(void).
Note; if interested here are the in-line functions to specifically catch allocation errors wrt. Board class.
CBoard* getBoard(void)
Get pointer to CBoard instance.

ASSERT that pointer is not-NULL.

Return pointer.

All the second version of the getBoard() function is defined using const to allow the CGame's getSize() function to use it.

Step 5.
It is preferred to use similar pass-through functionality in the program's Document class. (With a private CGame variable.)

Step 6.
Since the View class's onDraw(CDC *pDC) only has one statement to be added, pDoc->Draw(pDC), we will go onto the OnInitialUpdate() function.
void CMuTorereView::OnInitialUpdate(void)
// from the development's' function wizard
Call CView::OnInitialUpdate().

Get the Board class's CSize from the Document.

Increase the retrieved size in the X direction by twice the window's frame.
Increase the retrieved size in the Y direction by the Window's frame + the height of the menu and the height of the titlebar.

Get the width of the desktop.
If the retrieved size is wider than the desktop, then limit the retrieved size's width.

Get the height of the desktop.
If the retrieved size is taller than the desktop, then limit the retrieved size's height.

AfxGetMainWnd()->SetWindowPos(NULL, 0, 0, tSz.cx, tSz.cy, SWP_NOMOVE |
SWP_NOZORDER);

Mu Torere, the Playing Board

Step 3,
As a starting point, the Board class is a good one. Once this class is set-up, the View can be set to right size and to draw. There are two of the class's functions right there, getSize(void) const const and Draw(CDC *pDC).

The Board class will use the Singleton pattern, so getInstance(void) and Release(void) will need to be added.
Other functions needed for the game are getPlace(const int&) const to return a rectangle for drawing playing pieces, whatIndex(const CPoint&) const for determining valid mouse clicks, and canMove(const int& from, const int& to) const for checking for valid neighbours.

In addition to the Singleton's instance, the Board class also needs an array for the program's playable CRect's, places[CBoard::NUM_PLACES].
The named constants are OFF_BOARD = -1 (a public constant, not really needed in the Board class but a habit), NUM_PLACES = 9 (private, used for readability), and BORDER = 20 (private).

Now all of the numbers used in this class were determined by hand because of the general awkwardness of calculating the positions of the 8 points of the star plus the indents. (Actually I use a positioning kluge to come up with the right numbers, but I will not subject the readers to that mess.)


Constructor
CBoard::CBoard(void)
places[0].SetRect(80,20,130,70);
places[1].SetRect(160,20,210,70);
places[2].SetRect(220,95,270,145);
places[3].SetRect(220,180,270,230);
places[4].SetRect(160,250,210,300);
places[5].SetRect(80,250,130,300);
places[6].SetRect(20,180,70,230);
places[7].SetRect(20,95,70,145);
places[8].SetRect(120,130,175,185);


For the Singleton pattern;

CBoard* CBoard::getInstance(void)
Is instance NULL?
{
Try allocating new CBoard instance.

If allocation fails, set instance to NULL.
}
Return instance.


void CBoard::Release(void)
Is instance not-NULL?
{
Delete instance.

Set instance to NULL.
}


For the View;
CSize CBoard::getSize(void) const
Pre-Condition:
instance is not-NULL.
Is Return CSize(right-most point+CBoard::BORDER,bottom-most point+CBoard::BORDER)


void CBoard::Draw(CDC* pDC)
Pre-Condition:
instance is not-NULL.
Create a solid brush with the colour of the window's background.
Create a pen with the colour of the menu's text.
(This should provide enough contrast.)

Select into drawing context the pen and brush.

Draw a circle in the rectangle given by place[8].

Move to center of place[0].
Draw line to (145,95).
Draw line to center of places[1].
Draw line to (185,120).
Draw line to center of places[2].
Draw line to (205,160).
Draw line to center of places[3].
Draw line to (185,205).
Draw line to center of places[4]
Draw line to (145,230).
Draw line to center of places[5].
Draw line to (105,205).
Draw line to center of places[6].
Draw line to (90,160).
Draw line to center of places[7].
Draw line to (105,120).
Draw line to center of places[0].

Select into drawing context the old pen and brush.

Note: As an alternative playing field, a 8-spoked wheel can also be draw. Just draw the center last to keep it from being over-drawn.

2006-04-15

Mu Torere, the Application I

Step 2.
Again the Application class will be used for storing the session values. The values stored, private, will be 'int m_AI' for the AI level, 'int m_Undo' for the number of Undo's, 'COLORREF m_Computer', 'COLORREF m_User', and 'bool m_Display' for showing the playing piece display.
Since these are private variables, you will need to add get/set accessor functions (inline) to the Application classes. The only exception would be for the m_Undo variable, only a get function is needed as the user will NOT be able to adjust this during the game. (If the user is feeling ambitious, he/she can go into the registry to change this value.)

Mu Torere, the Set Up

The basic set-up of this program will be Microsoft's View-Document model, as I wrote earlier.

Not much in the way a frills are needed, though I would recommend using the static MFC libraries. After all, passing on your program to friends only to find out it woun't run from the lack of the proper libraries is not a good thing. (This will also happen as your developement libraries become outdated.)

Again, in the Mainframe class's PreCreateWindow(), the 'FWS_ADDTOTITLE' style needs removal.

PS. There was an additional class I neglected to mention last time, CInfoDisplay. This class is more an aid to memory for the user as there is no easy way to tell the playing pieces apart except for the colour. If you prefer you can mark the playing pieces appropriately, but follow along for now.

2006-04-13

Allocating memory and further thoughts on the Singleton Pattern

In all earnest, allocating memory is a prime case of "Damn'd if you do, and damn'd if you do not." On one hand, you spend time programming allocation checking for a 200 K-byte utility that will be the only thing running on a system with 2 G-bytes of RAM. On the other hand, you find out the hard way about the lack such checks when the utility recursively takes over the system's memory during the demo before the boss and very important clients 2 and 3.

The current standards for C++ require that the new operator throws a bad_alloc exception when things go wrong during memory allocation. Compilers can be made aware of this exception by including the 'new' header file while 'using namespace std;' (Sorry, angle brackets are still awkward under Blogger.)
Thus;
bool Setup(void)
{
int *fields;

try{

fields = new int[NUM_RECORDS];

}
catch(bad_alloc e){

return false;

}

// do something

return true;

}

This will allow the program to fail nicely and handle the situation, without crashing the system.

PS. C++ also allows new NOT to throw an exception, but the only reason I can see for this is to allow new to be used in constructors. But I could be wrong.

With respect to Singletons, this means that the Singleton instance can be allowed to fail (return NULL) in case of memory issues. The other side to this is that these kind of memory failures need to be handled as well.Take a look at how Microsoft handles the situation in its View-Documents architecture.
In Release executables, the View uses an inline GetDocument() function that returns a Document pointer that is re-cast into a pointer of the program's specific Document class. In Debug executables, this GetDocument() function first ASSERTs that the program's Document is correctly derived before returning the pointer.

The only cause for concern that might spring up is that when using a Singleton instance in serveral different classes, what happens to version control?

2006-04-12

Smeg. Smeg. Smeg!

My Tablet PC is screwing up. Which should not be an issue except for the fact that I have all my projects stored on it.

I really hope that all that needs doing is to update a driver.

2006-04-11

Mu Torere Steps

Next Game
Mu Torere Classes
Mu Torere, the Set Up
Mu Torere, the Application I
Mu Torere, the Playing Board
Mu Torere, the Playing Board II
Mu Torere, the Legend
Mu Torere, changing colours
Mu Torere, the Owner class
Mu Torere, the Stone Singleton
Mu Torere, the AI!
Mu Torere, moving the pieces
Mu Torere, moving the pieces II
Mu Torere, the AI II
Mu Torere AI, again.
Mu Torere, a digression
Mu Torere, Undo
Mu Torere, Undo II
Mu Torere AI II
Mu Torere, setting the AI
Mu Torere, the rest of the story
Mu Torere, the Final test
Mu Torere, Improvements

I see that I will need to go back and re-do the titles.

Mu Torere Classes

A quick run down of the classes

Microsoft classes

View class (Drawing the game)

Application class (Storing the session values in the registry)

Document class (Managing the game)
Game class (Bookkeeping for the game and its sub-components)

Board class (Singleton instance of the playing field)

Owner class (Bookkeeping for the players)


Stone class (Singleton instance for the playing pieces)

Undo class (Derived from)


Circular Queue class

Move Generator class (Singleton, Determines the next move)


k-Tree class (Helper class for the program's best move tree)

2006-04-10

Simple Blocking Game

The game with a solid lock on being the simplest game in history is widespread though out Asia. A sample of the names by which it is known (from Parlett); Do-guti (India), Pong Hau K'i (China), On-moul-ko-no (Korea), Sua tok (Thailand).

The playing field can be thought of as a diagonally crossed square with one side removed. Movement is along the lines as show in the figure. (At the risk of pointing out the obvious, the playable locations are the four corners of the square and the center.)



Pong Hau K'i

Players move their pieces alternately to the empty point until one player cannot move. The player that cannot move loses.

An alternate way to start that is mentioned by R.C. Bell is that the players alternate placing their pieces onto the field before starting to move.

2006-04-09

Next Game

The next game that will be made in to a program is Mu Torere, a straight forward blocking game played by the Maori of New Zealand.

It is played on a eight pointed star with the star's center as the ninth playable location. Each player has four pieces and the movement rules are simple enough.
- a Piece can move from the center to an empty star point.
- a Piece can move from a star point to a neighbouring start point.
- a Piece can move from a star point to the empty star center ONLY IF one or both of the neighboouring points are occupied by Pieces belonging to the opposing player.
- in the program, the User will go first. Letting the Computer play first is an option.

A Player loses if there is no possible move availible.

on Poggle

First Example
The Name of the Game is Poggle
Poggle Patterns
After adding the Board Class
What type data members for static instance?
On Menu actions
View Class Update I
View Class Update II
Clicking on Poggle
The Big part of Poggle
Drawing Re-visited
Poggle, Is this thing on?
Poggle, Working with the Registry
Final Exam for Poggle
Some ideas for upgrading Poggle

Now all I need to do is to go back and gammar check my posts.

2006-04-07

Some ideas for upgrading the Poggle executable.

Idea 1:
Localization for other languages.

There are only two places where this would need to be done. The menu is one, the other is the Message to the user annoucing that the puzzle is solved. Most of the material that I have read on the subject recommend to use the String table in the resources to store the message and menu strings the user will read, one String table per language.
One solution that came up is to use resource DLLs. See the following page at CodeGuru for further information.

Idea 2:
Accessibility.

First off, what changes would need to be made where the mouse cannot be used? The program then needs to handle keyboard input. Which keys will be used for pointing? for selecting the pointed to cell? Can the User change these input keys?
Also, how will the selection be highlighted? One way would be to manipulate the cursor so that it will point to the proper cell as the user uses the keyboard. Another would be to change the display to make the selected cell stand out.

As this program is visual in nature, how can vision issues be addressed. In addition to blindness, there is colour-blindness. Should the user be allowed to adjust the colours? make them mono-chrome?

Idea 3:
Solutions.

There is a very good chance that users will complain about the puzzles being impossible to solve. So the solutions need to be documented. How about automating the process?

2006-04-05

Final Exam for Poggle

Now that the program was coded and all the syntax errors have been fixed, the time has come to do all the finishing touches for the program.

A formal and complete test schedule will not be described. This would mean listing out ALL the "if .. [else if ..] then" staments in all coded routines and creating scenerios to trigger them. The test set that will be described should be inclusive enough.

Note all of the following should be done using the Debug version of the program. This will allow the compiler's debugger to display the proper information.

Round 1.
- Does the program start?
- Are all expected menu item accessible?
- Does the Help menu work?
- Does the program exit cleanly?

For the first round that is all that is needed. The user interface and starting/stopping the program is checked at this point.
If the Program does not start, the initialization need to be checked. If a three finger salute is needed to halt the program, the clean-up needs to be examined. And the program's resources need to be examined if the menu is not correct.

One final point to make here is that now is the time to start looking for memory leaks. If one is found, it needs addressing immediately. Usually, this will also get a majority of the memory problems that would otherwise pop up later.

Round 2.
- Using the basic options, does the game detect mouse clicks? valid ones? invalid ones?
- Using the basic options, does the game process the user's selections properly? Click each cell twice to address the following questions.
- - Using the basic options, do the cells switch colours (black and white here) correctly?
- - Using the basic options, do the correct neighbouring cells change state?
- Using the basic options, does the game detect the winning condition? What happends when the program gets mouse clicks after this point?
- Finally, using the basic options, does the 'New Game' menu item return the game to its starting position?
- Exit and look for memory leaks again.

Round 3 through N.
Much of the same questions are asked for each game option. Additionally;
- Do the game settings menu items change the game?
- - Is the number of cells correct? Is it drawn correctly?
- - Do the cells cycle through the correct colours? Every time?

Now once the winning condition has been tested for the basic game, I did not test for it to happen with the other versions. If you get a win, more power to ya.

Once the program was tested, memory leaks fixed, and debugged, the program can be compiled again for Release, i.e. optimized.

Cheers

2006-04-03

How about that.

I am 9% Idiot.
Friggin Genius
I am not annoying at all. In fact most people come to me for advice. Of course they annoy the hell out of me. But what can I do? I am smarter than most people.

Officially ...

I did not want to get caught up in all the 'April Fools' posting.

Unofficially, I was too bleep-ing lazy to actually log on.