I suppose he could read an entire database of games into RAM. If we assume a rough upper bound on the number of moves of 361 (19*19), with each move represented in 2 bytes (a byte per coordinate) and then round up to the nearest kilobyte (because working with multiples of 1 is easier), that gives us 1kb per game. You could easily fit a few hundred thousand of such into RAM these days .


Does that change anyone's answer?

_________________
19/02/2011: this grumpy person takes a voluntary holiday from L19.

What do you mean?

_________________
"Those who calculate greatly will win; those who calculate only a little will lose, but what of those who don't make any calculations at all!? This is why everything must be calculated, in order to foresee victory and defeat."-The Art of War

I was just wondering what assumptions people were making when suggesting languages and whether a little more context might change their suggestions, though mostly the advice has been somewhat general, so I think it probably won't change.

_________________
19/02/2011: this grumpy person takes a voluntary holiday from L19.

"Furthermore, a higher level language (which according to some benchmarks may be slower) may make it easier for you to select the right data structures and algorithms, reducing the algorithmic complexity of your end result and actually giving you a program that solves the problems you are interested in faster"

See -- I am disagreeing totally with this. The selection of data structures and algotrithms should be taking place in the design phase where everything is still at an abstract level and haven't decided things like "what langauge will this be implemented in" (of course that might be a "shop standards" issue, already predetermined which langauges allowed for production programs in the shop --- maintenance of programs usually a more important consideration than a slight improvement in the efficiency of any one program so sensible to restrict the number of langauges a shop has to have experience on hand to support).

If you instead start with the langauge and what data structures and algrotihms come built in then you are very likely to make data structure and algorithm decisions based on that and can almost guarantee bad choices.

IMO, prototyping in a high level language is the design phase.

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

I can see some advantages to this in the later portion of the design phase, but sitting down with pen and paper (usually using actual pen and paper) at the beginning of the design phase and putting down the fundamentals has always worked better for me than blind (or semi-blind) prototyping as you describe above. Jumping in and hammering out a quick code prototype has its usefulness, though, I do admit.

There is not a single best way to do design (as there is not a single best programming language)

_________________
Offending ad removed

Care to try an example? After retiring from a career in large financial systems I decided to treat myself to learning C. For a "case problem" I chose writing a compress/decompress pair for a finite version of the Lempel-Zev 2nd Universal Data Compression algorithm. Definition:

Given an initial dictionary, transmit the number of bits that are the ID of the longest match in the dictionary followed by the character caused the mismatch and now add that string (the one that matched plus the character) to the dictionary. In the finite version, once the dictionary has reached some maximum size, remove the least recently used dictionary element in order to add the new one.

Sorry but I can't show you my solution as had a house fire in 2006 and backups did not survive the heat (now kept in a fire safe with a copy in a different building). But this wasn't a particularly large program. Part of this learning exercise was "standards" so had all the features like "about", "help" etc. and was heavly commented and I don't cram stuff on a line and still the compress/decompress program (could do either) was well under 2000 lines.

What I'm trying to say here is that how could you prototype in a high level langauge first? Without first visualizing what sort of structures you will want for "dictionary", "dictionary element", "least recently used", etc.

Well, C is not exactly a high-level language. I'm thinking something like Python. And my statement was hyperbole (depending on the size of the project). But prototyping parts of the problem is a large part of the process.

So I might start by just picking one of the more interesting functional units, like the dictionary search and just get it working with whatever data structure was convenient and a completely naive algorithm like a linear search. Just to get it working - maybe it'll be stupid and slow and only work on a data set, but I just want to have some logic there to look at. Just doing the simplest thing that could possibly work.

Then I'd decide if the simplest approach is "good enough". Sometimes it is. Sometimes it needs some trivially improvement to be "good enough", like a binary search, or a hash table.

I'd repeat the process for other parts of the program, keeping in mind what I'd learned from other parts I'd worked on, and make refinements along the way.

