C ONLY PLEASE Write a function that converts strings containing base-3 numbers t
ID: 3880361 • Letter: C
Question
C ONLY PLEASE
Write a function that converts strings containing base-3 numbers to their integer equivalent as an unsigned short integer:
unsigned short b3tous( char b3[10] );
Write a function that works the other way, converting unsigned short integers to null terminated strings of the characters ‘0’, ‘1’, and ‘2’.
void b3fromus( char b3[10], unsigned short us );
Boards
Consider the following depiction of a tic-tac-toe board:
X | O |
---+---+---
| |
---+---+---
| |
This board is represented by the 60 character C string:
“ X | O | ---+---+--- | | ---+---+--- | | “
If we consider the Xs to be represented by 2s and the Os by 1s and the blank spaces by 0s. We can encode the board above by the base-3 number 210000000(3) which is equal to 15,309.
Write a function that converts the C string board representation to a base-3 string:
void boardtob3( char b3[10], char board[60] );
and a function that converts the base-3 string representation back into a C string board:
void boardfromb3( char board[60], char b3[10] );
TicTacToe Basics
Next, you will write a function that takes a board in unsigned short (us) format and determines who the winner of the board is. I.e. if there are three Xs in a row, column or diagonal, then X has won, and your function should return the value ‘2’ (not 2). Similarly, for O, it should return the value ‘1’ (not 1). Note that it is possible to create boards where both X and O win at the same time, e.g. 222000111(3), but these boards will not occur in a real game, so you are not required to worry about this case (we will not test your function which boards that cannot occur). Hint, feel free to use the b3fromus function that you created above to convert the unsigned short into a representation where you can more easily determine a winner.
char winner( unsigned short us );
Next, you will write a function that determines what the next board looks like if a player places their symbol in a given position. Position 0, is the top left, 1 is the top middle, 2 is top right, 3 is middle left, …, 8 is bottom right. If there is already a piece in the given position your function should return the value 0. Note that this function also uses the unsigned short representation, but you can convert to and from b3 inside your function to make it easier.
unsigned short next ( unsigned short us, char pos );
For example, if us is 100020000(3), and pos is 6, then the return value should be 100020200(3). But if pos is 0, then the return value should be 000000000(3). You don’t need to worry about the case where a player has already won the game.
Now, you will write a function that will return an integer indicating what move of the game it is. A move consists of one action by one player. The first move is 0, the next move is 1, etc., so you can just count the number of pieces on the board.
char get_move( char b3[10] );
Finally, you will write a function that will return a character indicating whose turn is it. ‘2’ means X’s turn, ‘1’ means O’s turn.
char get_turn( char b3[10] );
IMPORTANT: Save all of these functions in a file called “tictactoe.c”, and create a “tictactoe.h” header file to accompany it.
Program 1:
Write a program called “a1p1.c” that takes a single command line argument representing an integer board number (us format) and prints out the following information:
Or:
In these examples, the line “Winner: ” has a space after the colon and then another character. The character that goes after the space is:
‘2’ if X has won the game,
‘1’ if O has won the game,
‘0’ if the game ended in a tie, and
‘ ’ (space) if the game is incomplete (in this case there will be two spaces on the line).
The numbers after the arrows represent the next boards in 'us' format for that move. E.g. in the last example, it is not possible to move into square 0 (top-left). Moving to square 1 (top-middle), takes you to board 9908, etc.
Program 2:
Write a second program that writes a binary file, named “strategyfile”, consisting of exactly 39366 bytes. This file should contain 19683 2-byte records. Each record will encode the following structure for every possible tic-tac-toe board in order for us=0 to us=19682:
struct strategy_struct
{
char best_move;
char winner;
};
For now, set best_move to -1 and set the value of winner to ‘ ’ (blank space).
Program 3:
Write a third program that takes an integer command-line argument representing the move number and loops over all possible boards. When it finds a board that matches the move number, the program should determine if someone is the winner (according to the winner function you wrote earlier). If the game is a win, loss or tie (‘2’, ‘1’, or ‘0’), it should set the “winner” value in the strategy_struct variable to that value, set the “best_move” value to -1, and save the structure in the appropriate position in the binary file.
If the game is undetermined (the winner function returns ‘ ’ (blank space)), then your program should look at all the possible moves that can be made and look at the winner value stored in the file for each of the resulting boards. It should then do the following:
If there is a move that leads to a board whose “winner” value matches the current player’s “turn” (i.e. the current player can make a winning move), then set the winner value in the strategy_struct variable to the current player and set the “best_move” to whatever move led to that board.
If there is no winning move, but there is a tying move, then set the winner value in the strategy_struct to ‘0’ (tie) and set the “best_move” to whatever move led to that board.
If there are no winning moves, and no tying moves, then set the winner value to the opponent’s character and set the “best_move” to the last (highest numbered) legal move.
Run your program with the command line argument set to 9, 8, 7, 6, 5, 4, 3, 2, 1, 0. At this point your program will have mastered the game of tic-tac-toe and incorporated its body of knowledge in the “strategyfile”.
Program 4
Review the program that you created in a1p1.c and create a new program called a1p4.c that also displays the winner and best_move values from the strategyfile for each board as follows:
and,
Program 5
For the final program, a1p5.c, create a tic-tac-toe player that operates as follows. User input is indicated in RED:
SHALL WE PLAY A GAME?
PLEASE ENTER YOUR NAME: PROFESSOR FALKEN
GREETINGS PROFESSOR FALKEN
Which side would you like to play (X/O)? O
Ok, you will be O; I will be X.
My turn; my move is 0:
Your turn; chose a move [0-8]: 1
My turn; my move is 3:
Your turn; chose a move [0-8]: 6
My turn; my move is 4:
Your turn; chose a move [0-8]: 8
My turn; my move is 5:
I won!
A STRANGE GAME.
THE ONLY WINNING MOVE IS
NOT TO PLAY.
Make sure your spelling, punctuation and spaces matches the example above exactly.
Explanation / Answer
#include "TicTacToe.h"
/*This is a testing file for testing the functions*/
int main()
{
char b3[10] = {0};
char board[60] = {0};
u16 us = 0;
b3fromus(b3, 9);
printf("%s = %d ", b3, b3tous(b3));
b3fromus(b3, 210);
printf("%s = %d ", b3, b3tous(b3));
b3fromus(b3, 304);
printf("%s = %d ", b3, b3tous(b3));
b3fromus(b3, 1234);
printf("us=1234; %s = %d ", b3, b3tous(b3));
printf(" ");
boardtob3(b3, " X | O | ---+---+--- | | ---+---+--- | | ");
printf("%s ", b3);
boardfromb3(board, b3);
printf("%s ", board);
printf(" ");
boardtob3(b3, " X | O | ---+---+--- | O | X ---+---+--- | X | ");
printf("%s ", b3);
boardfromb3(board, b3);
printf("%s ", board);
printf(" ");
boardfromb3(board, "101010122");
printf("%s ", board);
printf("Winner: %c ", winner(b3tous("101010122")));
printf(" ");
strcpy(b3, "100002020");
boardfromb3(board, b3);
printf("%s ", board);
us = next(b3tous(b3), 3);
boardfromus(board, us);
printf("%s ", board);
printf(" ");
printf("turn = %c[char] ", get_turn("210020000"));
printf(" ");
printf("Pow(3,6)=%d ",ipow(3,6));
return 0;
}
---------------------------------------------------------------------------------------
TicTacToe.c
---------------------------------------------
#include "TicTacToe.h"
/*Used in the next and b3atpos function, where it is only called once; therefore not too wasteful*/
int ipow(int b, u16 e)
{
int result = 1;
u16 i;
/*Redundant since for e==0; result is already 1 and loop wont execute*/
/*if (e == 0)
{
return 1;
}*/
for (i = 0; i < e; i++, result*=b);
return result;
}
u16 b3tous(char b3[10])
{
u16 value = 0;
u16 placeValue = 1;
u8 i = 0;
/*Go through every space on the board, starting from the lowest place value
The loop condition is "i<9" because after i is 0, i will wrap around to 255*/
for (i = 8; i < 9; i--)
{
/*convert b3 to a number value, then multiply it by it's place value*/
value += (b3[i] - '0') * placeValue;
placeValue *= 3;
}
return value;
}
void b3fromus(char b3[10], u16 us)
{
/*u16 placeValue = 3*3*3 * 3*3*3 * 3*3;*/
u8 i;
/*Start at lowest place value and itterate towards the highest place value*/
for (i = 8; i < 9; i--)
{
/*Old Algorithm:
divide us by the place value, then convert to a character
Uses integer math to only get the integer number for the current place value*/
/*b3[i] = (us / (placeValue)) + '0';*/
/*update us by subtracting the value of b3 at the current place value*/
/*us -= (b3[i] - '0') * placeValue;*/
/*placeValue /= 3;*/
/*Calculate the b3 value for each place value in order from lowest to highest*/
b3[i] = (us % 3) + '0';
us /= 3;
}
}
/*readded and maked use of ipow function*/
u8 b3atpos(u16 us, u8 pos)
{
/*directly returns the b3 value at a place value*/
return (us / (u8)ipow(3,pos)) % 3;
}
void boardtob3(char b3[10], char board[60])
{
u8 i;
/*set the end of the array to a null character*/
b3[9] = '';
for (i = 0; i < 9; i++)
{
/*The math converts i from range [0,8] to the indices of each piece on the grid.
The first part of the calculation handles accessing the columns, and the second
skips over the rows where there are no pieces.*/
char piece = board[i*4 + 1 + 12*(i/3)];
/*Set the number character in b3 based on the piece character
'X'->'2' 'O'->'1' ' '->'0'*/
b3[i] = (piece == 'X' ? '2' : (piece == 'O' ? '1' : '0'));
}
}
/*wrapper for boardtob3 to automatically convert back to us*/
u16 boardtous(char board[60])
{
char b3[10];
boardtob3(b3, board);
return b3tous(b3);
}
void boardfromb3(char board[60], char b3[10])
{
u8 i;
/*Fill the board with an empty grid. The board is populated in the next step*/
strcpy(board, " | | ---+---+--- | | ---+---+--- | | ");
/*populate the board. Go through every position on the board; i in range [0,8]*/
for (i = 0; i < 9; i++)
{
/*The math converts i from range [0,8] to the indices of each piece on the grid.
The first part of the calculation handles accessing the columns, and the second
skips over the rows where there are no pieces.
Sets the piece character based on the number character.
'2'->'X' '1'->'O' '0'->' '*/
board[i*4 + 1 + 12*(i/3)] = (b3[i] == '2' ? 'X' : (b3[i] == '1' ? 'O' : ' '));
}
}
/*wrapper for boardfromus to allow using us as a parameter*/
void boardfromus(char board[60], u16 us)
{
char b3[10];
b3fromus(b3, us);
boardfromb3(board, b3);
}
/*Prints out the state of the board*/
void printBoardb3(char b3[10])
{
char board[60];
boardfromb3(board, b3);
printf("%s ", board);
}
/*wrapper for printBoardb3 to allow using us as a parameter*/
void printBoardus(u16 us)
{
char b3[10];
b3fromus(b3, us);
printBoardb3(b3);
}
char winner(u16 us)
{
char b3[10];
/*Binary 0b11. This algorithms uses binary arithmitic so it is useful to think of 3 in this way
row0, row1, row2, col0, col1, col2, diagonal1, diagonal2*/
u8 win[8] = {3,3,3,3,3,3,3,3};
u8 i;
b3fromus(b3, us);
/*Go once through*/
for (i = 0; i < 9; i++)
{
/*Convert each b3 value to a number value (0->2), from a char.
This also means that the value becomes one of 0b00, 0b01, 0b10.*/
b3[i] = b3[i] - '0';
/*Theory of algorithm:
Calculates if all in each row, column, or diangonal are all the same.
This is done using '&' operations. If there is a line of 3 of the same piece,
then the corresponding value in the array will be non-zero. If there is any
non-zero values in the array, then there is a winner. A value of 0b01 is 'O'
and a value of 0b10 is 'X'. 0b11 is possible, but the board will never be reached*/
win[i / 3] &= b3[i]; /*Calculate for rows*/
win[(i % 3) + 3] &= b3[i]; /*Calculate for columns*/
win[6] &= (i % 4 == 0 ? b3[i] : 3); /*Calculate for the first diagonal*/
win[7] &= (i == 2 || i == 4 || i == 6 ? b3[i] : 3); /*calculate for the seccond diagonal*/
/*Removed; Simplified into previous two lines of code*/
/*if (i % 4 == 0) (i == 0 || i == 4 || i == 8)
{
win[6] &= b3[i];
}
if (i == 2 || i == 4 || i == 6)
{
win[7] &= b3[i];
}*/
}
/*OR all the values together and store in the first array value, so that the
array can be tested for non-zero values easily*/
for (i = 1; i < 8; i++)
{
win[0] |= win[i];
}
/*If win[0] has 0b10, then 'X' won, if win[0] has 0b01, then 'O' won. else nobody one.
0b11 is not going to occur in regular use. Returns '2'for this case*/
return (win[0] & 2 ? '2' : (win[0] & 1 ? '1' : ' '));
}
u16 next(u16 us, char pos)
{
char b3[10];
b3fromus(b3, us);
/*Check if there is no peice at the location pos*/
if (b3[(int)pos] == '0')
{
/*Add the place value of the move to us.
This operates the same as the get_turn function. The piece number is then
multiplied by the place value. Note: could use get turn, but this calculation
is faster and doesnt need to convert back from a char*/
return us + (2-(get_move(b3)%2)) * ipow(3,8-pos);
}
return 0;
}
char get_move(char b3[10])
{
u8 i;
char count = 0;
/*Count the number of non-zero values in b3*/
for (i = 0; i < 9; i++)
{
count += !!(b3[i] - '0'); /* "!!" coverts the value to either 1 or 0*/
}
return count;
}
/*wrapper for get_move to allow using us as a parameter*/
char get_move_us(u16 us)
{
char b3[10];
b3fromus(b3, us);
return get_move(b3);
}
char get_turn(char b3[10])
{
/*get_move is used to determine what piece. This is calulated by seeing what
the move number is and assuming X plays first. Therefore if the move is
divisible by 2, the move is '2'*/
return (get_move(b3) % 2 == 0 ? '2' : '1');
}
/*wrapper for get_turn to allow using us as a parameter*/
char get_turn_us(u16 us)
{
char b3[10];
b3fromus(b3, us);
return get_turn(b3);
}
char get_next_turn(char b3[10])
{
/*Uses get_turn, but inverts the answer*/
return (get_turn(b3) == '1' ? '2' : '1');
}
/*wrapper for get_next_turn to allow using us as a parameter*/
char get_next_turn_us(u16 us)
{
char b3[10];
b3fromus(b3, us);
return get_next_turn(b3);
}
/*Opens strategy file and stores it into buf*/
void readStrategyFile(void *buf)
{
FILE *file = fopen( "strategyfile", "rb" ); /*Binary Format*/
fread(buf, sizeof(strategy), NUMBOARD, file); /*Reads NUMBOARD strategy structs*/
fclose(file);
}
/*Opens strategy file and writes buf to the file*/
void writeStrategyFile(void *buf)
{
FILE *file = fopen( "strategyfile", "wb" ); /*Binary Format*/
fwrite(buf, sizeof(strategy), NUMBOARD, file); /*Writes NUMBOARD strategy structs*/
fclose(file);
}
-----------------------------------------------------------------------------------------------
TicTacToe.h
------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define NUMBOARD 19683 /*equal to pow(3,9)*/
/*These types are used constantly; easier to read and type shortforms*/
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
typedef struct strategy_struct
{
char best_move;
char winner;
} strategy;
int ipow(int b, u16 e);
u16 b3tous(char b3[10]);
void b3fromus(char b3[10], u16 us);
u8 b3atpos(u16 us, u8 pos); /*additional*/
void boardtob3(char b3[10], char board[60]);
u16 boardtous(char board[60]); /*additional*/
void boardfromb3(char board[60], char b3[10]);
void boardfromus(char board[60], u16 us); /*additional*/
void printBoardb3(char b3[10]); /*additional*/
void printBoardus(u16 us); /*additional*/
char winner(u16 us);
u16 next(u16 us, char pos);
char get_move(char b3[10]);
char get_move_us(u16 us); /*additional*/
char get_turn(char b3[10]);
char get_turn_us(u16 us); /*additional*/
char get_next_turn(char b3[10]); /*additional*/
char get_next_turn_us(u16 us); /*additional*/
void readStrategyFile(void *buf); /*additional*/
void writeStrategyFile(void *buf); /*additional*/
-----------------------------------------------------------------------------------------------------
a1p1.c
---------------------------------
#include "TicTacToe.h"
int main(int argc, char **argv)
{
/*Initilize Vars*/
u16 us, i;
char b3[10];
char board[60];
/*Ensure that an argument has been supplied*/
if (argc < 2)
{
printf("Error:: no argument supplied ");
return 1;
}
/*Calculate information about the board*/
us = atoi(argv[1]);
b3fromus(b3, us);
boardfromb3(board, b3);
/*print board information*/
printf("Board number: %d ", us);
printf("Board b3: %s ", b3);
printf("Board pic: %s ", board); /*Using printBoardb3 would require an extra print statement for new lines*/
printf("Move: %d ", get_move(b3));
printf("Turn: %c ", get_turn(b3));
printf("Winner: %c ", winner(us));
/*print next possible moves*/
for (i = 0; i < 9; i++)
{
printf("%d -> %d ", i, next(us, i));
}
return 0;
}
-------------------------------------------------------------
a1p2.c
------------------------
#include "TicTacToe.h"
int main()
{
u16 i;
FILE *file;
/*Open the strategy file for writing*/
file = fopen( "strategyfile", "wb" );
/*Put the default data in the file by repeatidly adding characters*/
for (i = 0; i < NUMBOARD; i++)
{
fputc(-1, file);/*best_move*/
fputc(' ', file);/*winner*/
}
fclose(file);
return 0;
-----------------------------------------------------------------
a1p3.c
-----------------------
#include "TicTacToe.h"
int main(int argc, char **argv)
{
u8 move;
u16 us;
/*char b3[10];
char board[60];*/
strategy strategyBuf[NUMBOARD];
/*char playerWin;*/
/*Ensure that an argument has been supplied*/
if (argc < 2)
{
printf("Error:: no argument supplied ");
return 1;
}
move = atoi(argv[1]);
/*Open the current Strategy File; this allows all previously entries to be
kept, and allows fast and easy access to the contents since it is storred
in ram and can be accessed with an array*/
readStrategyFile(strategyBuf);
for (us = 0; us < NUMBOARD; us++)
{
/*Only Consider boards that are on selected move*/
if (get_move_us(us) == move)
{
char playerWin = winner(us);
/*printf("%d: ", us);*/
/*Test if a player won*/
if (playerWin != ' ')
{
/*Winner is player that won, no next move*/
strategyBuf[us].winner = playerWin;
strategyBuf[us].best_move = -1;
/*printf("Winning Board ");*/
}
else /*No winner on current move*/
{
u8 i = 0;/*, move = 0, highestMove = 0;*/
/*Loop 9*3 times. The 9 is for 9 possible moves. The 3 is for the 3
strategy cases. Doing it this way save on having a loop for each of
the 3 conditions and additional flow control*/
for (i = 0; i < 9*3; i++)
{
/*Retrieve move number from i. (goes from 0->8 3 times)*/
u8 move = i%9;
u16 nextBoard = next(us, move);
/*next Move that leads to winner*/
if (i/9 == 0 && strategyBuf[nextBoard].winner == get_turn_us(us))
{
/*Winner is current player, best move is current move being examined*/
strategyBuf[us].winner = get_turn_us(us);
strategyBuf[us].best_move = move + '0';
i = 9*3;/*Exit back to us loop; stop evaluating the stratagy for current board*/
/*printf("Winning Move ");*/
}
/*next Move that leads to a tie;*/
if (i/9 == 1 && (strategyBuf[nextBoard].winner == '0' || get_move_us(nextBoard) == 9))
{
/*Winner is nobody, best move is current move being examined*/
strategyBuf[us].winner = '0';
strategyBuf[us].best_move = move + '0';
i = 9*3;/*Exit back to us loop; stop evaluating the stratagy for current board*/
/*printf("Tieing Move ");*/
}
/*no winning strategy; next move is highest us value; select the first valid move*/
if (i/9 == 2 && nextBoard != 0)
{
/*Winner is other player, best move is current move being examined*/
strategyBuf[us].winner = get_next_turn_us(us);
strategyBuf[us].best_move = move + '0';
i = 9*3;/*Exit back to us loop; stop evaluating the stratagy for current board*/
/*printf("Loosing Move ");*/
}
}/*End i loop*/
}
}/*End board select*/
}/*End us loop*/
/*Save the new calculated Strategy File*/
writeStrategyFile(strategyBuf);
return 0;
}
--------------------------------------------------------------------------------
a1p4.c
-------------------
#include "TicTacToe.h"
int main(int argc, char **argv)
{
/*Initilize Vars*/
u16 us, i;
char b3[10];
char board[60];
strategy strategyBuf[NUMBOARD];
/*Ensure that an argument has been supplied*/
if (argc < 2)
{
printf("Error:: no argument supplied ");
return 1;
}
/*Calculate information about the board*/
us = atoi(argv[1]);
b3fromus(b3, us);
boardfromb3(board, b3);
/*print board information*/
printf("Board number: %d ", us);
printf("Board b3: %s ", b3);
printf("Board pic: %s ", board); /*Using printBoardb3 would require an extra print statement for new lines*/
printf("Move: %d ", get_move(b3));
printf("Turn: %c ", get_turn(b3));
printf("Winner: %c ", winner(us));
/*Open strategy file and read information*/
readStrategyFile(strategyBuf);
printf("best_move=%c, winner=%c ", strategyBuf[us].best_move, strategyBuf[us].winner);
/*print next possible moves*/
for (i = 0; i < 9; i++)
{
printf("%d -> %d ", i, next(us, i));
}
return 0;
}
------------------------------------------------------------------------------
a1p5.c
-----------------------------
#include "TicTacToe.h"
int main()
{
/*
SHALL WE PLAY A GAME?
PLEASE ENTER YOUR NAME: ABC
GREETINGS ABC
Which side would you like to play (X/O)? O
Ok, you will be O; I will be X.
*/
char name[21];
char playerPiece;
u8 turn = 0, play = 1;
u16 board = 0;
strategy strategyBuf[NUMBOARD];
readStrategyFile(strategyBuf);
/*Initial Prompt*/
printf("SHALL WE PLAY A GAME? PLEASE ENTER YOUR NAME: ");
fgets(name, 20, stdin); /*Get name, Including space*/
printf("GREETINGS %s ", name);
printf("Which side would you like to play (X/O)? ");
scanf("%c", &playerPiece); /*Get selected Player Piece*/
printf("Ok, you will be %c; I will be %c. ", playerPiece, playerPiece == 'O' ? 'X' : 'O');
/*Set which player goes first; whoever is X always playes first*/
turn = (playerPiece == 'X' ? 1 : 0);
printBoardus(board);
while (play)
{
/*Do each player's turn*/
if (turn == 0)
{
/*Get move from stratgey*/
char move = strategyBuf[board].best_move;
printf("My turn; my move is %c: ", move);
board = next(board, move - '0'); /*Move to board with next move*/
}
else if (turn == 1)
{
/*Get next move. must use int because you cant scan in a u8 in c90*/
int move = 0;
printf("Your turn; chose a move [0-8]: ");
scanf("%d", &move);
board = next(board, (char)move); /*Move to board with next move*/
}
/*Display the board*/
printf(" ");
printBoardus(board);
printf(" ");
/*Test for end game conditions*/
/*Use of conditional statement to test if the winner is the peice other than the player; ie computer won*/
if (winner(board) == (playerPiece == 'X' ? '1' : '2'))
{
printf("I won! ");
play = 0;
}
else if (winner(board) == playerPiece) /*Never occurs with calculated AI. You can never win ;)*/
{
printf("You won! ");
play = 0;
}
else if (get_move_us(board) == 9)
{
printf("Tie! ");
play = 0;
}
turn = 1 - turn; /*Switch Players*/
}
printf(" A STRANGE GAME. THE ONLY WINNING MOVE IS NOT TO PLAY. ");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.