-1

What is generally accepted as being the first machine implementation of a search tree (as they are more commonly known and used in modern computing for things like solving or powering, mazes, checkers, chess, tic-tac-toe, etc.)?

  • Early maze solving robots/machines, some of them may have been based on right or left hand rule, and depth search.

  • The first machines that played board games, since obviously each square of the board would have been a permanent part of the machine. (a permanent search tree).

  • Obviously, very few of the first maze solvers would have stored the maze, or what they had so far mapped of the maze, however, I suspect that the robot arm built by 'Thomas Ross' in 1933, at the 'University of Washington' would have, it used a type of electromechanical memory .

  • Here's a link to what seem to be the first maze solvers, 'Thomas Ross', at the 'University of Washington', built some (how many?) at that time.

  • I re worded this question, by using the suggestion in the comment below, so I just copied the text in that comment "the first machine implementation of a search tree", to be the question.

  • Note - I have not actually made it a requisite that the tree or part of it be stored, I just left that undecided to allow 'interesting' other designs to be posted. My unavoidable error is in mentioning storage of the search-tree or how much of it had been generated so far. To make this question truly correct, maybe I should make it a requisite that the search-tree or how much of it had been generated so far, be stored. I think it's wiser to leave it as it is, unless it makes this question too badly asked.

Improve this question
17
  • 2
    Do you have an example of one of these 1930s systems?
    – Alex Hajnal
    Dec 21, 2021 at 22:31
  • 3
    A 'search tree' is an abstract concept, and thus any algorithm was likely invented/discovered before anyone built a robot capable of implementing the algorithm. But maybe I'm just unclear on what you mean by an 'occurrence' of a search tree.
    – another-dave
    Dec 21, 2021 at 23:08
  • 1
    Sounds like you're asking for the first machine implementation of a search tree, as distinct from the abstract algorithm.
    – another-dave
    Dec 21, 2021 at 23:18
  • 1
    For simply-connected mazes (those with only branches/exit not on an isolated island) one can simply use wall-following. Just pick a wall (e.g. the left-hand one) and keep following it and it will lead to the exit. IIRC that's how Thomas Ross's robots worked. His robots used analog circuits (capacitors, mechanical switches, etc.) for decision-making. The idea was to try to emulate how a real animal's brain works, albeit in a very rudimentary form.
    – Alex Hajnal
    Dec 21, 2021 at 23:32
  • 1
    Re noughts and crosses: when I was young (I'd guess 10 or 11), a friend's father had built a noughts and crosses machine out of, as far as I know, switches, lights, and relays. No "electronics" in there.
    – another-dave
    Dec 22, 2021 at 3:03

3 Answers 3

Reset to default
5

Those "what was the first" questions are always difficult, because they assume that somehow the concept sprang suddenly into existence. That's almost never the case, usually the concept is developed gradually, until you reach an abstraction like "search tree" that is then taught in CS.

for things like solving or powering, mazes

Mazes were solved much earlier without search trees, by using a variant of the "left-hand wall" algorithm, and implement in robots like the "turtle" by Thomas Ross mentioned in the comments (I build one of those when I was a kid, with help from my father).

checkers, chess, tic-tac-toe

There were implementations that did this without search trees, e.g. 80s chess/tic-tac-toe game machines, and probably earlier ones as well. "The first machines that played board games", whatever it was, also most certainly did not use a search tree.

For an actual implementation of search trees, you need either backtracking, so a sufficiently "fast" computer, or enough memory. That narrows down the possible window for early implementations.

And while I cannot tell you "the first", a pretty famous implementation of AI using backtracking was SHRDLU (1968-70), a natural language parser for a "toy block" world with a planner to execute actions in this world. The Planner used backtracking.

So that was already a pretty elaborate implementation.

The A* algorithm which is one of the first practical ones to actually use backtracking/search trees to solve game playing was published in 1968, which gives another hint of the timeline.

Finally, Lisp was sort of a natural language to express these kinds of algorithms. It was specified in 1958, so that gives another indication of the timeline.

So I'd assume there were programs playing around with some kind of backtracking/search-tree approach in the 60s, though I couldn't name a concrete example, with actually useful ones in the late 60s.

Again, let me emphasize that these implementations would have little similarity with how search-trees are used today to play games - the machines were just too slow, and there was too little memory, to do this on the same scale as it is done today.

Improve this answer
12
  • 1
    The left hand wall algorithm is itself an example of a backtracking depth first search.
    – JeremyP
    Dec 22, 2021 at 9:03
  • 1
    @JeremyP I disagree, the left-hand rule doesn't need a stack for internal state, which is what you need for backtracking/dfs.
    – dirkt
    Dec 22, 2021 at 11:07
  • I don't see that the Ross 'robot arm' required a search tree. The maze was simple, and only one level of backtracking was needed. At any junction, if you take the path that encounters a dead end, then back up to the junction and take the other path. There was a 'memory' aspect which recorded the route as a series of left/right decisions, such that on restarting the maze, no mistakes would be made.
    – another-dave
    Dec 22, 2021 at 21:42
  • The Samuel's checker playing program - debuted in 1959 - used alpha-beta pruning and was in development since 1949 and apparently Samuel was instrumental in developing the IBM 701 instruction set to facilitate his checkers program - see Arthur Samuel – Biography, History and Inventions
    – davidbak
    Dec 23, 2021 at 0:29
  • @dirkt If you view the maze as a tree, which it is topologically, the left wall rule is clearly a depth first search with backtracking. You don't need a stack as such, you just need to know how to get back from each node to its parent.
    – JeremyP
    Dec 23, 2021 at 9:03
3

Samuel's checker playing program - debuted in 1959 - used alpha-beta pruning and was in development since 1949 and apparently Samuel was instrumental in developing the IBM 701 instruction set to facilitate his checkers program - see "Arthur Samuel – Biography, History and Inventions".

Improve this answer
4
  • It'd be interesting to know more about what influence this had on the instruction set. The article, alas, is silent on that.
    – another-dave
    Dec 23, 2021 at 15:08
  • Me too. ........
    – davidbak
    Dec 23, 2021 at 18:22
  • "Because his checker work was one of the earliest examples of non-numerical computation, Samuel greatly influenced the instruction set of early IBM computers. The logical instructions of these computers were put in at his instigation and were quickly adopted by all computer designers, because they are useful for most non-numerical computation" -- Stanford memorial resolution for Samuel, in the wayback machine,
    – another-dave
    Dec 23, 2021 at 18:45
  • @another-dave - huh, very interesting - and here I thought the logical operations were put in because, you know, binary logic: why not? But it definitely is the case that early computers were primarily for numerical calculation (ballistic tables and so forth - even early accounting applications probably had no more need of special boolean instructions - you could do everything you needed with conditional jumps). (Or so I see it now.) Thanks! (Oh, and also early computers were not necessarily binary based so it wasn't obvious to them I guess!)
    – davidbak
    Dec 23, 2021 at 18:49
1

I'll go with noughts and crosses.

Some sort of 'first' seems to have been awarded to Donald Davies (who later went on to invent packet switching). He reportedly had a relay-based noughts and crosses game in 1949; this article reproduces a paper with a picture of a decision tree.

It appears it set of some sort of craze for such things in the electronics literature and popular press.

Since I'd mentioned seeing a simple noughts-and-crosses machine in my childhood:

I now think it was the machine described in the September 1965 edition of Practical Electronics, pages 806 to 812. The logic is implemented purely on switches.

I have yet to read and understand the logic. At first glance, there's some curious stuff about how if the machine fails to announce a move, you need to rotate a switch to unstick it.

Improve this answer
3
  • 2
    A decision tree isn't a search tree. There's no search being made: the tree is precalculated. (I actually implemented tic-tac-toe this way in FORTRAN II, my first program ever, when I was in junior high. I had the entire decision tree drawn on multiple sheets of paper and I just coded it straight. I've been embarrassed about it for many many years now.)
    – davidbak
    Dec 23, 2021 at 4:09
  • @davidbak - are you saying that Davies' machine used a precomputed decision tree? It wasn't clear to me from the reproduced book page whether that was talking about something wired into the machine. I agree that the PE machine did - maybe I should not have muddied the waters there.
    – another-dave
    Dec 23, 2021 at 16:38
  • 1
    I do not know. But later in the article he is quoted as saying "There seems to be no possibility, with electronic machines as at present contemplated, of analysing any game of reasonable size completely." Note: he speaks of "completely". Tic-tac-toe can be analyzed completely in a few pages (as I said, I did it!) He talks of the mini-max algorithm - but that can be done by hand for a game like tic-tac-toe (I refuse to call it "noughts and crosses"). I think the idea of a runtime search of a large tree came later with programmable computers, not relay systems. (As for Checkers.)
    – davidbak
    Dec 23, 2021 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.