Practice: Pre-requisite Assignment

Consider the game of Tic-Tac-Toe where a square may contain either a cross or a knot or be empty. For the time being if we ignore the rules of the game and allow ILLEGAL board positions then what is the maximum number of board positions possible for a 3x3 labeled board shown here?

Enter an integer in the text box. DO NOT ENTER COMMAS, SPACES, DOTS, PLUS SIGN OR ANY EXTRANEOUS CHARACTERS.

As an exercise, estimate the number of LEGAL board positions. Is it less or more than the boards counted in the previous question? Enter an integer in the text box. DO NOT ENTER COMMAS, SPACES, DOTS, PLUS SIGN OR ANY EXTRANEOUS CHARACTERS.

An intermediate board position of a Tic-Tac-Toe game (first player plays cross) is shown below. Find out all the board positions that can occur after the next move. Note that we are not looking for the best or even good moves here, but just enumerating legal moves.

Select the correct boards.

Find out all the board positions that (after one move) will produce the following board position. Again we are not commenting on the quality of the moves, just understanding the rules of the game.

Select the correct boards.

How many legal states are present in the completed state-transition diagram? Enter an integer in the text box. DO NOT ENTER COMMAS, SPACES, DOTS, PLUS SIGN OR ANY EXTRANEOUS CHARACTERS.

How many legal state-transitions (arrows) are present in the completed state-transition diagram? Enter an integer in the text box. DO NOT ENTER COMMAS, SPACES, DOTS, PLUS SIGN OR ANY EXTRANEOUS CHARACTERS.

Which of the following is a valid first move?

Which of the following are valid second moves?

Starting from the initial state, which of the following sequence of moves lead to the final state?

For the sake of simplicity, let us empty the arm as soon as possible, i.e., when we PickUp(X), let us immediately either PutDown(X) or Stack(X,Y), similarly, when we Unstack(X,Y), let us immediately either putDown(X) or Stack(X,Z) or Stack(X,Y). So in this way, when we start in a state where the arm is empty, and make two consecutive moves, we will end up in a state where the arm will be empty — this is equivalent to defining a Move(X,Y) action which says that IF X is free, move it to location Y which could be another free block or the table. Now, count the number of such states (where the arm is empty) for a blocks-world problem containing three labeled blocks? Enter an integer in the text box. DO NOT ENTER COMMAS, SPACES, DOTS, PLUS SIGN OR ANY EXTRANEOUS CHARACTERS.

Which of the following is true of the Tic-Tac-Toe state space that is constructed from the empty board by allowing only legal moves?

Which of the following is true of the Water-Jug state space that is constructed from (3,0,0) by allowing only legal moves?

For the blocks-world problem with three labeled blocks, which of the following is true of the state space that is constructed from the initial position (all blocks on the table) and by making only legal moves?