WOW,SO MANY PEOPLE...

XEO1OF

Inflatable Obstacle<br>
Inflatable Tunnel<br>
Inflatable Toys

CompTIA A+ Certification<br>

CompTIA A+ is the most recognized and trusted certification for entry-level service technicians. From installation to basic networking, employers know CompTIA A+ Exams certified technicians have the knowledge and skills to successfully complete the job. Adding a CompTIA A+ certification to your resume will prove to employers your abilities with core hardware and operating system technologies. pass4sure offer the CompTIA A+ exam answers

Key benefits for becoming COMPTIA HTI+ Certification:<br>
• A solid credential that makes you more marketable, leading to better job opportunities.<br>
o Top technology companies including CompuCom and IBM have made CompTIA A+ certification mandatory for their service technicians. Additionally, more than 100 companies now require IBM certifications as a prerequisite to qualify for their corporate and vendor-specific training programs.<br>
• Credibility and respect in the workplace.<br>
o Nearly 71 percent of certified professionals say that credentials give them more prestige among their colleagues.<br>
• Validation of achievement in an industry-valued skill.<br>
o A+ COMPTIA EXAM PASS is an opportunity for individuals to earn the credential that proves their competency in core hardware and operating system technologies including installation, configuration, diagnosing, preventive maintenance and basic networking.<br>
• Increased knowledge, leading to increased job satisfaction.<br>
o Ninety-three percent of CompTIA certified IT professionals feel their customers are in qualified hands, and 84 percent say they have the confidence and required skills to do a superior job.<br>
• Viable career path, leading to higher level positions.<br>
o Seventy-four percent of IT managers say a CompTIA certification is an important factor in considering an employee for a promotion.
<br>
Don’t delay, act today and start earning a valuable CompTIA certification using the quality pass4sure learning products.pass4sure<br>

Our mission is to introduce you to the fun world of Inflatables. We offer an astounding array of Inflatable merchandise. Browse our pages for Boats, Inflatable Pools for young and old, AeroBeds and Air Beds, Furniture, Inflatable Toys, Accessories for all, and much more! Offering items from Intex, and AeroBed; both world recognized leaders in Inflatables manufacturing for style, desirability, quality, durability, and value.<br>

Other items include: Inflatable Jumper, Inflatable Bouncers, Inflatable Castle, Inflatable Obstacle, Inflatable Tunnel, Inflatable Games, and much, much more! Our products are a great affordable choice and are designed for all age groups. Many of the kid's pools will double as ball pits and are fine for indoor play during winter or stormy days. Our Inflatable Toys are a wonderful alternative to those hard bleachers at the little league games and provide an elevated vantage when watching the kids at the beach. The scuba accessories and pool floats are just the thing for little swimmers and big ones alike. Explore the pages of our site for your gift giving ideas!

Kei Shun Ma - congrats on the Data Mining competition. I have a quick question for you - can you possibly contact me on p.ellegaard@yahoo.com

Thanks Peter

Hopefully you've all picked up HW4&5. If you find any grading errors, email me - I'll probably have you make a note and stick it in my mailbox.

I should be getting project grades to you over the next couple days.

It's been a pleasure!

hey matt, even though he said only parts 1-3 are relevant, do you expect we will need to be able to work out problems like the last page of the sample final: http://www.cse.ucsd.edu/classes/sp07/cse15...ead-problems1-3.pdf

Yes, the last problem on that final is relevant - sorry I missed that!

-g.

I have posted all of the lectures, and a couple
of relevant tests...see you tonight!

-gary

Hi folks --

If you haven't gotten an email from Matt yet, here are
the answers:

As mentioned in class, the review session is tomorrow, Monday,
June 11, at 7PM. Our plan is to have it in the same room as
last time, in the basement of EBU3B, just opposite the elevators.

You can have one two-sided cheat sheet for the final.

I plan on posting the slides from the last k classes tonight,
as well as a practice final, at least as close as I can come
to one under the circumstances (somewhat different material,
etc. from the last time I taught it).

cheers,
g.

I would also like to know this

when is the final review????????????

I think when we were discussing the cheat sheet for the midterm we came to the conclusion that we could have a 1-sided cheat sheet for the midterm and a 2-sided cheat sheet for the final.

Are we allowed a cheat sheet? One-sided?

Will we have any final review and lecture notes posted online?

Edited by author 06-08-2007 01:10 AM
If it's in the training set, it's perfectly legit to just add more feature words based on your performance... Feature selection is a bit of an art, not a science (at least at this stage - more scientific and principled approaches to feature selection are pretty active areas of research).

Wondering what everyone is getting trying to classify the test sets?
For us, currently:
trainSpam4 = 99.14% correct
trainHam3 = 77.13% correct

We are having a tough time classifying ham messages as ham, especially ones that are not written by a human and short messages that do not contain any of our feature words. Any suggestions.

I was messing around the the mailbox module and discovered that if you use mailbox.PortableUnixMailbox() you'll get 293 for the ham count
and you would get a ham count of 291 if you used
mailbox.UnixMailbox()

I was using UnixMailbox yesterday, but switched up to using PortableUnixMailbox since it was recommended over the regular UnixMailbox by some of the sites I found.

I also get 598 spam and 293 ham using the python mailbox module.

Also, would it be possible for a project extension since specifications and files for the 20 emails per file format aren't up yet? It would greatly ease the 10th week pressure and what not =).

Using the python mailbox parser I got 598 spam and 291 ham, but originally I was using just a regex and I got 598 spam and 293 ham. Looks like something is wrong with the ham training set, because it looks like everyone can agree on the spam.

Got those exact same numbers, in both our parsers. My personal parser used Java. Used "From "

This is my count, can anyone else verify this?

Spam: 598
Not Spam: 293

I posted the slides from the last couple sections on the webpage. Last week's in particular has a lot of tips and explanation of the current project and is at: http://www.cse.ucsd.edu/classes/sp07/cse150/section/Section8.pdf.

For 13.8, they give exact numbers so you should use them to support your argument numerically (ie do a calculation).

For 20.13, I'd want some written out calculation of how it would change - Gary's indicated that that sort of thing is likely to be on the test, so you should take the chance to practice.

I'm guessing/hoping from the lack of continued complaints that people are feeling more comfy with mbox parsing? There actually are some toolboxes out there for mbox reading (one student at least has been using the Python tool box). It seems like the format is reasonably well spelled out, so it doesn't seem like there should be disagreement. If it's something people are worried about, like I said I'd be willing to break up the test set into small chunks with known #s of emails so you can either fix things (by hand if necessary) or at least not be penalized for being off by one or somesuch.

Slogging through the questions built up about the HW (from here, discussion, and email):

10.1 Question from Erik - You should probably model your answers on the effect axioms described in section 10.3. These use both Poss (to check preconditions) and Result (to refer to the appropriate resulting state).

