הטכניון - מכון טכנולוגי לישראל Technion - Israel Institute of Technology Технион - израильский технологический институт ألتخنيون - معهد تكنولوجي لإسرائيل

02360501 - מבוא לבינה מלאכותית 02360501 - Introduction to Artificial Intelligence 02360501 - Introduction to Artificial Intelligence 02360501 - Introduction to Artificial Intelligence

חורף 2008-2009Winter 2008-2009Зима 2008-2009شتاء 2008-2009

שאלות ותשובות Frequently Asked Questions Вопросы и Ответы أسئلة وأجوبة

Exercise #2

Can we assume anything about the game parameters?

You can assume the following:
0 < C < 100, 0 < R < 100, 0 < N <= max(C, R), M >= N, 0.1 <= T <= 20

Can we use code from the internet? (e.g. for the alpha-beta algorithm)

Yes you can, and state which parts of the code aren't yours and state their source(s).

What is CSL1 and how do I access it?

csl1.cs.technion.ac.il is the students/courses server.
The tournament will be run on this server.

If you are CS undergrads, you should already have an account on this server. Your username/password should be the same as those you use to login to computers in the CS computer farm (also, your Z: drive / windows/linux login data resides on this server).
If you don't know your username/password or have forgotten them, please contact the helpdesk in the computer farm.
Also, you can try to reset your password using: http://linux-sup.cs.technion.ac.il/change-password .

If you are not a CS undergrad, you should have an account on CSL1 if you are registered to a CS course, with your T2 username as username and your ID# as initial password.
If you don't have an account or don't know your username/password or have forgotten them, please contact me and I'll try to sort it out.

CSL1 can only be accessed from within the Technion network, and only through SSH, so you have to "ssh uyourusernameatcsl1.cs.technion.ac.il" from T2/TX/CSD etc. if you are outside the Technion network (e.g. at home).
Use sftp or scp to transfer files over ssh (see their man pages for usage instructions).

It is important to compile and run your programs on CSL1 or a similar machine in order to avoid problems related to g++ versions.
CSL1 uses gcc/g++ v4.1.2.
If you decide to use your own linux machine/VM / cygwin, please take care to use this version of g++, and to not use any nonstandard extensions to C++ (e.g. STL is allowed, libboost is not).

Whatever development environment you choose to use, do remember that the exercise will be checked on CSL1 so you still need to test it there.

Are the player's construction and initialization times parameters of the program?

No, they are always 1 and 10 seconds (respectively).

In main(.) the interactive player is defined. How will our player be loaded?

The tournament's main(.) will be dynamically and automatically constructed at the beginning of each game.
If you follow the .h file writing guidelines, my script will parse your file/class correctly and will plant your player's class in that main(.) function instead of the interactive players that are constructed in the demo main(.) you now have.

Can we rely on the internal structure of ConnectNBoard? Can you change the members of ConnectNBoard from private to protected so that we can inherit from it?

You should not rely on the internal structure of any class other than Player and its inherited classes (that includes your own player).
Rely only on the interface of the classes given to you. Use their public methods to extract whatever information you need, and for a change of functionality (e.g. a board with a matrix rather than the current vector<vector>) construct your own class (you may freely use the code supplied to you).

Your programs will run with a system that is similar but not necessarily identical to the one supplied to you, as the latter is only for easing your development of the player.

We chose to implement extension X to the alpha-beta algorithm. Must we do the parametric research that is associated with it in the exercise paper?

No. These parametric researches are just examples of what you can do.
If you find other interesting parameters you'd like to research, you're more than welcome to do so instead of researching the given examples.

You wrote we'll lose 10 points if we have compilation warnings on csl1.
What is the build command? "g++ -Wall / -pedantic *.cpp" gives warnings, even on the supplied files.

The compilation command against which your programs will be checked is "g++ *.cpp".
This gives 0 warnings on the supplied files (or at least so it should).

Exercise #1

What is the weight of this exercise in the final grade?

