If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.
Are comments needed for each method/function?
As always, please include docstrings. You should also include comments for portions of your code if they might be hard to understand without the comments.
Something seems wrong in one of my methods, but my code looks correct. What should I do?
If your new method is using one of your earlier methods, it’s
possible that there may be a bug in that method. Use debugging
print
statements to make sure the results of your methods make
sense – and fix your earlier methods as needed.
In addition, you should check for subtle bugs including:
Using ==
instead of =
. For example, let’s say that we want
to assign the result of the method call p.foo()
to the
variable x
. This line of code is incorrect:
x == p.foo() # incorrect!
Instead, you need to use the assignment operator:
x = p.foo() # correct!
Forgetting to include the empty parentheses when making a method call for a method that has no inputs. For example, we might forget to include the parentheses from the line above:
x = p.foo # incorrect! need parens as shown above
Without the parentheses, the method call doesn’t actually get made!
Passing in the wrong inputs for a method. For example, let’s
say that you’re trying to determine if the board b
is a win
for the current player so that you can figure out the player’s
score for the column col
. If you’re not careful, you might
make the following call:
if b.is_win_for(col) == True: # incorrect!
This doesn’t work, because is_win_for
needs you to pass in the
checker of the player whose win you are trying to check for –
not a column index like col
. Instead, the correct call
would look something like this:
if b.is_win_for(self.checker) == True: # correct!
Before you attempt to call a method, remind yourself of what inputs the method is supposed to take so that you can call it correctly!
In the Board
class, does the tiles
attribute have to be a
2-D list of strings, or can it contain integers?
It must be a 2-D list of single-character strings, with the
string '0'
representing the blank cell. For example, let’s say
that you construct a Board
object as follows:
>>> b = Board('012345678')
If you then evaluate its tiles
attribute, here is what you should
see:
>>> b.tiles result: [['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']]
You should not see the following:
>>> b.tiles result: [[0, 1, 2], [3, 4, 5], [6, 7, 8]] # incorrect!
If you do, you should fix your code.
What should our move_blank
method do if a direction other
than 'left'
, 'right'
, 'up'
, or 'down'
is passed in for the
input?
It should simply return False
, without making any
changes to the object.
In the __init__
method for the State
class, how can we
determine the number of moves of the predecessor?
Keep in mind that the predecessor is also a State
object.
Therefore, you can access its num_moves
attribute using dot notation.
For example, if p
is the predecessor, you would do p.num_moves
.
You should replace p
with the appropriate expression for the
predecessor.
In the is_goal
method, how can I access the tiles in the Board
object associated with the State
object?
Inside any State
method, self.board
will give us access to the
Board
object associated with the State
object. And because tiles
is an attribute of the Board
object, you can use the following
expression to access the tiles: self.board.tiles
In the generate_successors
method, what should we use as the
input for the predecessor when we construct the new State
object?
As the hints provided for this method suggest, you should use the
variable self
for the predecessor, since the current state (the one
represented by the called object self
) is itself the predecessor of
the new state.
In the generate_successors
method, when I try to add a successor
to the list of successors, I get an error that says State
object
is not iterable`. What am I doing wrong?
When you use the +
or +=
operator to add a State
object to the
list of successors, you need to perform list concatenation – adding
one list to another list. As a result, you need to make sure that you
put square brackets []
around the State
object.
My generate_successors
method doesn’t produce the expected
results. What am I doing wrong?
One thing worth checking: Make sure that you aren’t mistakenly
calling move_blank()
twice for a given move.
Each call to move_blank()
does up to two things: if the move is
possible, it modifies the contents of the Board
object, and it
also returns either True
or False
to indicate whether the move
was possible. As a result, you should only call it once per
move. However, many people have been mistakenly calling it twice
per move: once to check if the move is possible, and once to make
the move.
For example, this is not correct:
# don't do this! if b.move_blank(direction) == True: b.move_blank(direction) # no! this moves the blank again! s = State(b, ...) ...
Rather, you should do this instead:
# do this instead! if b.move_blank(direction) == True: s = State(b, ...) ...
My should_add
method doesn’t seem to work correctly for the case
in which the input state
would create a cycle. I don’t see any errors
in my should_add
. Is it possible that the provided creates_cycle
method has a bug?
No! However, it is possible that the problem actually goes back to
one of your Board
methods. The creates_cycle
method
compares two Board
objects to check for a cycle, so
if one of your Board
methods is making an improper change to
a Board
object, then it’s possible that two Board
objects that
should be considered equal are actually considered unequal.
Here’s one piece of test code that could help you to diagnose the problem:
>>> b = Board('012345678') >>> b.tiles result: [['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']] >>> b.move_blank('right') result: True >>> b.tiles result: [['1', '0', '2'], ['3', '4', '5'], ['6', '7', '8']]
Make sure that the 2-D lists that you get for b.tiles
match the ones
that you see above. In particular, make sure that all of the elements
of the lists are strings, not integers. If your results for b.tiles
are not correct, check your __init__
and move_blank
methods.
Other possible sources of the problem are: (1) the __eq__
, copy
, and
digit_string
methods in the Board
class, and (2) the __init__
and
generate_successors
methods in the State
class, which might be
failing to set up an appropriate connection between a State
object
and its predecessor. Here is some additional test code that may help
you to diagnose the problem:
>>> b = Board('012345678') >>> b.tiles result: [['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']] >>> b.digit_string() result: '012345678' >>> b.tiles result: [['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']] >>> b2 = b.copy() >>> b2.tiles result: [['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']] >>> b.tiles result: [['0', '1', '2'], ['3', '4', '5'], ['6', '7', '8']] >>> s = State(b, None, 'init') >>> s.predecessor == None result: True >>> succ = s.generate_successors() >>> succ result: [312045678-down-1, 102345678-right-1] >>> succ[0].predecessor result: 012345678-init-0 >>> succ[1].predecessor result: 012345678-init-0
We have also included some additional tests that you can use for diagnosis here.
My should_add
method doesn’t seem to work correctly when the
Searcher
has a depth limit (i.e., when self.depth_limit
is not
equal to -1
). In that case, the method sometimes doesn’t return
anything. What am I doing wrong?
Be careful about how you construct your conditional code. We have seen many people use the equivalent of this incorrect pseudocode:
# this pseudocode does *not* work! if the depth limit != -1: # block 1 if the number of moves to the state > the depth limit: return False elif the state creates a cycle: # block 2 return False else: # block 3 return True
This doesn’t work!
Note that the above pseudocode uses an if-elif-else
statement to
choose exactly one of three blocks, which we have labeled
block 1
, block 2
and block 3
. This has two problems:
If depth limit != -1, we execute block 1
and skip block 2
and block 3
. As a result, when the searcher has a depth
limit, we never even check if the state creates a cycle.
If we execute block 1
and the number of moves to the state
is greater than the depth limit, we correctly return
False
. However, if the number of moves is less than or equal
to the depth limit, we return nothing, because none of the return
statements are ever executed!
One way to fix this is issue to replace the if-elif-else
with two
separate if
statements:
# this pseudocode works! if the depth limit != -1: if the number of moves to the state > the depth limit: return False if the state creates a cycle: return False else: return True
Note that using two separate decisions in this way ensures that
we always execute one of the return
statements.
How can we determine which state has been in the list the longest?
Try tracing through some examples on paper of adding states–one at a time–to the list, and think about which of them should be removed if you want the one that has been in the list the longest.
My DFSearcher
works for all the tests cases except the one that
imposes a depth limit (the third test case). How can I figure out what
is going wrong?
Here are a few things to check:
Is your DFSearcher
‘s depth limit being set properly? Try this from
the Shell:
>>> d = DFSearcher(25) >>> d.depth_limit result: 25
If you don’t see 25, then you should take a look at how you are
constructing a DFSearcher
. If your class is simply using the
constructor inherited from Searcher
, then check to ensure that
the Searcher
constructor is properly initializing the depth_limit
attribute.
Is the should_add()
method that you defined in the Searcher
class—and that your DFSearcher
should simply inherit – dealing
appropriately with states that are beyond the depth limit?
Here’s some test code:
>>> d = DFSearcher(25) >>> s = State(Board('012345678'), None, 'init') >>> d.should_add(s) result: True >>> s.num_moves = 26 # artificially change the number of moves >>> d.should_add(s) result: False
If you don’t see the correct results, you should:
Fix your should_add
method in Searcher
as needed (see
question 2 in the previous section of the FAQ).
Make sure that DFSearcher
is simply using the inherited
version of should_add()
and not defining its own version.
Is should_add()
being properly called in the context of a
DFSearcher
‘s execution of find_solution()
? In Part III, we
indicated that add_states()
in Searcher
should use
should_add()
to decide whether to add a state. Is your
add_states()
doing that? Is your DFSearcher
simply using
the inherited add_states()
as it should?
When I try to use the eight_puzzle
driver function to test my
Greedy and A* searchers, I receive an error that says TypeError:
'int' object is not callable
. How can I fix this?
When you use eight_puzzle()
to test Greedy or A*, you need to make
sure to pass in the heuristic function as the third input, rather than
a depth limit. For example:
>>> eight_puzzle('142358607', 'A*', h1)
My GreedySearcher
class passes the tests that are given in task
4 of Part IV, but when I try to use Greedy Search in the context of
the eight_puzzle
driver function in task 6, I’m getting an error
that says that a State
object does not support indexing. What I am
doing wrong?
The problem may actually be in your Searcher
class, since
GreedySearcher
inherits from Searcher
. In particular, make sure
that:
the add_states()
method in Searcher
uses the add_state()
method when adding a new state to the searcher’s list of states
the find_solution()
method in Searcher
uses add_state()
to add the initial state to the list of states
the find_solution()
method in Searcher
uses the add_states()
method (note the s
) to add the list of successors to the
searcher’s list of states.
Make sure that neither of these methods tries to add states
using assignment or list concatenation. Rather, they must use
add_state
and/or add_states
.
The reason that this matters is that GreedySearcher
overrides
the version of add_state()
that it inherits from Searcher
, but
it doesn’t override the inherited versions of add_states
and
find_solution
. As a result, if those methods don’t call
add_state()
as they should, the GreedySearcher
version of
add_state()
won’t get called, and thus the list of states won’t
include the priorities as required.
How do I read from a file?
In lecture, we presented two different ways to read the contents
of a file. You can consult the lecture notes from a couple weeks
ago or check out the example code online. For the project,
we recommend reading in the file one line at a time using
a for
loop.
I’ve completed my process_file
function, and I’m performing the
initial tests that you recommend using the 10_moves.txt
file.
Although my earlier tests of BFS all went fine, I’m getting
non-optimal solutions when I perform BFS using process_file
.
Do you have any suggestions for how to find the problem?
Yes! Make sure that you create a new searcher object for each puzzle (i.e., for each line of the file). Otherwise, the searcher will still have information inside it from previous searches when it starts to solve a new puzzle.
When I test the process_file
function using the
10_moves.txt
file. I’m able to reproduce the results for BFS,
but I don’t get the same results for Greedy. Is that a problem?
Probably. When you first implemented the GreedySearcher
class in
Part IV, task 4, if you got the same results as we did for the
examples that we provided, then you should get more or less the
same results here as well. The only possible exception is the
number of searches that you choose to terminate.
If your results don’t match ours, one thing to double check is your
num_misplaced
method in the Board
class. Here are some additional
test cases for that method that should help you to ensure that it’s
working correctly in all cases:
>>> b = Board('012345678') >>> b.num_misplaced() result: 0 >>> b.move_blank('right') result: True >>> b.num_misplaced() result: 1 >>> b.move_blank('down') result: True >>> b.num_misplaced() result: 2 >>> b.move_blank('left') result: True >>> b.num_misplaced() result: 3 >>> b.move_blank('up') result: True >>> b.num_misplaced() result: 3
My h2
heuristic function still doesn’t allow A* to solve the
24-move or 27-move puzzles in a reasonable amount of time. Is that
okay?
Probably. To ensure that your h2
heuristic is good enough,
try comparing it to h1
in the context of puzzles that require fewer
moves. For example:
>>> process_file('15_moves.txt', 'A*', h1) >>> process_file('15_moves.txt', 'A*', h2)
When you look at the results of these two calls, you should see that:
using h2
allows A* to test fewer states than it does when it
uses h1
the h2
solutions are still optimal (i.e., they
require the specified number of moves).
For full credit, you should also ensure that your h2
never
overestimates the number of remaining moves. See the assignment
for more details.
If all of these things are true, then your h2
is probably good
enough.
My h2
seems to work well, but I’m failing a test in Gradescope
that says the following:
part VI: h2(s1) for state s1 in the examples Test Failed: h2(s1) overestimates the number of moves to the goal
What does this mean?
When constructing a heuristic function for state-space search, one of the criteria is that the function should never overestimate the number of remaining moves. Otherwise, there is no guarantee that A* will always find an optimal solution.
The state s1
that is mentioned in the failed test has the
following board:
This board is 5 moves away from the goal. The message accompanying
the failed test indicates that your h2
gives this state an
estimate that is greater than 5 – and therefore it overestimates
the number of remaining moves. You can test this as follows:
>>> s1 = State(Board('142358607'), None, 'init') >>> h2(s1) # what result do you see?
If you are failing the Gradescope test mentioned above, the result that you will see will be greater than 5 – and it shouldn’t be!
If possible, you should adjust your h2
so that it never
overestimates the number of remaining moves.
Note that if your version of h2
fails this test, you don’t have
to eliminate that function entirely or get rid of your
experimental results for it. Instead, you can change its name to
h3
and still include its experimental results in your
report. Then you can implement a different h2
– either using
the approach described above or some other approach that never
overestimates the remaining moves, and run additional experiments
using it.
It’s worth noting if you don’t have time, it’s also okay to stick
with your current h2
! You will still get almost all of the
credit if your h2
meets the other two criteria described in question 4
above.
Last updated on April 24, 2024.