10.4 Question from Josh & discussion - A lot of this I answered, but I missed the mereological part. Basically mereology is a branch that provides an alternative to set theory, more or less providing an alternative to set theory based on partof relations. Sometimes this makes sense: for instance since set theory assumes atomic elements, elemOf(x, Water) ^ partof(y, x) => elemOf(y, Water) seems very odd, since x and y are atomic elements of the set of things that are Water. On the other hand, partof(x, Water) ^ partof(y,x) => partof(y, Water) seems very natural. So for the second half, you use partof relations instead of predicates (e.g. Water(x)) or set theory (elemof(x, Water) or "x \in Water"). Don't stress it too much, the focus is more on the first part.

11.4 As Josh pointed out, you need a "Holding" fluent and an "At" fluent - both are mentioned, but not made explicit. It already mentions "Go" and "Push" actions, so I disagree about the need for an additional "Move" action. It is indeed a blockworld-like world with only 3 positions.

I don't think I've gotten any question from Chapter 13 questions

20.13 - "Are we supposed to be describing what happens to the weights of a still single layered perceptron like it was talking about in the first sentence?" Yes. 4 input neurons feeding into one perceptron output unit trying to compute parity. "Does four-input refer to 00, 01, 10, and 11, or are there actually 4 bits of input?" Four bits of input. "Are we basically showing why single layer perceptrons fail?" I'd say partly yes, and partly getting some hands-on practice with perceptrons.

How Long are ppl's learners taking? This seems really slow...

-bash-2.05b$ time java spamNBLearner > spamParams.txt

real 3m20.461s
user 3m22.930s
sys 0m2.360s

Almost all of the time is spent reading the email files in.

Edited by author 06-03-2007 08:54 PM
So, as I said in the assignment, the files are in mbox format, the most commonly used format. So I'm a bit surprised that there's any problem getting them chopped up into separate emails. If you look up the format, there's a specified way of how to break them up, namely lines starting with "From ", with a blank line appended at the end. This is the official specification. I don't actually get the counts I'd expect (I think I get 290 and 598 with my quick check), but I did say they were mbox files so you should treat them as such.....

So, for instance, this is from the second hit Google provides:

  A reader scans through an mbox file looking for From_ lines.
          Any From_ line marks the beginning of a message. The reader
          should not attempt to take advantage of the fact that every
          From_ line (past the beginning of the file) is preceded by a
          blank line.

          Once the reader finds a message, it extracts a (possibly
          corrupted) envelope sender and delivery date out of the
          From_ line. It then reads until the next From_ line or end
          of file, whichever comes first. It strips off the final
          blank line and deletes the quoting of >From_ lines and
          >>From_ lines and so on. The result is an RFC 822 message.