For me, trying things out is the best way to get a feel for the problem. I'll have a much better idea of what sort of data structures I'll need, what the pitfalls are, what the bottlenecks are, etc. once I've played with some actual code. And in a language like Python, you're almost writing pseudocode, so it's not much different than hashing out ideas on paper, except you can actually test it out.

Granted, my day-to-day work is database backed web sites, which tend to be completely uninteresting from a CS/algorithms point of view.

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

Gee, and I thought the advantage of "high level" languages was supposed to be that they directly supported high level structures.

"So I might start by just picking one of the more interesting functional units, like the dictionary search and just get it working with whatever data structure was convenient"

Search what? (what is the structure you will search)

Here's a hint -- the dictionary structure that would be "convenient" for this problem is the "n-tree" and as the stream in input characters come in you don't "search" it but traverse it to the farthest node you can reach (that's the longest match). The character coming in that didn't match would be added as a child (added to the child list of this node). Don't be misled by thinking that conceptual string matching means any need to store strings as a data type.

For the nodes you might try a structure that had an ID (an integer) and a value (the character) and a number of links. Going to have to be able to delete as well as add nodes and be able to traverse backwards from node to root and to keep track of least recently visited. So links to left and right sibling, link back to parent (for decompressing), link down to child list, link to next more recently and next less recently visited. While the dictionary is below mamimum size these can be kept on an "available" list assigning one of the links for that purpose.

Look, I chose this example precisely because while parts of the structures handy would be available as built in objects in a higher level language like C++ others would likely not (does it have an "n-tree" primative? -- the more common "b-tree" perhaps). And of course because making heavy use of linked lists (mainly double because intensive moving nodes around and the need to traverse both ways).

Diving right in to code is a bad way to do any program more difficult than you can visualize in its entirety in your head (for me that might be substantial). If you think you might even have to "hunt and peck to see what works" you've bitten off more than you can chew that way. Design top down and design first.

We're talking past each-other. Mucking around in code to get ideas doesn't preclude top down design, it informs it. Rapid prototyping in software is quite common these days.

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

I did not read the whole thread, just the last few posts.

Mike, you seem like a competent coder. I'm going to guess you're professional coding experience was from, say, late 80s to early 90s. To be frank, though, much has changed in what is considered "best practices". Most of your experience as far as project planning would probably be considered out-dated in the modern workplace (with the exception of work on embedded systems probably). Out is the idea that you should design everything upfront, and in is the idea that you should get something roughly working NOW and iterate on it. The idea being that clients are stupid, and even when they tell you what they want they have no idea what they really want. Even (and especially) when the "client" is you, the coder.

See Waterfall model vs. Iterative development.

So I'm going to side with fwiffo here. Get your SQL database of go games or whatever, and your language (python is as good a choice as any, though I'd personally prefer C# because of the IDE), and just hack away with really naive code to get something that more or less works. Be as naive in the implementation as you need to be to get it working fast (fast meaning how much effort you put in. Not in how fast it runs). Then use it (play against it), and refine.

_________________
1k KGS

How did this come to sides?

My personal opinion on business practices (past and present) is that different projects benefit from different design processes, and a good number of modern code houses (from small operations to enterprise) have become smart enough to tailor their design processes to each individual product. (And, of course, there are a good number of code houses that cling to a single design paradigm, with mixed results.)

My personal design preferences: design first. Forgetting about work processes, I prefer to design my personal projects before writing them out. I get things done quicker that way.

This doesn't mean I won't design iteratively and prototype early when the need arises. It simply means I like to start with a set of non-trivial requirements fleshed out before I start writing code. Makes my personal coding experience much smoother and easier to handle, given that I spend less time in front of a computer screen ... I don't like spending long periods of time writing code.

For the record, I currently do code as part of my position at work. I'm happy because it's not my entire role, and I can switch gears frequently throughout the day to keep my brain going.

If I might argue against myself for a second, it actually really depends on what you're doing. Mike's example is a very precise specification, which makes a very planned design a lot more possible.

But here's a fictitious but typical specification that I see regularly in the sort of work I do (web stuff).

----

The client wants a web site. They don't know what they want it to look like, but they have a couple competitor sites they want to look better than, and they have some other web sites that they like the look of. His daughter is an art student and thinks the color blue is really great.

The site needs to be easy for them to update, and it also needs to have a way for their clients to search their inventory. They have a separate inventory system which our code will need to import from. They can't tell us anything about the file format it exports, but they can give us an example file. They're not sure yet how we can automate the export process. They also don't know what the search form on the web site will look like, or what fields it will be searching.

They also have some flyers, manuals, and marketing literature that can be cribbed from for the content of the web site.

----

That specification is obviously terrible. But that's what I have to work with. And I also know it's going to change every time we talk to the customer.

The first thing I need to do is roll out an instance of our (constantly changing) content manager. We need to have that in place immediately so that our content people can start putting in web site content, even though we don't have a design or any of the custom features done, otherwise it would take too long.

Next I need to get started to work on the custom code for the site (the inventory import and search) even though the specification is maybe 10% complete. I can't wait until the graphic design or content is done, or until we know more about how their inventory export works, otherwise it will take too long to get the site out.

The best way to get started on that is to take a look at that sample file and see if I can figure out what's in it. I may or may not be able to find an exact specification for the file format - they have some weird in-house system which might not even have a specification. But it's almost always CSV. I just need to figure out which flavor, what character encoding, and what the different fields are, and how they're related. The best way to do that is to write some quick-and-dirty code to parse the sample file and print it out in a human readable format.

Once I've figured out the file format, then I can design a database schema that can represent the data and write a script that can import that data in an automated way. I still don't know if I'm going to be getting it from an FTP server, or if it's going to be manually uploaded somehow, or from a SOAP call or what.

Once I've got some sample data in the database, I can write the search. I pretty much have to guess how they want the search to work because the client isn't ever going to be able to articulate it. But I can make a pretty good guess because I've learned about how their data works from reverse engineering their file format. Once I have a prototype search coded, we can show it to the client and see what direction it needs to go from there.

----

That's the sort of situation where I think this sort of prototyping and playing with code is most helpful. The specification is incomplete constantly changing, and the project is not terribly large. If you have the luxury of a detailed specification, you can do a lot more up-front design.

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

Well, even with so-called lightweight methods, you still need to have some idea of what you'll be doing beforehand. I suspect that if you can just jump in and be successful with apparently little thought, then you're simply underestimating what thought you're actually putting into it or the results of prior experience allowing you to rapidly choose a roughly appropriate solution. Just as in go where a strong player might be able to play flexibly without planning out his whole game because he's built up the unconscious mental machinery to evaluate board positions quickly and identify what moves may reasonably lead to workable strategies.

_________________
19/02/2011: this grumpy person takes a voluntary holiday from L19.

In go terms, imagine if you could undo an arbitrary number of moves when it became clear that a line of play doesn't work, and then continue play from there. That's like iterative development.

A certain level of expertise is still needed to be successful, of course, but that's true regardless of the techniques you employ. If you can't design the system iteratively, you certainly can't design it all up-front either since you don't have the experience. At least prototyping gives you a way to get the experience

Actually that would be an interesting experiment: pair a new go player with a score counter and infinite undos and see how strong they could end up playing (probably against a computer since human players wouldn't have the patience).

_________________
1k KGS

In go you can simply start over every 30 minutes (or so), and as you get better you have your thoughts checked by stronger players naturally through just playing them.


Well, if you're asking a novice programmer to just jump in and start prototyping as a way to get experience, I would suggest that they're going to spend a heck of a lot of time reinventing every wheel up til the current day that's ever been invented in computer science ... I think I'd suggest they read a few books first :p. However, I don't think that's what you're actually suggesting, again, I think the unspoken assumption is that they already have some ideas for how to approach the problem.

I agree that they're going to spend a lot of time getting things wrong and rewriting code. It's just a question of how far to take the design part before you start writing code. The more experienced you are, the more goes unconscious thought will go into the design part. Novices will only be able to read a couple of moves ahead before getting confused.

Note: I can't figure out if I'm disagreeing or agreeing with you. Or what I'm trying to say, even ... eh, well don't mind me :p. Just take this as my iterative method of getting thoughts out . Maybe in a few more posts I will have something reasonably coherent!

Maybe we can draw a comparison between tsumego and designing everything explicitly. They both force you to develop machinery to work everything out in your head instead of having to play actual moves. Ok, maybe that doesn't really work as a comparison.

[edit]
Ok, here's something that's hopefully more coherent:




I agree with both of these statements. I think the disagreement between you both is what constitutes a high enough level language. Of course Mike expresses and works out his designs in a high level language, he simply considers existing programming languages to not be high level enough. If we could execute his language, then Fwiffo would argue that he's doing rapid prototyping. On the other hand, if Fwiffo would pick a language that didn't force unnecessary assumptions or models of thinking on Mike, then Mike would consider such a language an effective tool for use during the design process .

_________________
19/02/2011: this grumpy person takes a voluntary holiday from L19.

"If we could execute his language, then Fwiffo would argue that he's doing rapid prototyping. On the other hand, if Fwiffo would pick a language that didn't force unnecessary assumptions or models of thinking on Mike, then Mike would consider such a language an effective tool for use during the design process"

Sort of the right idea, but .............

a) I am assuming that I will have a "machine" to execute (or evaluate -- we have "functional" programmers reading this) this imaginary language. In other words, as soon as I have the problem solved in terms of the data sturctures and operations on them of this imaginary language all that remains is to emulate those using some real language. That is going to be easy (and easily testable in pieces)no matter what the real language used.

In effect I have broken the problem into two parts, a high level solution testable on paper (correctness proofs) and a low level solution to implement that high level "machine" (each part of which is small and testable in isolation).

b) Except that for any real language you name it doesn't matter what finite set of goodies it comes with built in. I could always find an example problem which called for abstract constructions it did not already contain.

