Feeds

back to article Chess algorithm written by Alan Turing goes up against Kasparov

Chess grandmaster Garry Kasparov has played one of the first computer chess programs ever created, written over 60 years ago by Alan Turing. Credit: VideoLectures.net As part of the University of Manchester's Alan Turing Centenary Conference, Kasparov took on Turochamp, an algorithm that Turing wrote by hand, but never had …

COMMENTS

This topic is closed for new posts.

Page:

Facepalm

I think I'm hungry

My first thought was what the hell is a cheese algorithm, and what would it have to do with mathematics.

9
0
TRT
Silver badge
IT Angle

Re: I think I'm hungry

START:

WHILE rare_bit = 1

IF available_bytes >= 1 THEN

MOVE bite;

ENDIF

IF available_bytes <1 THEN

MOVE nibble;

ENDIF

ENDWHILE

END:

8
0
Bronze badge

Re: I think I'm hungry

There's a much more efficient algorithm for dealing with sparse rarebits:

// how many bit(e)s in rarebit?

unsigned int bites (unsigned long rarebit) {

for (bites=0; rarebit; ++bites) {

rarebit &= (rarebit - 1);

}

return bites;

}

1
0
TRT
Silver badge

Re: I think I'm hungry

I like my rarebit with both pepper and mustard. Does anyone have the code for this using two condiments?

1
0
Joke

Re: I think I'm hungry

I have it in Perl, but the comments won't accept the syntax and you wouldn't be able to read it even if it did.

1
0
Pint

Performs exactly the way a real human would

<----What, it took one look at the opposition, conceded and went out for a swift one of these?

8
0
Silver badge
Linux

"He wrote algorithms without having a computer – many young scientists would never believe that was possible. It was an outstanding accomplishment" -- Designing your code is actually part of the system development life cycle. Ever heard of pseudocode?

11
10
Thumb Up

Whenever I had to do that in university programming modules, I'd always submit it in a long comment at the header of my code (or the main file if there multiple files/classes involved).

0
0
Silver badge

Miek...

... be fair! There's a difference between writing pseudocode before you go to the computer and writing it before the bloody thing has even been invented :-)

BTW: match is at http://www.chessvibes.com/reports/garry-kasparov-versus-alan-turings-1950-chess-program, worth a look.

34
0
Ru

"Ever heard of pseudocode?"

Has anyone actually ever used pseudocode, outside of 'intro to programming' type courses? It ism after all, a collossal waste of time. Specifying an algorithm to a useful degree without handwaving is practically the same amount of work required to actually code up that same algorithm in an appropriate language, modulo a few bits of punctuation or whitespace.

I'd venture that compared to some appropriately expressive programming languages, waffly English specifications can easily be less clear to read, more awkward to define and a lot more verbose.

10
16
Silver badge

Re: "Ever heard of pseudocode?"

Flow charts are pseudo-code

Specifications are pseudo-code

5
2
Anonymous Coward

Re: "Ever heard of pseudocode?"

Are meaningless overgeneralisations also pseudocode?

4
0
Silver badge

Re: "Ever heard of pseudocode?"

'Flow charts are pseudo-code'

Box 1: Input required data.

Box 2: Process input.

Box 3: Output required data.

11
0
Anonymous Coward

An indictment against the state of young scientists today, more than a laudation of Turing. Yes, he was a brilliant man, but I'm pretty sure most mathematicians at the time (which is what he was) were aware of this concept called an 'algorithm', without needing a computer to bash it into.

7
0
Silver badge
Linux

Re: Miek...

Sounds rather like a homework assignment from the class that teaches you about Turing Machines.

People tend to forget that this stuff exists in the total absence of any hardware.

3
0

I reckon Alan Turing is l337

3
0
Ru

Re: "Ever heard of pseudocode?"

"Flow charts are pseudo-code"

"Specifications are pseudo-code"

If they are isomorphic to an actual algorithm, then they may as well have been written in a programming language in the first place. If they are not, then they are handwavey wishful thinking; more pseudo than code.

5
6
FAIL

Re: "Ever heard of pseudocode?"

If they are isomorphic to an actual algorithm, then they may as well have been written in a programming language in the first place. If they are not, then they are handwavey wishful thinking; more pseudo than code.

--

Thats kind of the point of a spec though, isn't it. Its a statement of intent, an conceptual representation of something that will be made real in code later on.