Aside from the first msg, the following RegExp should work: "\n\nFrom .*\n". (That's from the next Google hit). So it seems like the answer to your question was out there with a pretty minimal amount of digging.....

Matt, Stephen was saying that even if you split up the emails into chunks of 20 emails each, that doesn't help at all, since different ways of splitting up the emails can still yield different results. We need a standardized way of splitting them, so everyone can get the same results

Clarification: When I said 20 email chunks, I meant files with 20 emails each, not 20 chunks of unknown amount.

I'm a bit confused on problem 10.1. I'm not 100% convinced I did it right. Is the format of the answer to the Result(a,s) function?

Yeah, I'm at around 580 spam and 290 ham/non-spam e-mails. It would be nice to have a standard way of splitting the messages so that I can output the correct number of 0's and 1's.

I think that splitting on return-paths causes there to be problems. Consider the message on line 12569, in which the attached message has a return-path but no From line in the header. This is really one message with the bounced message attached but with the return-path technique it will be split into two messages. Doing a simple "[Ff]rom .*@" search I get 598 messages for the spam and 293 ham. Maybe it would be best if we were given a standard way to split messages, because I don't think 20 smaller chunks will help.

Edited by author 06-02-2007 05:10 PM
I think one of the problem is that the email given is normally started with a sentence like "From abc@def WEEKDAY MONTH(one or two space)DATE TIME YEAR"
and then the second line is "Return-Path: xxxx"

However in both spam and hams emails, some miss the first line and start with the second line "Return-Path: xxx" instead, so the numbers I found is by counting the lines start with "Return-Path: ", but I am not sure if there is any email missing both the first and second line....

600 and 300 message files were used (+/- 1, I'd say). *Supposedly* breaking them apart is easy, but it's not something I've had to do, honestly. If people are having problems getting consistent separation, would it be helpful if the test set were in, say, 20 email chunks?

Edited by author 06-02-2007 12:27 AM
for 11.4, i envision the problem a block world-like place, but where left position is A, middle position is B, and right position is C.

if so, shouldnt there also be an "At" fluent that is true if (box,monkey,banana) is at place A,B, or C? Thus we need a Move action for the monkey to go to and from positions?

The numbers I get is 611 spams and 297 hams, but I am not sure it is correct or not...

Anyone know yet how many spam/ham messages are in each of the files? Is there any best way to split up the emails other than trying to recognize what combination of strings a new email starts as? I'm sometimes having trouble figuring out when a new email starts and ends when I'm looking at the list... let alone abstracting the beginning or the end.

Right now i'm counting 608 spam, and 348 ham

Just to be clear. Both the
learner and the classifier take in the name of the email file (as
text) and call the preprocessor to generate the features. The
classifier does not call the learner, since it can be run on both the
training and testing data.

For 11.4, there's also a "holding" fluent, which you should assume is false in the initial state. I'm not sure why it wasn't italicized in R&N.

Your answer isn't really what we're looking for. (Is "Water" a constant? What does it refer to?) Generally with logic we've done things like "forall x,y Dog(x) ^ Bone(y) -> Likes(x,y)". There's actually an example in the text of almost this exact same problem you ask about... Basically, use as basic and general propositions as possible. For (b) you shouldn't need to invent a proposition like IsLiquidBetween(...), but should identify the conditions under which something like IsLiquid(x) is true. I think it should be pretty obvious from the text what extensions are relevant.

I'll be late for my office hours (probably at least half an hour). I'll still stay an hour from whenever I arrive.

for problem 10.5 in the homework, it seems like there are a lot of "representations developed in the chapter" so I was wondering if something like this is what they are looking for--

b- "water boils at 100 degrees"
answer- BoilsAt(Water, 100 degrees)

Also for the second part, i can't find any examples in the book of using the mereological approach. is it using the partof() and other like operators?

Thanks

No, that simply refers to the report. I was pretty tired when I finalized it, I'll clarify the assignment. Thanks!

I found that README/ README header were mentioned several times in PA4, does it mean besides the normal comment and the written report, we need to create a file README to describe how the program works?

The ham training set was posted this afternoon.

If anyone wants to work on this last lab together or has a group I can join, please message me Erik Peterson at erikpeters@gmail.com. Thank you.

Edited by author 05-25-2007 02:34 AM
Stephen,

Yeah, after trying it out, you're right. Normally I wouldn't speak out of ignorance, but I wanted to be sure you got an answer ASAP (despite my lag on this more recent turn around). I'd really have expected them to have done something about that when they added typed containers.

Everyone can feel free to add Stephen's suggestion. I'll add it to the test copy too.

Matt,

This link has notes on equals methods http://www.ibm.com/developerworks/java/library/j-jtp05273.html

I've tried printing out to stderr at the equals call of the code you gave and I got nothing.
I admit that using the try catch is ugly and costly. It would probably be better to implement it as

    public boolean equals(Object obj) {
        return obj instanceof Coord && equals(this,(Coord)obj);
    }

Stephen,
I'm *relatively* sure that when you type a collection (ie Vector<Coords>) that it would correctly use the correctly typed equals, which means the one I provided below should be fine. It was definitely my intent to make the sort of thing you describe easy, so if I'm wrong I guess I can add the code you suggest (or equivalent using getClass instead of try/catch). Let me know what you find out.

(That try/catch block really bothers me a lot. It looks like the correct way would be:
  if (c2.getClass() == Coord.class)
   return false;
but I haven't really tried it.)

Matt,
I was thinking it would make sense to have the overloaded equals function so we could easily look for the coordinate in the threats vector. I'm pretty sure the contains() call uses the overloaded function.

Erik,

I did mean average... 14 seconds seems very high though.....

Stephen,

I'm not sure I understand why there'd be any benefit to having an "equals" function that takes a generic Object... I do know that in general having a try/catch like that is generally better avoided (you could probably work out a check involving getClass()).

I'll add the following. Rather than rerelease, feel free to insert it into your code.

 public boolean equals(Coord c2){
  if ((x == c2.x) && (y == c2.y))
   return true;
  return false;
 }

Am I correct in assuming that the average move should take 1 second? My competitive solver can take up to 14 seconds for some moves but more than makes up for it by taking just a few milliseconds in other moves, is this a problem?

Could you please add

    public boolean equals(Object obj) {
        try {
            return equals(this,(Coord)obj);
        }
        catch (ClassCastException e) {
            return false;
        }
    }

to the Coord object so we can easily search for coordinates in the threats vector?

Kei,

The same state repeated four times would certainly be a sufficient condition. That's what I'm leaning towards, assuming I automatize tie deciding.

Thanks Erik and John for the feedback. Since some of you may have been fine tuning for 500, at least part (and maybe all) will be run at that limit for the competition. But I'm still reserving the right to have higher limits in addition.

Has the draw condition been decided? It would be good to know ahead so we can detect and avoid the draw and take other path if possible.

Edited by author 05-24-2007 12:37 AM
I tested my competitive solver. With a 1 second time limit it usually expands to around 20,000 nodes and also trims around another 16,000 nodes with alpha beta pruning.

With a 500 node limit my program has takes 20 milliseconds to select a move.

This is run on a 1.8ghz Pentium 4 laptop.

My competitive solver's performance varies greatly with depending on the expansion limit, is it staying at 500 nodes?

Kei,

Tuesday is fine as long as it's the same as the pdf you submit when you turn in the project.

-Matt

Is the hard copy of report due Friday office hour or next Tue?

Also, I thought I'd made this clear, but I got asked about it today. Everyone will be tested using MY version of the Checkers package (which will be the same as the one I handed out to you). Your code should not be part of this package, but should import the necessary classes. The testing function (which I'll be running) will be very like the Player class provided - I'll be instantiating two Solvers (one yours, one someone else's) and calling on them to provide moves.

I would assume this would go without saying, but BE SURE TO SITE ANY AND ALL SOURCES. I don't care if an idea isn't your own - doing research into a problem is part of good research. But if you don't cite it, it's plagiarism.

That said, using other people's code is not allowed, cited or not.

You're welcome to have memorized values for particular states as part of your submission. The total size of your submitted code (so not counting your pdf) cannot be more than one MB.

Is programming specific finishing moves allowed via our utility function? Is anything allowed as long as we use the information available in the utility function and nothing else?

Edited by author 05-22-2007 09:05 PM
I wrote my competitive solver to search as much as possible within the 1 second time limit, and with not expansion limits, it usually expands around ~20,000 nodes and also trims around another ~20,000 nodes from the search tree using alpha beta pruning.

With a 500 node limit my program has a selectMove() runtime of about 0.02s

(Edit: This is run on a 3.4ghz Pentium 4 machine)

Edited by author 05-22-2007 05:28 PM
Regarding competition params:

The intent is that if your program takes more than about a second on average per move at 500, you may be disqualified. Machines have come a long way since the last time I did this course, so the sec/move rule was just an educated guess. How's it working out in practice? How deep are people able to go in the first parts?

If people are far enough along, I wouldn't mind some feedback about how long things are taking per move at a limit of 500? It was just a guess at balancing three goals:
-giving you enough space to work your magic
-actually having the competition be feasible (I'm going to be running a LOT of games of checkers)
-not giving you too much space so that clever pruning and evaluations aren't overly meaningful.
What are people's perceptions so far of 500 as a limit?

If I get some useful feedback, I can try and nail down the specifics a bit more if people would like.

Robin,

I don't know what your best solver is. It seems like its difference from alpha-beta could be huge or minor. Any chance you meant alpha-beta/minimax instead of best/alpha-beta?

Kei makes a good point that alpha-beta and minimax should be the same for the same depth. As he suggests, this is a good way to do some debugging. Your "best" shouldn't do worse than either of the vanilla methods, and it would be surprising if those would be beaten by random more than once in a blue moon (it is of course "possible", but it seems mighty unlikely).

Edited by author 05-22-2007 06:09 PM
Ben,

Yes, it seems like that would currently be illegal since it seems like you'd have to calculate the possible moves (the expand function) to know how many there are. If you want to make a case for it, I'd at least consider adding Game.getNumMoves(b) I suppose.

I know it sometimes ends up being a somewhat arbitrary distinction. Basically, there are four good ways of providing limits:
a) # of evaluations (probably most common for this sort of competition, but would be harder to provide common interface and make it easier to cheat the counter, plus a lot of gray area on what's evaluation and what's heuristic)
b) depth (easy to implement and understand, not very useful for measure success in pruning)
c) time (probably most used on commercial systems, but
d) # of expansions (what I chose - easy to quantify and control, but can make the boundaries of what the evaluation function can do a bit murky)

Basically, expand returns the results of actions. You can't replicate this in your evaluation function. However, you can do some small local search around individual pieces (such as what's next to a piece in the directions it can move).

If you want your evaluation function to really know about what actions are possible and what the results are, you're going to have to call it on a node you've expanded (which is fine) rather than on a true leaf. It's more expensive in terms of # of expansions, but can make for more powerful evaluation function.

Edited by author 05-22-2007 06:09 AM
I tested with depth limit 3 to 6, and they works the same. But when I set the expand limit, they come up with different result, as the better solver will search deeper.

I should say when I tried to modified the textbook's code to find also the best successor, the order of codes in the forloop made me trouble. I have to reorder the codes to make my algorithm works. The code itself is correct.

Kei,

What values did you select for your testing? (i.e. depth limit, expand limit)
What is wrong with the way the book describes it?

Matt,