First, regardless of the hw weight, you must know that the exercises are mandatory in order to pass the course.

The total weight of the HW exercises in the final grade is 40%. Currently, two exercises are planned with equal 20% weight.

I have a few questions regarding the exercise, could you answer them?

Sure! here we go:

You must reach a total of k appearances of the goal string, not add k appearances.

Goal appearances do not overlap. If the goal string is "aa", "aaa" contain a single goal appearance.

X and Y are fixed parameters of the algorithm, and you can assume they are defined at the beginning of the search.

All your enzymes, aiding strings, and goal string are given at the beginning of your search, as part of the initial conditions of the problem. They can be different between two different problems.

The aiding strings can be of different lengths (as the example shows).

Your algorithm should be able to run on any initial conditions and different values of X, Y, n, k. It is your responsibility to create experiments where you set these initial conditions in a way that would allow you to answer your research questions.

If a minor detail in the exercise isn't specified, and common sense doesn't help, you can assume whatever you want as long as you mention it clearly and it doesn't contradict anything else specified in the exercise or FAQ.

The number of pages for the report is limited (see exercise document). However, do not mistake this for an excuse to exclude important topics. If you have, for some reason, too many things you want to write - select the most meaningful and important topics in your opinion.

Does the cutting enzyme really cut everywhere it finds a match in the DNA string? Can't I put it only where I want to cut?

You can't.

Biologically the idea is that you put the DNA with the enzyme in a test tube, and stir it up. The cutting enzyme attaches to everywhere it finds a match without any choices - and cuts.

Can I use the cutting enzyme on the aiding strings?

You are right, this was not defined before.

Yes you may. It will cut everywhere and you can use each segment as a new aiding string.

Could I have decided, in the example in the document, to glue only one side of the aiding string?

Yes, you may attach the aiding string to any or both of the two open ends of the input DNA string.

You said I can use the enzymes and aiding strings in reverse.

Does this mean I should count the goal strings entered in reverse as one of the K required appearances?

Good question!

The answer is NO! Goal strings are only counted in their original direction.

Can we reverse the whole DNA string? That way, we can put reversed goal strings and then reverse the whole DNA for them to count.

Good question. Nope. The example was simply wrong. Sorry.

Can we use the paste enzymes on the aiding strings?

No. You can only glue aiding strings to the original (cut open) DNA string.

What is a typical size of these sets of cutting enzymes and aiding sequences? This obviously greatly affects the branching factor and the whole solution...
What about the other parameters? What sizes of enzymes should we experiment with? What sizes of DNA strings? what is a reasonable X, Y, n, K?

We are avoiding this question on purpose because we want you to think about it. These are great questions for you to experiment with, and report about.

We do not require that you use "real world" values, but if you're curious about them: human DNA length is ~ 3 billion, cutting enzymes ~6, aiding sequences could be a few hundreds. The pasting works a bit differently then what we said here, but usually Y < 6.

The only hint we are willing to provide is that you solve problems that you are able to base some statistics on, and not necessarily because they were very easy.

Wait, are the cutting enzymes unlimited too?

Yes. Didn't we say so already?

Do we need to enter EXACTLY K goal strings to the DNA, or AT LEAST K?

At least K.

Cutting aiding strings really complicated things...

There have been complaints about the option to apply the cutting enzymes on the aiding strings. While we do not necessarily agree with the reasons why this is problematic, to make a long discussion short, we have decided to allow you to choose one of the two options:

1. Cutting an aiding string is allowed, and is considered an operation just like any operation in the problem (cutting, gluing, etc.). You can cut an aiding string to create new aiding strings, and then cut the result as well, as many times as you like.

2. Cutting an aiding string is NOT allowed.

In both cases, you are not limited in the amount of times you use the cutting enzymes on the full DNA string, the aiding strings, or the new aiding strings generated by cutting old ones.

State your choice clearly in the document and explain its consequences.

Do we care about solution length etc.? Do we have to provide the path, or just the final string?

That is for you to figure out from the problem description. Please think this through.