Channels ▼

Community Voices

Dr. Dobb's Bloggers

Thinking to the Side

February 20, 2008

Even back in 1994, Alex Lane was warning programmers not to rely solely on the language-du-jour to solve all their problems. As this nugget from AI Expert illustrates, an open mind has always been a useful tool.

 

Thinking to the Side

By Alex Lane

One of the most useful tools for solving artificial intelligence problems is a flexible mind

Just as fairy tales begin “Once upon a time...” AI problem solvers often solve in the same old way. One electronic correspondent of mine insists Prolog can solve all problems, but while Prolog is a marvelous language, his view that it is the solution to every problem reminds me of the saying, “All problems look like nails if you have a hammer.” One of the most valuable tools we have in this line of work is a flexible mind.

Consider the following game that requires a set of cards numbered one through nine. The object of the game is for two players to alternately take cards—which are spread out, face up, on the table between them—until one player holds cards whose sum is 15. The question to consider for this game is whether or not a forced-win strategy for either side exists. For example, does it matter who goes first?

It turns out that no strategy will assure either side of a win. Played properly, all games should end in a “draw” (neither side achieves the goal of cards summing to 15). This answer becomes evident if we represent the problem a certain way. Most folks would numerically order the cards in front of them in a single row: 1 2 3 4 5 6 7 8 9. As logical as this scheme may seem, this representation doesn’t really help us solve the problem. In fact, it may intimidate us, since we see we have nine choices to select from for the first pick, eight choices for the second, and so on, resulting in 9! (or 362,880) possible ways to pick up the cards. Solving this problem requires the ability to step back and pose the problem in some other way. Stop reading now if you want to tackle this yourself.
It turns out that if you arrange the cards in a 3x3 matrix:

 

you have a “magic square” arrangement where each row, column, and diagonal add up to the same number, which happens to be 15 in this example.

We can take advantage of this layout to rephrase the victory condition: The winner will be whoever can first take three cards corresponding to a row, column, or diagonal in the above setup. Have you ever played a game where players alternate trying to get three-in-a-row within a 3x3 matrix? Of course you have. The answer to our problem is obvious, as we all know that no forced-win strategy occurs in tic-tac-toe.


COPING WITH COMPLEXITY
Humans tame large numbers by ignoring them. Over 30 years ago, Donald Michie wrote a paper in which those 9! possible positions for tic-tac-toe were reduced via symmetry and the rules of the game to roughly 300 distinct positions.

Of course, another way of looking at the problem is that three possible “states” exist for any cell in a tic-tac-toe: empty, X-ed, or O-ed. Multiplying 39 gives us only 19,683 different positions before taking account of symmetry and game rules.

Yet a third approach, suggested by A.J. Roycroft of the Turing Institute in Glasgow, Scotland, results in many fewer positions. Roycroft, writing in a paper on chess endgames, noted that calculations do not impress human players. In fact, given the rules of tic-tac-toe, eliminating symmetries and realizing that draws can be forced, he proposed the following chain of reasoning.

Roycroft began by establishing that the first player cannot occupy all four corner cells without someone winning. Next, he noted that the first player can occupy just three of the corner cells without some one winning, but only in one way. Then he noted that there were two ways for the first player to occupy just two corner cells: in diagonally opposite and in adjacent corners. In the former case, the other pair of diagonally opposite cells must belong to the second player, meaning a win is inevitable (someone’s going to get the center). The latter case allows just two possible distinct configurations.

If you sum these up, you get, according to Roycroft, only three distinct positions. Roycroft concludes his analysis by asking which number corresponds most closely to the reader’s perception of “how many positions?” exist in a game of tic-tac-toe: 360,000, 20,000, or three. For most of us, that perception is closer to three than to the other two alternatives.

Roycroft thus presents a strong argument that game-playing ability in humans (which we assume correlates with intelligence) has more to do with forming, holding, and manipulating patterns than calculation.

The “collect-15” game played with nine cards was “converted” to tic-tac-toe by a process called lateral thinking, a term often associated with Edward De Bono, who has written several books on the subject. The term “lateral thinking” is difficult to define and impossible to specify; it’s easier to demonstrate, as we did with the card game, and as Roycroft demonstrates with his analysis. I’ll only say that it’s a way of looking at things that avoids the traditional “Only-one-way-to-do-it” logical approach to finding solutions. If you haven’t already done so, find and read a book on lateral thinking by Edward De Bono.


NEW DIRECTIONS
If you’re running a small development shop, or thinking of starting one, you already know you need heaps of accurate information and money. A CD-ROM called “Government Giveaways for Entrepreneurs” is designed to help you tap one of the largest sources of information (and biggest spenders) in the world—the U.S. Government.
The disk’s publisher, Infobusihess (Orem, Utah), notes that in 1992 the federal government spent an average of $40,000 for every business in the United States and nearly 60% of folks who apply to programs such as the “Small Business Loan Program” get the money for which they applied.


The software runs under Microsoft Windows and offers live-action video and audio clips of Matthew Lesko, who is billed as the “guru of government giveaways.” While these features may look good on the box, I tend to look at them as gimmicks. Virtually nothing I saw or heard couldn’t have been presented as text. What did impress me about the package was the search engine (allowing Boolean, proximity, and wildcard searches, among others) and the ability to personalize the software with highlighting, notes, and the placement of bookmarks. The copy I looked at came with a supplemental floppy disk containing new, last-minute information.


If you’re not in the market to be an entrepreneur, then you’ll be working for someone, either now or in the future. Infobusiness is set to release another CD-ROM aimed at folks looking for jobs. In the meantime, I’ve been looking at a new book, Ace the Technical Interview: How to get your next job in the computer industry, (McGraw Hill, New York, 1994), by Michael Rothstein.


Just over 30 pages of this 420-page tome are devoted to the kind of plain-vanilla issues involved in finding a job, such as resumes and personal appearance. The rest of the book consists of chapters devoted to various technical areas, such as MrS, Unix, OS/2, Oracle, CICS, SQL, client-server, networking, OOP, and AI. (Interestingly, no chapters cover Windows and DOS.)


The chapter on AI was written by Joseph S. Rubenreid of Inference Corp. (El Segundo, Calif.) and Jeffrey O. Milman of Applied Intelligence Systems (New York, N.Y.). They note that interviewers look for creativity, problem-solving ability, and flexibility (among other qualities). Most of the questions are oriented toward expert systems, although general concepts (such as heuristics) and languages (LISP, Prolog, and Smalltalk) are addressed as well. This book has value as a source for brushing up on basics or as a check of what your level of knowledge is on a specific subject or in general.

SOURCE: AI Expert, May 1994

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video