"More guidelines on what “reasonably quick” means will be forthcoming, but it shouldn’t take more than a second with reasonable limits."

"The exact limit will not necessarily be announced ahead of time, but will be at least 500 nodes. "

Should we try to optimize our solver based on 500 node expand limit? Or is there an official number?

Thanks,

Robin

Edited by author 05-22-2007 04:40 AM
Robin,

    How does your vanilla alpha-beta player play against the RandomPlayer? I think even the vanilla alpha-beta player should win all the game against the RandomPlayer. My old vanilla alpha-beta player sometimes lost to the RandomPlayer (about 1 in 10 games), but then I found a bug on it (the textbook's code doesn't really work). Now I have tested my new vanilla alpha-beta player against the RandomPlayer for more than 300 times, and it wins all.

    Besides, the way I found that bug is that, for different solvers (e.g. Minimax against alpha-beta) with the same evaluation function (e.g. sum_up) and the same depth limit (but no expand limit), the result should always be the same againist the same player (except RandomPlayer). The only difference should only be the speed. That's what I get so far. It is true at least for using sum_up or some simple method as the evaluation function.

If we test our Best Solver against the vanilla alpha-beta player, without changing any settings, won't it always compute the same game?

Also, does anyone else's Best solver still sometimes loose to the RandomPlayer?

Edited by author 05-22-2007 12:23 AM
I noticed that there is no function Game.GetNumMoves(Board b).

Is computing the number of moves available for some board state which we are considering but have not yet expanded 'illegal'? It seems it vaguely resembles computing the successors of the state outside of the Game.expand function...?

Kei,

Just the expansion limit for competition. That should take care of both parts of your question.

Edited by author 05-18-2007 06:03 PM
For the competition, besides the lookup limit, would there be any depth limit?

Also, would we be allowed to know the depth limit directly?

I would put the evaluation function in the node, that way, when you want to peek at which node looks best, you call each nodes eval() and choose accordingly.

just an idea,
Erik

Sorry if this is a really dumb question...
but for #2 on the project... "write an evaluation function"... where does this function go? I understand what it does, but where do we put it? In the node class? In Board? In our solver?

Yeah, there are oddles of variations, house rules, and minor tweaks out there. I probably could have looked things up to find out what the official word was on some of this, but it seemed silly for a game I'd been playing for SO many years.

I think it's usually pretty apparent if there's a tie. I may or may not take the time to code up a check.

Bummer about stopping when kinged - those were oodles of fun those VERY rare times when you could work out something huge. But it's a minor tweak, and I guess I'll make it later today. Want to be street legal if possible!

Here is a rule about the American Checkers/English draughts

http://www.darkfish.com/checkers/rules.html

It suggests several ways to consider a draw, but I think only the following one making sense for our project as we don't have a referee =) :

If neither side has advanced a piece towards the king-row and if no pieces have been removed from the board within 50 (or 40) moves, the game is a draw. He also adds another set of conditions under which a draw can be declared: “A draw shall be declared if a player can demonstrate that with his next move he would create the same position for the fourth time during the game.”

Edited by author 05-17-2007 05:55 AM
Forced jump is really fun =)

In wiki, there is a rule - If player's piece jumps into the kings row, the move terminates (it cannot jump out (as in a multiple-jump move) until that move has ended and the piece has been kinged)?

(The code doesn't enforce that, but I think we are playing a less restricted version making life easier)

The wikipedia article on Checkers is mildly interesting, and actually has a fair amount of info on computer chess. One thing it mentions is that Checkers has not actually been "solved" in the sense of the search tree being completely, but that this should be doable in the next few years.

http://en.wikipedia.org/wiki/English_draughts

It also says that the current Player method is mildly wrong in that it's supposed to be a loss if you have no valid moves but still have pieces (it's currently tagged as a tie, as in chess). Doesn't come up that often, but you may want to fix it. I'll include the fix if I do another release.

Edited by author 05-17-2007 05:26 AM
That's not a bug, it's part of the game of Checkers. "If you can jump, you must. And, a multiple jump must be completed; you cannot stop part way through a multiple jump. If you have a choice of jumps, you can choose among them, regardless of whether some of them are multiple, or not."

There's actually a really fun variant where you win if you force the opponent to take all your pieces. (If you finish early and get bored, this might be fun to try.)

Not-so-random tangent: I remember getting in a fight in something like 4th grade with some friend who refused to make a jump that was going to set him up for a triple jump. But if you poke around on the web, forced jumps are a pretty key part of Checkers strategy.

There appears to be a bug in the successor method. If a piece can be captured it'll only generate the successors that can capture a piece. If no piece can be captured then it does properly generate all possible successors.

Sometimes it's advantageous to play it safe and not capture a piece so this is limiting the usefulness of some strategies.

Edited by author 05-16-2007 07:48 PM
Erik,

That's my problem to detect, not yours. :) Unless I extend the interface to include a "claim tie" option that both sides would agree to somehow (especially since nothing says your opponent won't be able to take advantage of suboptimal play, since not limited to minimax), it's best if the overall Player recognizes that it's looping or that there are just too few pieces left to resolve play. I'll either do this visually or by calling it a tie if the same state is repeated 2 or 3 times.

For your reporting, you can do that too.

That's a good point that you're often unable to take advantage of suboptimal play under minimax.

Edited by author 05-16-2007 04:46 PM
I'm getting an infinite loop.
Player R: minimaxSolver
Player B: randomMoves solver

Board State: Shown below, it is B's turn.

 | | | | | | | |
 | | | | | | | |
 | | | | | | | |
 | | | |B| | |
 | | | | | | | |
 | | | | | | | |
R| | | | | | | |
 | | | | | | | |

Optimal moves would render this a tie so R is never detecting a better position to move and alternates between the position it is in and a bottom-right diagonal move indefinitely.

B is moving randomly but since R is assuming B is playing optimally, it'll never capitalize on B's future possible dumb moves and stays in the same two positions forever from which it can never capture B's last piece.

Are we expected to detect such situations and just call it a tie?

Edited by author 05-16-2007 02:04 AM
Fixed, and with my default flags changed so it shouldn't happen again. And no, wasn't *quite* up to date (wrong Player there), so you may want to snag again.

Oh, and even more recently small modification to Game to avoid an off-by-one error on the #of accesses.