c) The sorts of things by which I decide a language convenient may be different (example: are variables and functions (names) local or global? -- I detest having to deal with "data dictionaries"). Choices here differ. The reason why C and Unix shells appear lower level than they are is that they devised by engineers in the Bell lab who preferred memorizing bizarrely shortened names/spellings to entering more keystrokes.

From my point of view it doesn't make much difference what language is used to implement the inaginary machine that solves the problem. The bits and peices are small enough the advantages of one language over another is comparatively small.

For somebody who doesn't have experience programming, the choice of language should probably one that facilitates learning, not worrying about performance or anything else like that. But the better question is "how do I learn how to write software."

Writing the fanciest go game database in the world is probably not a good starting point because that's a pretty advanced task.

A good first program is one that just prints "Hello, world!"

A good second program might be one that takes a decimal dollar value as input (e.g. 24.32) and then prints out the necessary bills and coins to produce that value.

A good third program might sort a list of numbers.

A good fourth program might do the same, but efficiently.

etc.

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

I disagree somewhat.

Yes, the first thing with some new language is to see how one obtains the output "hello world" (and then perhaps some of the others, but not "devise an efficient* sort algorithm". By some simple exercises which you have done before (in other languages you can quickly see how this language does things differently.

But that isn't about learning "programming" (the design of correct programs)

Just "try it and see" is why most programs contain bugs that surface later (a randomly selected test set is almost certain not to be testing all possible conditions).



* Sorry, but if you have the competence even to determine "this sorting algorithms will execute in n*lg(n) time" then you are far from a beginner in programming. Especially when you throw in the special case consideratons like "already almost in order" (that changes things)