If you do commercial coding, you get a spec of what is supposed to be implemented, you make some tests to prove you've delivered it (of whatever variety) and the code that is the specification made concrete.

Being able to represent an algorithm in both a logical spec and in code is a good idea, forcing you to consider the problem at hand, rather than getting caught up in syntax of your chosen language.

They are an abstraction, and totally necessary for a problem beyond the trivial.

6
1
Ru

Re: "Ever heard of pseudocode?"

I draw your attention to my original statement:

"Specifying an algorithm to a useful degree without handwaving is practically the same amount of work required to actually code up that same algorithm in an appropriate language, modulo a few bits of punctuation or whitespace"

Anyone care to disagree?

So, on to your point,

"Being able to represent an algorithm in both a logical spec and in code is a good idea, forcing you to consider the problem at hand, rather than getting caught up in syntax of your chosen language."

So you don't seem to have contradicted me, but you are in favour of writing the same algorithm twice, once in a form where it isn't particularly useful. Pseudo indeed!

3
7
Thumb Up

Re: "Ever heard of pseudocode?"

I use it, very often, when *designing* algorithms. I find it invaluble for stripping away the language specifics and capturing the functionality. If find it clearer to "see" an algorithm in pseudo code, and its a doddle to transfer a pseudo code description of an algorithm to most programming languages. I also believe that the code produced in this manner can be often easier to read, especially if you transfer the pseudo code naming into the final code, as the naming will usually illustrate the "why" (and not the how). I have also on several occasions been very grateful for pseudo code descriptions of some classic algos, so I can implement my own.

How useful would Turings chess playing algo be if he left it to the world as Colossus paper tape instructions?

2
1

Re: "Ever heard of pseudocode?"

"Has anyone actually ever used pseudocode, outside of 'intro to programming' type courses?"

Yes, all the time. It's often simpler to write a few lines of pseudo-code to explain to our offshore build team what we're expecting them to do than draw a complex diagram or wax lyrical for several pages. Plus pseudo-code is easy to include in a text only email and not having all the weird punctuation means it's easy for business analysts to understand and validate it.

As to whether it would be quicker to write the code directly, sometimes yes, sometimes no. In particular, when writing pseudo code I can gloss over details like import statements, class/function declaration, etc.

5
0
Ru

Re: "Colossus paper tape instructions?"

...are not the same as source code.

As regards your algorithm design, "I find it invaluble for stripping away the language specifics and capturing the functionality", I shall once again go back to my original point, specifically, "actually code up that same algorithm in an appropriate language".

An algorithm that is principally mathematical in nature translates exceedingly well to ML; if I write it in F# it can be dropped into a .net application with ease; Scala isn't so functional but will suffice in java-land. Less mathematical algorithms I tend to prototype in something like Lua or Ruby. The syntax is clean and straightfoward, and the results of the prototyping are immediately visible. In the case of the latter, JRuby classes can easily work with JVM based systems, and IronRuby targets the CLR. Lua certainly has a JVM-friendly version (not sure about CLR these days) but also interoperates exceedinly well with C and C++. Regardless of platform, I've created working code which is every bit as useful as a handwavey design document, only it is already working.

Optimisation, if needed, may follow and may include porting to a less abstract language, but with the advantage of having a genuinely functional implementation to work from.

2
3
Gold badge
Happy

Re: "Ever heard of pseudocode?"

What's all this stuff here? I didn't know there was planning going on. I thought you programmers just went into a room full of pizza and coffee, and just started bashing away at the keyboard. Only coming out once either the pizza and coffee is exhausted, or your beard has grown so long it's obscuring the keyboard... At which point, the program is declared finished, and released.

8
0
Ru

Re: "Ever heard of pseudocode?"

"Yes, all the time. It's often simpler to write a few lines of pseudo-code to explain to our offshore build team"

This is always interesting. At what point is your spec ever detailed enough? I've encountered offshore dev teams whose ability to understand an abstract spec is minimal, and who generally end up being little more than a human macro expansion system who turn a practically fully functional algorithm (eg. isomorphic to actual code) into something that compiles.

"pseudo-code... not having all the weird punctuation... [is] easy for business analysts to understand and validate"

Have you considered using COBOL?

1
4
Anonymous Coward

Re: "Ever heard of pseudocode?"