Edited by author 05-15-2007 04:32 PM
Matt,
the new version of current.tar is not allowed to be downloaded, could you fix it?
(I copied the individual java files directly from the link http://www.cse.ucsd.edu/classes/sp07/cse150/pa3/ , but I am not sure it is the newest version or not)

Erik,

Important question! The basic idea is that the initial board forms the root Node of your search tree. You call expand on the board you receive to find all the Boards reachable in one move, forming the first layer of your search tree. You then select a node to expand, add the result to your tree, etc.

You all should have gotten an email from me on Sunday. If you didn't, or if the email where you received it isn't your preferred email, LET ME KNOW. Gary said a good chunk of you said you hadn't seen the project yet.... But I've been getting enough questions, I *know* some of you saw my email.

Also, a reminder that you're responsible for reading all emails from Gary or myself and for content of this board - quite a few people made mistakes on the HW that they couldn't have made if they'd been reading this board.

Fairly significant code change, please refresh your copies!

* Added getThreats(Board b), which lets you see what pieces COULD be taken the next turn
* Fixed bug for jumping
* Mildly increased error checking

so the expand function is used to peek at all the known possible moves right? I'm a little confused if we are allowed to expand once, then create nodes to search through, or we reuse this expand function as part of our search so that you track how deep we search etc... thanks Matt

Edited by author 05-14-2007 07:13 PM
Matt, the main CSE 150 page doesn't link to the pa3 page fyi.

If someone wants to partner up for this lab 3, email me at erikpeters@gmail.com

thank you

Minor tweaks to Player class.

Josh,

Chapters 1-9 and lectures up to last Thurs.

What section in the book will the midterm cover up to? Thanks in advance.

The class notes weren't completely linked in. I tossed in a link to their directory to the web page, so you should be able to get to them.

Yeah, rebooted at 8am. By my watch, people still have ~8 minutes.

Edited by author 05-04-2007 11:31 AM
yep.... its just up. It was still down around 7:30am this morning... so we can hand in our project at 11:59:59 pm again?

ieng6's 2 compute servers were down last night so nobody could ssh into them. They are now up and running again. =)

Edited by author 05-04-2007 02:24 AM
Should have just gotten an email about this. As long as your project is submitted by noon tomorrow it'll be ok.

We're still investigating the problem, since both Gary and I can log in fine...

IENG6 IS BROKEN.

Edited by author 05-04-2007 01:39 AM
Yeah, unable to login to ieng6 and turn in. Now what?

is everyone not able to login, I can't get it at all to test or turnin

Yep me too.... In the past several hours I can typed in password and then it frozed and refused to go to the welcome screen.... however now it completely refuse to connect to the server....

I can't login in either.. but the error message has changed now to:

ssh_exchange_identification: Connection closed by remote host

so maybe someone is fixing it?

Hmmm... I can log in fine from home currently... Anyone else having problems?

Edited by author 05-03-2007 11:16 PM
I found that I cannot connect to the ieng6.ucsd.edu suddenly at home.... I have been waiting for an hour but the connection still doesn't come back yet... Did anyone know what's happened?

(ps. I used SSH to connect to ieng6.ucsd.edu, I have tried both my laptop and desktop and rebooted several times and reconnect the internet, but nothing help... however I can go to all other website without any problem (including ucsd.edu, cse.ucsd.edu, and acs email at ieng6 and ieng9)

I tried telnet and ftp problem too... but still no use...

Also I can successively login to ieng9... but not ieng6 of our server...

Erik,

Probably no study guide per se. But my section next week will be prepping for the midterm (by request). And Gary mentioned to me he hopes to hold a review section as well (stay tuned for details).

The midterm covers up to the first part of today's lecture, corresponding to chapters 1-9 in the text.

Yes, in class May 10. You're allowed one cheat cheat sheet (standard 8.5"x11", single side, handwritten).

Anon,

No. And it wasn't extended.

Edited by author 05-03-2007 06:25 PM
I know it was announced in class, but for turning in the paper copies of your reports Gary said to bring them by his office hours. (Remember to turn in a pdf tonight as well, tho.)

(If for some reason this is a problem, please email me)

Edited by author 05-03-2007 06:12 PM
So at least a couple people have been confused about branching factors and nodes visted.

Nodes visited means you've popped it off the stack (ie a particular variable assignment to a particular value) and expanded it.

Branching factors means you're adding it TO the stack. Ie, you've selected your variable and are considering all its assignments, trying to select one of them. The branching factor of that value is the number of possible values the variable can take.

Alternately, you could also count the branching of variable selection, so you'd have two rounds of branching per assignment (one to select the variable, one over all values for the selected variable (and you wouldn't ever look at the branching of non-selected variables)).

Both are ok, but since the former corresponds to the stack operations you all know and love, that's what I'll be assuming you're doing unless you say otherwise.

If your two numbers are the same, you're probably doing something wrong. But I could see them being close in some cases.

Did he extend the deadline for program 2 in class today?

Will there be a study guide for the midterm? Up to what lecture will the midterm cover? Will the midterm be held in class on may 10th?

Thanks

If you haven't already found other .ss sources, http://angusj.com/sudoku/ has two fairly nice ones.

Robin:

CSPSolver.java test.txt -mrv -dh

how will the testing be ran with multiple flags?
like this: CSPSolver.java test.txt -mrv -dh

or like this: CSPSolver.java test.txt -mrv dh

or something else?

Degree heuristic: This seems to be the biggest source of confusion so far. There are a couple ways to go about it.

One is to simply count the number of unfilled boxes in the rows, columns, and boxes. You should probably avoid counting twice (since some elements of a box are also in row/column). This is the one corresponding to to the constraint V1 != V2 and is what is intended.

In discussion, someone suggested an alternative that involved the domain of the second variable. After reviewing the text, I'm sure this is *NOT* what was intended (consider the example given in the book), but is definitely still a valid degree heuristic. It involves the number of the active constraints between the *domain* of the variable under consideration and each element of the *domain* of each other variable it's connected to (or at least that's how I'm interpreting the suggestin). So if V1 can take the values {1, 2, 4} and V2 can take {2, 4, 5} it would contribute 2 to the sum. This corresponds to a FAR more lengthy set of constraints, essentially of the form "V1 ~= i OR V2 ~= i" for each value of i.

Anyways, hope this helps and doesn't confuse more.

LCV,

I'm not really sure what to expect. I know it's generally useful in conjunction with others (that's mainly how it's intended to be used, but seeing how they work alone is informative too). And it's sensible, since you want to pick the value that has the least chance of closing some critical door. But you're right that it also means that there's a larger search sub-tree involved, so it may be that *w/o* the variable selecting heuristics (which it sound like is your question) that it may actually backfire in some (or even many) cases.

Should LCV go faster than the blind backtracker? It seems that it could either go faster or it could go slower and really depends on the puzzle. So far, from what we have tested, our LCV heuristic goes slower than the blind backtracker. This is understandable because the LCV picks the value that constrains the other variables the least. This effectively means that all other variables have to try more values. Am I thinking about this correctly and should the LCV go slower than the blind backtracker?

Sorry Matt, this is Erik Peterson, I was in autopilot logging in, anyway that sentence is from out of the notes from the previous course.. its hard to read because \/ is supposed to be an 'or' and I didn't read it like that at first. Thank you!

Couple notes from Proj1:

Grades have two parts, written and performance.
Written:
-10 points writeup style
-10 points coding style
-10 points testing
-5 points graph
-15 points approach (Description of algs, correctness of approach, validity of conclusions).
Performance:
-10 Followed directions for running
-20 Ran to completion for each, finding solution if there was one
-20 Correct results
Extra:
10 points by original time
3-5 points state checking (depending on implementation)
3 pts IDA*
2 pts per heuristic that's dominates by Manhattan distance (ie worse)
5 pts for better heuristic (no one got this)
2 pts for Iterative/recursive depth first comparison

