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

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.

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 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.

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

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).

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

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...

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.

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.

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.

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!)

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?

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

I'm guessing it's a typo.

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?

Yes, it was a typo. Stephen is right.

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.

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

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

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....

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

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?

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

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

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 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.

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-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.

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

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.

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.

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-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.

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-27-2007 07:28 PM
Will the mid-term still be held on May 3?
Will the review material/ lecture slides be posted?

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

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?

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-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)

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.

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.

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.

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?

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

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 <->.

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.

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 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...

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.

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.

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).

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.

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!

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?

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.

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.

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?

Robin:

CSPSolver.java test.txt -mrv -dh

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

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

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

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.

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)

Anon,

No. And it wasn't extended.

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).

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...

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

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?

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....

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

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

IENG6 IS BROKEN.

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'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 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?

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

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.

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

Josh,

Chapters 1-9 and lectures up to last Thurs.

Minor tweaks to Player class.

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

thank you

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

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

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

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.

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.

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)

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-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 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.

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-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.

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: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)

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.”

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!

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?

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

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?

Kei,

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

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...?

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 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.

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 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.

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.

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 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.

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)

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?

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.

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.