Right, except we're not allowed to write much code these days. Instead, we specify it, hand it off to an offshore team, write tests and then verify their work.

Since their work often resembles gibberish at that point, inserting pseudo code of how I expect an algorithm to work gives them an idea of what they should be writing (and something for me to beat them with if they deviate from that algorithm).

3
0

Re: "Colossus paper tape instructions?"

"Regardless of platform, I've created working code which is every bit as useful as a handwavey design document, only it is already working."

I find that the added constraint that the code must also be well formed within <language of choice> is unhelpful, to me, when designing.

Also, this isn't a "handwavey design document" - its an exploration of the problem domain, without the need to compile/interpret anything, or run anything. To each their own however - I would have no issue with someone writing 'pseudo code' which was also working Lua etc.

1
0
Terminator

Re: "Ever heard of pseudocode?"

You may have confused "pseudocode" with management level "specifications".

0
1
Ru

Re: "You may have confused "pseudocode" with management level "specifications"."

Pseudo.

0
1
Boffin

We are not all as smart as you are

Back in the day, we had COBOL, and sometimes CICS, and frequently a database -- or not. We also had teams. The best results came from communicating to the end users and the team members in some sort of common language. We used flow charts, pseudocode, and sometimes a sort of graphic prototype for screen flow. We also used something we called structured programming, which is more natural to the modern programming languages, starting with PL/1.

The prototype, if any, was contained in the structured program, in which control passed to PERFORMs, also known as subroutines. The comments at the beginning of each set of paragraphs in the PERFORM would be the statement of what it was supposed to do. While writing this non-code, we discovered errors in thinking and design.

We could do this as a group, because there were also CALLed programs, with parameters. The design team could say up front what should be in the program, and define its inputs and outputs. Common data definitions were put into the same sort of INCLUDE libraries used today.

There would have been no point in writing all this in the target language, COBOL (and sometimes assembly language). It isn't self-documenting, despite claims. Using and maintaining the comments, taken from pseudocode, was a best practice that lived on in some form through C and possibly Java. Anything larger than a single algorithm (e.g., an operating system, a compiler), requiring teamwork over a period of time, needs this thoughtful design phase. Even if, like Linus Torvalds, you ended up writing it all yourself.

3
0
Silver badge

Re: "Ever heard of pseudocode?"

I think that many programmers will agree that they actually "think" in pseudocode all the time. Sometime we write it down, sometimes we don't.

Pseudocode is a simplified process that helps us validate our thoughts more than anything else.

Maybe it should have been called PseudoThought.

3
0
Gold badge

Re: "Ever heard of pseudocode?"

"consider the problem at hand, rather than getting caught up in syntax of your chosen language"

If the syntax of your chosen language prevents you from presenting the algorithm in a readable fashion, you need a new language.

This does happen. For example, if you are maintaining some legacy crapware written in INTERCAL then you might very well put together some pseudocode in a different language. If that different language happens to be a properly specified one for which a compiler exists then you can write and execute tests against your design. You might like that.

Generally, though, whilst all languages have peculiarities of syntax, decent ones do not impede understanding to the extent that someone who is paid to program in that language would not be able to follow the algorithm.

There's a place for a pseudocode that is just a string of hand-waving comments about the general flow of the algorithm. That place is the written documentation that accompanies the source code. As soon as you get down to specifying details, you might as well write something that the compiler can parse. As a bonus, if you write your "pseudocode" in the target language, you might even end up with meaningful variable names, short helper functions, and a general bias towards representing application domain concepts with linguistic constructs.

3
2

Read some history

In Turing's time, even a general purpose tool (not even computer) that can do almost everything was a issue since it didn't exist in human history therefore it was hard to imagine.

1
0

@LinkOfHyrule

He totally pwnd those Nazis lol.

1
0
Anonymous Coward

Re: @LinkOfHyrule

Beer is pseudocode.

0
0

@UncleSiggy

Impossible. One is readable, and the other doesn't generally exist until after the project is done. And then only as "not this".

1
0
Silver badge

tru nuff

madd skilzz indeed

0
1

Re: "Ever heard of pseudocode?"

""Specifying an algorithm to a useful degree without handwaving is practically the same amount of work required to actually code up that same algorithm in an appropriate language, modulo a few bits of punctuation or whitespace""