Penalties:
1 point to coding for repeated code (no solver abstraction)

-So far, the mean is 70%. But there'll be some flux with extra points I missed, a couple performance scores that are still being added, etc. A final report will be coming out once this has stabilized. A few scores w/o reports or who only implemented depth first are affecting the average a lot.
-Interestingly, projects with teams tended to do worse.
-A number of people said things like "ID (or A*) doesn't always find the optimal solution." Of the methods we had you do, only DFS wasn't complete and optimal under these conditions, and knowing this is part of what we expect you to know - so this should have been reported as a bug, not a claim. This is the sort of thing that might be on the midterm.

Here's a useful structure for your report to make sure you touch on everything (and make it easier to grade). Use it!

1. Files submitted (with brief description of each)
2. How to run (including unpacking, compiling)
3. Approach (describe algorithm(s)), problems encountered, hurdles overcome)
4. Known bugs (hopefully empty! But better to report than for me to find.)
5. Extra credit (can be empty - just because it's here doesn't mean you'll get points, but won't get points if not listed)
6. Sample output
7. Testing (convince me (and yourself) it works! Be thorough.)
8. Answers to questions
9. Summary

(I'll be adding some variant of this to the webpage, but wanted to get it out to you ASAP).

John,

<100 doesn't tell me much w/out knowing the scale (<100 could be a lot out of 150, not so much out of a million). Erik was getting the *same* number, because he was "visiting" nodes when they were added to the queue rather than coming out.

It's not surprising that there's a minimal difference w/o value selection heuristics, if you think about it enough. (Might want to discuss this in the report.) Part of the point is to see if you can get this difference larger by choosing values wisely.

But being equal, Erik's question, means you're doing something wrong.

P.S. I agree, we seem to be outgrowing the board. I'll look into something with more oomph. The AI group uses quicktopic a lot for classes, but there's generally not this much discussion.

mhtong(48)

I've been getting the same thing as Erik, the sum of the branching factor is usually only different by < 100 compared to the number of nodes visited. From what I understand the branching factor is when a new node is created, it is the sum of the number of possible values (1-4, 1-9, or 0-F) that the node can take that haven't already been eliminated through forward checking. Is this correct?

PS. This board is terrible, why don't we have webboard again? It is like a million time better than this single thread board.

Edited by author 05-01-2007 06:56 AM
Hwy9Nightkid,

Where's the sentence from?

The expression means that if x is such that Mary has x as a daughter, then x must be Joan or Beth. And conversely (since bidirectional), if x is Joan or Beth, then Mary has x as a daughter. If it were just =>, then it might be the case that Mary has no daughters, or only one daughter (Joan or Beth). If it were just <=, then Mary could have more than two daughters (as long as two of them are Joan and Beth).

The point is that this is how you would express the sentence "Mary has (exactly) two daughters: Joan and Beth" formally.

BTW, be nice to know who's asking...

Edited by author 05-01-2007 06:56 AM
Erik(45)

That seems wrong to me, unless you're *incredibly* unlucky.

Edited by author 05-01-2007 07:03 AM
Erik(44)

I think I answered this a while back on this board, but it was ages ago at this point. There's no problem with 9x9 using 1-9 and 16x16 using 0-15 - they just are all unique tokens, and the fact that they're numbers is unimportant (I've seen it done with just letters, for instance). Could we have done it 1-G? Sure. You could also conceptually place 0 after 9 (ie 0=10, A=11) if it makes you happy. Basically, we chose 0-F since it's hex, and that's actually a standard and potentially useful/reusable/already-done conversion. Plus if someone's *really* ambitious and wants to try not just 25x25 (which isn't required) but 36x36, this format will let them do it easily (*grin*).

I'll be testing using this format, though, so stray from it at your own peril... 4x4 => 1-4, 9x9 => 1-9, 16x16 => 0-F.

i dont understand what this sentence states..

To represent a multi-valued function precisely, we must use a complex sentence such as

       forall x has-daughter(Mary,x) <-> [ x=Joan \/ x=Beth ]

Be sure to understand the exact effect of the bidirectional implication <->.

The number of nodes visited is always equal to the sum of the branching factors for each node. Am I doing something wrong?

I have a question about using the values 0-15 instead of 1-16. The problem is that the practice puzzles supplied in the HW#2 pdf file contain practice puzzles that go from 1-9. In this case our code will look to fill up the puzzle with 0-8 values instead of 0-9. What should we do in this case? Can we just represnt the value 16 as G?

10 = A, ...., 16 = G?

Jesus,

It means connected in the constraint graph. If you've listed *all* constraints as binary constraints, the graph structure should be apparent. Think about it, and if you still have questions ask away.

Kei,

1) See John's answer.
2) I believe the plan is to have you submit during Gary's office hour, but stay tuned.
3) If it's not solvable, it should fail gracefully once all possibilities have been tried.

1) The reason it is 0-15 instead of 1-16 is because in hexadecimal 16 is "10", we do it as 0-15 so we can represent each entry in the board with a single digit. The highest digit in hex is F, and F = 15, so if we try any values higher than 15 we would need to use multiple digits.

Edited by author 04-29-2007 05:33 PM
Thanks Matt,
   I have other questions

1) Why for boards greater 9x9 will switch to 0-15 instead of 1-16 in your last post? If A=10, B=11, I think the board will have values from 1 to 9 and A to F, so it should be 1-16 but not 0-15.

2) As the due day is May 3 11:59:59pm at Thur, and the "Hard copies of write-ups are due at the beginning of class the following class", does it mean that the due day of hard copies is May 8 Tue?

3) Also, are the boards being tested always solvable? (our program can ignore testing it is solvable or not)

Kei,

Timer should probably be first line. But I'll probably actually be using the time reported by the system from when I enter the command to its completion, so it shouldn't matter as long as you specify. For your report, it's self-comparison in terms of time.

Use whatever methods you want for -best. The ones in the spec, class, and book might be a good start. Like I've said, some Sudoku-specific methods can capture some higher order constraints, but may be more efficient than implementing general higher-order constraints.

Edited by author 04-28-2007 08:31 PM
Thanks Tony.

For our project 2, when should we start the timer for calculating the excution time? As the first line of the constructor (i.e. before reading the file)? Or after reading the file but before creating the initial puzzle state? Or just as the first statement of the real solve method?

Should the timer be in ms or ns?

When solving with -best option, can we use other methods other than that mentioned in the spec, in class and in our textbook?

Hey Kei, I believe the Prof. postponed the midterm until May 10.

Edited by author 04-27-2007 07:28 PM
Will the mid-term still be held on May 3?
Will the review material/ lecture slides be posted?

Do you (or your group of 2) need a partner?

I'm a good person to work with. I have: good analytical thinking skills, MENSA IQ (though I'm not trying to be a jerk or something - I'd never announce that in person - just saying im not dumb), very friendly demeanor, strong work ethic.

Shoot me an email to thutchin @ (thedomain we all have addresses at).edu

You can also find me in class or often in B240.

:-)

Tom

Edited by author 04-26-2007 03:47 AM
>For question 6.10 of the homework, the problems says to pick
>"one or more of the following games". Will one be sufficient?

Yes.

For question 6.10 of the homework, the problems says to pick "one or more of the following games". Will one be sufficient?

Edited by author 04-25-2007 05:19 PM
> On the homework, for the third problem (5.5), I was wondering what it
> meant by a precise formulation. By this, do they mean give an initial
> state, a successor function, a goal test, and a path cost?

Not so much, no. That would be the form for general search. As a constraint satisfaction problem you provide a list of (hard or soft) constraints on the assignment of variables. Also describe your variables and domains.

This *could* be phrased as general search. You can either provide an initial state or have hard assignments as constraints (i.e. add something like x1 = 'red' to your list of constraints).The "goal state" is having all variables assigned and all constraints satisfied. Successors are just valid variable assignments. Usually, all solutions have equal cost, so path cost is constant, but you can add soft constraints (preferences) if desired by having different costs (we won't really be discussing this). However, this would miss out on all the great structure CSPs have that allow them to be solved so much more efficiently.

Edited by author 04-25-2007 12:12 PM
Proj 2 edit:
For 16x16 puzzles (the largest you're expected to test on), the .ss files will represent numbers in hex (10 => A, 11 => B, etc). If anyone wants to go higher, say to 25x25, just keep using letters.

Note that the fact that this involves switching from 1-9 to 0-15 doesn't matter, since only the uniqueness of numbers matters. And once you've read them in, they can be represented as normal base-10 numbers.

I noticed that the program is due May 3rd. Will the midterm still be on May 3rd?

Edited by author 04-23-2007 05:10 AM
Steffan,

Right. The s is key.

Where did you see the instructions? From the class assignment page: "More specifically: tar up your files, then type 'turnin -c cs150s [filename]' where [filename] is the name of your tarfile (the -c cs150s can be omitted if you've run prep, but better safe than sorry)."

EDIT: Found it in the course pdf. I'll let Gary know it's a letter off. Sorry for any confusion.

Edited by author 04-23-2007 02:28 AM
I'm trying to turn this thing in... and I found the instructions:

Use the "turnin" facility to turn in your programs. To use it, first "prep cs150" if you have an
OCE account. (Do nothing otherwise!). Then, simply type "turnin <filename>".

but I get this:

Source file information:
   source file name: hw1.tar
   source file date: Sun Apr 22 23:13:09 2007
   source file size: 194560 bytes
turnin: courseid cs150 is not valid.


EDIT:
I did cs150s , and I think that worked...

Edited by author 04-22-2007 10:23 PM
Clifton,

I'm not entirely sure I understand your question. Checking for previous states is, of course, optional. I think what you're saying is "what if a solution is beyond the limit by one path, but not by another, but the latter can't always be found because in some cases you already visited a node with the less optimal path." In which case I'd say don't worry about it, just increase your depth limit if you don't find a solution. Tim's comments are also appropriate here.

The depth limit is needed to ensure your program halts. If you didn't have a limit (and didn't implement checks for whether a state had been visited - which it DOES sound like you've done) you could loop forever, and when I tested your program I would have no way of knowing whether you were stuck looping or whether your code just hadn't found a solution yet.

When you compare nodes on the closed list (which we aren't required to implement), you have to compare how many moves it took to get there due to a path just barely being in reach. For the iterative deepening, you have to clear out the list, or (most likely better) just compare in terms of depth whether you got the optimal path to the node as per your last depth mark.

Edited by author 04-22-2007 03:40 AM
Hi, just had some concerns with Depth First Solver and Iterated Deepening Depth First Solver. If we have a specific depth limit, could this cause problems in terms of finding the right (not necessarily optimal) solution? For example, say we have a node that will expand to a solution but it is on the limit or say one before (and the solution node is a few levels lower). We put the node on the closed list since we "expanded" it. Now say some other branch will take us to the solution but has a node with the same state as the other "expanded" node. Since it is on the closed list, it won't be expanded, right? Will this be alright or should this not happen? If this shouldn't happen, what are people doing to avoid this?

Also, do we need to use the depth limit? My solver seems to be solving quite fast without a depth limit but runs out of space on 4x4 puzzles.

Thanks,
Clifton

Edited by author 04-20-2007 04:45 AM
Matt,

Just call me Kei :)

I have some thoughts about the blind uninformed search on this NP-complete Puzzle problem.
For DFS and IDsolver, I think the execution time (and also #states and #moves to sol) greatly depends on the order of successor visited.... for some cases I tested, visiting up first runs in 1 second, while visting down first takes more than 1 mins... while in other cases, the results are reversed... I wonder if the order selection of direction visit in DFS (and also in IDsolver) would cost me some point... (DFS and IDsolver were supposed to be blind uninformed search, not getting any information from environment)

Also for the BFS, when the size goes beyond 4x4 and optimal moves m beyond 15, I think it should usually be out of memory, since there will be closed to 3^(m-1) elements in the queue when the size increased (i.e. more than 4M elements, and each nodes should have size more than 32 bytes, which need more than the java default 128M memory)

Therefore I think it would be a problem to compare the performance of uninformed blink search.....


Here is some of my execution time and states visited.

For easy3x2, all of my Solver solved within 2ms, and DFS visited 103 states, BFS visited 2 states, ID visited 4 states, A* visited 2 states, IDA* visited 3 states.

For a 3x3 puzzle with 24 optimal moves:
8,7,3
6,0,1
5,4,2
My DFS is 1.5 seconds and 1650825 states, BFS is 11.5 seconds and 1494706 states, ID is 4 seconds and 4550781 states, A* with Manhattan is 0.04 seconds and 958 states, with misplaced tiles is 0.24 seconds and 32767 states, IDA* with Manhattan is 0.05 second and 1434 states, with misplaced tiles is 0.4 seconds and 117652 states

For a 3x3 puzzle with 30 optimal moves:
6,7,8
5,4,2
0,3,1
My DFS is 8 seconds and 9241658 states, BFS is running out of memory, ID is 72 seconds and 86733236 states, A* with Manhattan is 0.25 seconds and 32094 states, with misplaced tiles is 4 seconds and 798343 states, IDA* with Manhattan is 0.3 second and 59073 states, with misplaced tiles is 7 seconds and 2325622 states

For a 4x4 puzzle with 18 optimal moves:
6,4,0,2
1,7,11,3
5,8,9,10
12,13,14,15
My DFS can't finished in 5 mins, BFS is 30.6 seconds and 2095371 states, IDSolver is 2.5 seconds and 2335271 states, A* with Manhattan is 0.004 second and 38 states, with misplaced tiles is 0.043 second and 1094 states, IDA* with Manhattan is 0.003 second and 39 states, with mispalced tiles is 0.049 and 1602 states.

For a 6x6 puzzle with 48 optimal moves:
6,13,3,8,5,11
7,0,19,10,4,17
12,15,2,27,1,16
24,31,9,14,22,23
25,21,18,20,28,29
30,32,26,33,34,35
My uninformed solver sure can't finish in time :). My A* with Manhattan is 0.09 seconds with 2005 states, IDA* with Manhattan is 0.07 seconds and 1899 states, and misplaced tiles are running out of memory....

Are my results too worse? Do anyone get much better result?

Kei

Thanks for the clarification, so I am going to utilize some parents pointers, then when a solution is reached, backtrack towards the beginning..yes.

If I recursively reach a state I have already seen, for a DFS, how should it react?

Steffan,

C/C++ should be ok for this one, as long as your code runs ok on the school machines. (Although you're making me modify my testing scripts specially for you........) For the future, be sure to check ahead of time (as the assignment *requires*), as sometimes logistics will make it impossible. (If you don't know Java, notify me ASAP, as a common environment is required for games.)

-Matt

Edited by author 04-20-2007 01:56 AM
Kei Shun Ma,

You may loose some points if your solution is much less efficient than your peers. Off hand, your times seem marginally slow to me given the size of the problems you list. But of course, part of the point is the stunning advantage that even a decent heuristic gives you, and also that even relatively simple problems can explode.

What sort of solution times are people getting?

P.S. If I'm going to use a short, informal name, what would you like to be called? Full names seem so formal....

Edited by author 04-19-2007 05:30 AM
I want to know if we need to deal with large puzzles or one that have large optimal moves for ALL solvers. I have such question because the solvers have very different performances.

My informed solvers (A* and IDA*) are able to find a solution for large puzzles effectively (they are able to solve a 8x8 puzzle with 56 optimal moves in 30 and 15 seconds, and a 10x10 puzzle with 76 optimal moves in only 5 and 2.5 seconds...), but my other uninformed solvers are not even able solve a moderate puzzle with moderate optimal moves in acceptable time (for a 4x4 puzzle with optimal 18 moves, my BFS takes 35 seconds, while DFS takes more than 5 mins... for the same case my A* and IDA* take less than 0.01 second). But in general all solvers are able to solve a 3x3 puzzle in acceptable time. So I wonder if we need to tune up all solvers to solve puzzles with larger than size 4x4

errr i'm using C++, hope thats okay

Edited by author 04-19-2007 02:35 AM
Erik,

There's a distinction between states and nodes. A state is a particular configuration (of the board, in this case). A node contains a state, but also several other pieces of information, namely the cost to reach that particular state, the parent of the state, and the action that took the parent to the current node. If you make this distinction and are using Java (and no one's requested anything else) then the reference to the node's parent is enough to keep it accessible and Java's garbage collection won't get rid of it. Backtracking is then simply a recursive access of each node's parent. This kind of reference is very useful in AI (and in programming in general).

You COULD keep an array around and store indexes to the parent in the node. This is what you would have had to do if it we were using Matlab. However, part of the reason we're using Java here is exactly this kind of power. (It could be done easily in Lisp too, which is part of why Lisp is often used for symbolic AI. C/C++ has this power too, but one needs to be a lot more careful with it.).

Overall, the old-school style using arrays is harder to read, harder to debug, and not good style. PLUS, many of the pros/cons of the different methods is memory usage - if you're keeping the whole search tree around, then the differences can become pretty small in some cases.

Hope this helps.

Yes, it was a typo. Stephen is right.

Does anyone have a suggestion on how to keep track of the states? vs the solution paths? I am thinking i save the state of the puzzle as a 1 dimensional matrix(array)..but how can i backtrack over the moves?

It's supposed to be
> java DepthSolver easy2x2.txt

I'm guessing it's a typo.

I'm having trouble running the program by typing
"java DepthSolver.class easy2x2.txt"

It works fine if I use the jar file like this:
"java -jar DepthSolver.jar easy2x2.txt"
Does it matter either way, as long as it works or will we lose points?

Kei Shun Ma,

That is exactly what is meant. # moves = depth of solution. # states =
size of search tree.

(If you implement a check to see whether you've been to a state
before, be sure to document how you counted your states!)

In case anyone doesn't get the message (in which case please email me), the project is now due Sun 4/22, with the paper copy due in class Tues 4/24.

The text describes depth-limited depth-first search. If the depth-limit is 100, it simply does not expand any nodes to depth 101 (causing it to effectively backtrack).

This actually means I misanswered the earlier question regarding whether randomizing would help depth-first find a solution (I'd been picturing the unbounded case). Both randomization and ignoring previous states will not help find solutions that lie past the cut off, but they may help avoid looping behavior.

I'm revising the assignment slightly. The depth limit wasn't intended to be hard coded to 100 like that.

Edited by author 04-17-2007 03:39 AM
I want to make sure if I understand the difference between the two questions "How many moves to reach a solution?" and "How many states did you visit"

I think the first one means the "depth" to reach the solution (i.e. ignore all moves in all other paths), while the second one means the total number of moves (ignore moving the space back to original position) that the solver have run.

If I am wrong, please correct me.

Maybe i'm just confused about this implementation of depth search. Is it suppose to stop when it hits depth of 100 .. or is it suppose to act like an ID Depth with it's threshold set at 100?

After I changed it so that it would ignore previously seen states, it still doesn't find many equal states before it hits a depth of 100...

I think this problem is where we need to use the closed and open list implementations. Using the closed list we can make sure we don't repeat any previous states of the puzzle that have already been explored. Should work to solve your problem.

-Stephen

We hinted in class that this might/would happen. From the assignment description, "Did all your search methods succeed in finding a solution? If not, what could you do to remedy that (or what did you do to remedy it)?" Randomizing is one approach to fixing the problem, but there may be others (we discussed one in class at least briefly).

Edited by author 04-14-2007 08:45 PM
When we build our trees, should we randomly decide from the 4 possible states which our next state is? I had it at first creating the trees up,down,left,right in order, but realized that for a depth search that would cause it to loop moving the blank space up and down.

Steffan

I was asked about doing depth first recursively. Normally this can be a good idea and in the spirit of much of AI. However, since we're interested in the comparison between methods, you're probably better off with with the LIFO queue (stack) than with recursive calls (runtime stack). If nothing else, it definitely makes reusing your code for the different parts much easier.

If you are set on it, it's fairly easy to pass the necessary info to/from your calls. Or if you can get a measurement of the amount of memory used by the recursive calls vs. the amount of memory the queue data structure uses, that would be acceptable.

Exploring which works better here, recursive calls or a stack data structure, could be worth some extra credit here. Memory usage or execution times would both be possible ways of exploring this.

Homework 2 has been posted! I expect Gary will be sending out a more formal notice (if he hasn't already), but I wanted to give people a heads up.

I dont understand what is being asked in homework problem 3.3
I know the successor function is composed of legal actions and their results, but how do I define these results and actions in terms of the sucessor function? Thanks

G.

This is where you should ask questions about assignments,
lectures, etc.

When asking questions about assignments,
PLEASE DON'T POST LARGE AMOUNTS OF CODE!

A few lines are ok.

Thanks!
fearless leader