You have it the wrong way around, as do many moronic PHBs. Proper planning makes coding trivial. It's trivial turning proper pseudo-code into real working code because the hard part - working out what to do when and how - has already been done. So yes, if you've described your algorithm properly a monkey could code it, but that's the whole point of producing the description in the first place.

5
1
Silver badge
Linux

Wow, that got a response...

I was rather flippantly pointing out that any "students" studying in fields that require programming or engineering would likely have been taught about designing their code, using techniques including flow diagrams and pseudocode.

Alan Turing, however, shows remarkable discipline and a highly pragmatic approach. This story should be an example to students of how software should be produced instead of the quite common approach of mashing bits of code together and creating software without a clear focussed design (I'm quite guilty of this myself at times)

1
0

Re: "Ever heard of pseudocode?"

For some reason this springs to mind.

Step A: Steal underpants

Step B: ? ? ?

Step C: PROFIT!

Gotta love those gnomes.

0
0

Re: "Ever heard of pseudocode?"

Psuedocode is for the benefit of psuedo-programmers, "managers" as they're otherwise known. Any attendant benefit to the person actually bashing the bits is pure coincidence. However, this generalised hand-wavey overview is useful for letting the poor over worked, under fed, under housed and generally poverty stricken executive board who signed off release of capital for development know that they're more-or-less getting what they've forked out for without them needing to understand the finer elements of actual code.

0
3
Bronze badge
Devil

Re: "Ever heard of pseudocode?"

Have you thought of writing the code yourself, and pocketing the cheque for the offshore team?

Icon: you know you want to... go on, no-one will notice.

0
0

Re: "Ever heard of pseudocode?"

@Ru...give it a rest and concede that you're wrong...you might even feel liberated ;)

2
0

This post has been deleted by its author

Pint

Re: "Ever heard of pseudocode?"

Ok, so by way of example Mr Ru.

I frequently do the following

- Draw a few boxes with another coder or two to decide basic system components.

- Take a component and decide its responsibilities. These are put in some doc (even if its just a comment at the top, or a note next to its box).

- Figure out the code paths by writing very high level, 'do this', 'now do this', 'followed by this'. never goes beyond half a dozen.

- Then, in turn, expand each item into tests and code.

- Go to the pub having finished.

The first two items give us a simple spec we can check we aren't going renegade against, the third is a design/ development device that is high level pseudo code.

If you are talking about writing the gif compression algorithm in pseudo code, then sure, you might have a point (although I would probably still disagree). If you have large problems, they need to be designed properly or you'l screw it up. If you try to do all the design in your head, you're doing it wrong.

On the vagaries of languages getting in the way, I'd say it depends on your development process and the time allowed to create the correct level of abstraction. I would certainly not like to try to do my system design in code first time. Paper is cheap, writing working code is not.

0
0
Childcatcher

What came first the computer or the coder?

Well now you have your answer.

0
0

Re: What came first the computer or the coder?

Ada Lovelace settled that argument a long time ago.

2
0
Anonymous Coward

Re: What came first the computer or the coder?

The original computers were people. Mechanical computation is a littlemore modern ;-)

2
0

The coder, by miles

...and Turing wasn't the first to write an algorithm when he had no place to run it.

According to what I've read, Ada Lovelace did exactly the same, only she did it 106 years earlier than Turing wrote his chess program.

3
0
Gold badge

Re: mechanical computation

And electronic computation more modern still.

"Surely You're Joking Mr Feynman?" describes in some detail how the young Feynman managed the computer department at Los Alamos. He appears to have invented pipelining, out-of-order processing and error correction using a team of young ladies armed with mechanical calculators as his massively parallel CPU.

You'll also find that classic techniques like Simpson's Rule and Gaussian Elimination were originally implemented directly on wetware. And lastly, Babbage's original motivation for trying to build a mechanical computer was to do *exactly* what people were doing already, but without the mistakes. The idea that a mechanical computer might be able to do *new* things, came later.

3
0
Bronze badge
Go

Re: The coder, by miles

> According to what I've read, Ada Lovelace did exactly the same, only she did it 106 years earlier than Turing wrote his chess program.

Well, here's the daddy <http://en.wikipedia.org/wiki/Al-Khw%C4%81rizm%C4%AB>. At the very least he gave his name to it. Lived ~800 AD.

Icon is no-op.

0
0

Page:

This topic is closed for new posts.