oktober 17, 2004

Automatisk "lösning" av Minesweeper i Mozart/Oz

Raphaël Collet har byggt ett program som automatiskt löser spelet Minesweeper, och har också skrivit papret Playing the Minesweeper with Constraints (PDF) om detta. Programmet ser nästan ut som originalet och finns att ladda ner på The Oz Minesweeper page.

För att köra programmet krävs:
* The Mozart Programming System
* Någon form av Emacs (Xemacs eller GNU Emacs). Windows-versionen går det att ladda ner via denna sida
* Glöm inte bort att sätta miljövariabeln OZEMACS till Emacs-exekutabeln (annars funkar det inte)
* Läs på Enabling Oz Applets hur man kör Oz-program via webben.


Se vidare
Mozart Documentation
Speciellt skoj är Finite Domain Constraint Programming in Oz. A Tutorial

The Authoritative Minesweeper
Solving Minesweeper
Richard Kaye's Minesweeper Pages. Kaye bevisade för några år sedan att Minesweeper är ett NP-komplett problem: "Minesweeper is NP-complete", Mathematical Intelligencer volume 22 number 4, 2000, pages 9-15 (har varken hittat eller läst detta).
Ian Stewart on Minesweeper
Chris Studholme: Minesweeper as a Constraint Satisfaction Problem
Tetris is Hard, Even to Approximate


On-Line Guide to Constraint Programming av Roman Barták
Second International Mozart/Oz Conference


När det gäller Constraint Logic Programming tycker jag i och för sig att både ECLiPSE (fritt men kräver registrering) och Sicstus Prolog är lättare att arbeta med. Och boken Programming with Constraints av Kim Marriott och Peter J. Stuckey är en höjdare.


Rätt lite av ovanstående kom direkt via Lambda The Ultimate, men det började där.

Posted by hakank at 07:51 EM Posted to Artificiell intelligens

februari 10, 2004

Stephen Thaler's Creativity Machine

I The machine that invents berättas om Stephen Thaler och dennes "Creativity Machine".

Technically, Stephen Thaler has written more music than any composer in the world. He also invented the Oral-B CrossAction toothbrush and devices that search the Internet for messages from terrorists. He has discovered substances harder than diamonds, coined 1.5 million new English words, and trained robotic cockroaches. Technically.
...
"[Thaler's] first patent was for a Device for the Autonomous Generation of Useful Information," the official name of the Creativity Machine, Miller said. "His second patent was for the Self-Training Neural Network Object. Patent Number Two was invented by Patent Number One. Think about that. Patent Number Two was invented by Patent Number One!"
...
Thaler's technology was born from near-death experiences of dying computer programs. Its foundation is the discovery that great ideas are the result of noisy neurons and faulty memories.


Se även
Imagination Engines, Inc....
Steven Thaler
Walter J. Freeman Neurophysiology Lab


Uppdatering
Se även New Scientist-artikeln The creativity machine från januari 1996. (Via Heckler & Coch.)

Posted by hakank at 12:08 EM Posted to Artificiell intelligens | Comments (1)

januari 05, 2004

Korsord och AI

I artikeln Puzzles provide brain insight skrivs om forskning kring korsordslösande. CogNews-artikeln Crosswords Test AI frågar kort om detta är nästa stora utmaning för AI.

As early as 1991, research showed that letters and meanings combined provide a better set of cues for memory retrieval than either one alone. This matches our own impression that we rely on the syllable fragments in a partially-complete crossword as much as we rely on the list of definitions. Functional MRI scans show that multiple brain areas are involved in responding to these cues.

Artificial intelligence tries to duplicate or exceed human brain processing by means of a computer.

Solving crosswords has been a test of artificial-intelligence programs since 1977. Recently, researchers wrote a program to solve a crossword based on its clues as well as its diagram structure.

Researchers at Duke created a program called "Proverb" for "probabilistic cruciverbalist." A cruciverbalist is a crossword-puzzle solver, and probabilistic refers to using a computer to calculate how probable or likely a given answer is among many choices.

Några länkar:
Michael L. Littman
Constraint Satisfaction, Probability, and Solving Crossword Puzzles (om Proverb)
Solving Crossword Puzzles as Probabilistic Constraint Satisfaction
Några fler av Littmans papers finns här.

Se även:
Crossword Puzzle Software, Tools, Articles, etc
OK då: Här är mitt eget enkla verktyg för kortsordslösande Cross words som inte använder AI överhuvudtaget, men däremot finns både för svenska och engelska.

Posted by hakank at 10:27 FM Posted to Artificiell intelligens

december 10, 2003

Computational origami

Från BBC-News-artikeln Origami help for tech design:

Origami - the Japanese art of folding paper to make models - is being put to a new use - to help engineers design, amongst other things, new telescopes and cars.

Exploiting the study of the way that paper folds, known as computational origami, can reveal both better ways to construct objects and also predict how they will respond to certain pressures.

Se även
Erik Demaine
Nature-artikeln Origami solves road map riddle (februari 2002)
Origami Mathematics Page

Posted by hakank at 04:45 EM Posted to Artificiell intelligens

november 17, 2003

CogNews

[Tillbaka till ordningen nu efter allt testande.]

Jag upptäckte att jag inte nämnt en av mina stora favoritbloggar om AI, kognitionsforskning, psykologi och framförallt det tvärdisciplinära land som ligger däremellan: CogNews, som beskrivs sålunda:

CogNews is a Slashdot style news site for the cognitive sciences -- neurology, psychology, artificial intelligence, philosophy, linguistics, biology, sociology, anthropolgy and more. Basically anything that has to do with thinking, intelligence or how the mind works.

Jämfört med Slashdot har CogNews har betydligt färre kommentarer och som är av mycket högre kvalitet.

Posted by hakank at 09:18 EM Posted to Artificiell intelligens

november 15, 2003

Kommentarer om Semantic Web-kritik

Att läsa en regnig höstkväll: svar på den Semantic Web-kritiska artikeln The Semantic Web, Syllogism, and Worldview.

Clay takes on the Semantic Web pekar vidare på
shirky touches off a storm of semantic web posts och
Technorati backlinks samt rekommenderar speciellt A Response to Clay Shirky's “The Semantic Web, Syllogism, and Worldview”.

Posted by hakank at 09:12 FM Posted to Artificiell intelligens

oktober 20, 2003

Recension: Michael Crichton 'Prey'

För ett antal veckor sedan läste jag klart Michael Crichtons Prey. Av lite olika anledningar har det tagit ett tag innan denna recension skrivits.

Min tidigare erfarenhet av Crichton är blandad. Jag blev besviken på Jurassic Park eftersom det mest var jakt och suspense, vilket jag inte tycker är så skoj. Det lilla som handlar om kaosteorin var heller inte så upplyftande. I och för sig är boken rätt välskriven för genren (om man nu tycker om sådant). Andra böcker som jag läste för en massa år sedan, såsom Andromeda Strain och The Terminal Man ingav mig ungefär samma känsla

Så det var med rätt låga förväntningar jag började läsa Prey. Fast kanske ändå inte, eftersom anledningen till att jag började med boken var att boken har fyra sidor litteraturreferenser i ämnena nanoteknologi och agent-baserad modellering/swarm intelligens, varav det sistnämnda är mycket spännande. (Se nedan för lite blogganteckningar om detta.)

Min fråga när jag började läsa var då: Vad kan han skriva om svärmintelligens, månne? Eftersom Crichton är en teknikkritisk nisse (vilket jag uppskattar mycket) antog jag att det skulle bli elände och biljakter, hur han nu skulle få ihop detta.

Tack och lov visade det sig Prey vara en riktigt sidvändare! Vad var det då i boken som gjorde detta möjligt?

Främst var det två skäl. Först: Till skillnad från t.ex. Jurassic Park är den mycket mer personligt skriven. Den är skriven i jag-form och Crichton ger mer karaktärsdrag hos huvudpersonerna; kanske inte så mycket, men tillräckligt för att det ska bli intressant.

Det andra skälet är att han skriver mycket om agentbaserad modellering/svärmintelligens. Boken skulle faktiskt kunna vara en introduktion till detta ämne; man kan se den som en väldigt lång populärvetenskaplig tidningsartikel om agentbaserad modellering (och nanoteknologi), interfolierad med lite action.

De förklaringar Crichton skriver om de ämnen jag känner till, är ungefär lika bra som andra populariseringar jag läst. Visst förenklar och överdriver han en del, men det är inget som jag stördes av i alla fall. Man kan i och för sig fråga sig hur rimligt det är att en person som är mitt inne en kritisk situation börjar skriva ett par sidor om teoron eller tekniken bakom problemet. Det störde mig dock inte speciellt mycket.

Nå, hur var actionscenerna då? De var faktiskt inte alls så dumma, och föredömligt få. Naturligtvis är det den senare delen av boken som har dessa scener. Med Yuen Woo-Ping som actioninstruktör skulle det kunna bli en underbar film. (Yuen Woo-Ping är kampscensregissören till bland annat "Crouching Tiger, Hidden Dragon", "Matrix", "Tai Chi Master" etc. F.ö. är han kampsceninstruktör till cirka 7 av mina 10 favorit-kungfu-filmer, de tre nämnda inkluderade.) Det krävs möjligen lite kreativ rewriting, som att alla huvudpersoner är Kung-Fu-mästare, men det vore ett billigt pris att betala.


Ett slutomdöme
Boken finns numera på listan över böcker jag tänker läsa om nästa år, om inte
tidigare. För mig är det ett mycket högt betyg.


På denna reading list finns Prey med tillsammans med en massa av mina övriga favoritböcker i detta och näraliggande ämnen.

Förutom "Fragile Dominion" har jag samtliga böcker, fast Wolframs ANKOS har jag ännu inte börjat läsa ordentligt.

Information om workshopen som har denna trevliga litteraturlista finns på New Mexico Adventures in Modeling 2003-2004 Workshop. De använder ett av de system jag själv gärna använder, nämligen StarLogo.

Vidare läsning
Om ovanstående, inklusive böckerna i listan ovan, har jag skrivit ungefär här:


Uppdatering
Marcus på Commemoro skickade precis en TrackBack med sin recension av Prey.

Marcus borde fått en cred eftersom det var hans recension som gjorde att jag beslöt mig för att skriva min. Det får han därför nu: Cred till Marcus!

Posted by hakank at 12:44 EM Posted to Agentbaserad modellering | Artificiell intelligens | Böcker | Komplexitet/emergens | Comments (1)

september 02, 2003

New York Times om genetisk poesi

I From Genetic Poetry to the Web's Favorite Color skriver New York Times bl.a. om Darwinian Poetry, ett försök att skapa poesi via genetiska algoritmer. (Kalle skrev lite om detta projekt för ett tag sedan.)

I artikeln nämns en sajt som också verkar lite skoj: speech accent archive.

Posted by hakank at 09:05 FM Posted to Artificiell intelligens

Datorgenererad musik

I BBC-artikeln The Robot Composer, med underrubriken "Can computers write music?", berättas lite om datorgenererad musik. Notera att en del av länkarna i artikeln är fellänkade, däremot verkar textversionen av länkarna vara korrekta.

Som gammal jazzbassist är jag speciellt förtjust i GenJam.

Lite fler länkar om datorgenererad musik finns i
Yahoo-kateogorin Entertainment > Music > Computer Generated > Computer Generated Composition.

Posted by hakank at 08:10 FM Posted to Artificiell intelligens

augusti 19, 2003

Dagdrömmeri

The Hungry Spirit: Getting Our Gaze Back Is daydreaming a dose of self-medication in a data-processed world? berättar om en forskare i dagdrömmar.

Daydreaming," says artificial intelligence researcher Erik Mueller, "is spontaneously recalling or imagining personal or vicarious experiences in the past or future." He argues that it improves efficiency, assists creativity, and regulates emotions. The odd thing is that Mueller is studying human daydreaming in order to teach computers how to do it. I find this interesting because computers were developed primarily to process information. What flows through my e-mail and the Internet is an explosion of semi-random details from wider and wider sources. The human brain, however, is not made to process data. It works by matching patterns. Our minds create order out of chaos by learning patterns and then using those patterns in unique ways. It's our secret of survival.

Erik T. Mueller skrev på 80-talet ett AI-program Daydreamer för att undersöka vardagliga tankeströmmar. Jag har inte testat detta program.

Mueller är f.ö. skapare av ThoughtTreasure ("a commonsense knowledge base and architecture for natural language processing that uses multiple representations including logic, finite automata, grids, and scripts") samt andra program.

Posted by hakank at 10:11 FM Posted to Artificiell intelligens

augusti 18, 2003

Crime mapping

Computer model forecasts crime sprees

Computer forecasts that predict where and when crimes will happen by analysing past patterns should help police channel resources where they are needed most. The technique, now under trial in the US, could be available for routine use within a year.
...
Wilpen Gorr, who is an expert on information systems and forecasting and heads the team, also looked for more subtle and unexpected trends. He compiled a list of leading indicators - minor offences such as vandalism and trespassing that crime analysts believe precede more serious crimes.

He then used a neural network to make connections that link changes in the pattern of these minor offences with changes in levels of more serious crimes. He found that if a minor crime such as vandalism increases during one month, it can indicate that there will be an increase in serious property crimes such as burglary in the following month.

Cloudy, With a Chance of Theft är en artikel om detta skriven av Wilpen Gorr.

Se Researchers Develop Crime Prevention Software för ett exempel på en brottskarta ("crime map").

Två PDF-filer:
Crime Hot Spot Forecasting: Modeling and Comparative Evaluation av Wilpen Gorr och Andreas Olligschlaeger .

Mapping Crime: Principle and Practice: Principle and Practices av Keith Harries: This guide introduces the science of crime mapping to police officers, crime analysts, and other people interested in visualizing crime data through the medium of maps.

Posted by hakank at 08:01 FM Posted to Artificiell intelligens

augusti 17, 2003

AgentWeb

AgentWeb är en portal för forskning kring och nyheter om olika typer av agenter eller som de själv skriver: Information, resources newsletters and mailing lists relating to intelligent information agents, intentional agents, software agents, softbots, knowbots, infobots, etc.. Även Semantic Web behandlas. Se fler ämnen under Topics.

Det finns även en mailinglista AgentNews, prenumerationsinstruktioner finns i slutet på sidan.

Posted by hakank at 09:31 FM Posted to Artificiell intelligens

augusti 16, 2003

Ny bok om genetisk programmering

Genetic Programming IV: Routine Human-Competitive Machine Intelligence av Koza et.al. är en ny bok om genetisk programmering. Första kapitlet finns att ladda ner här (PDF). Dyr som pocker är den dock.

Länk till Amazon.

Posted by hakank at 09:18 EM Posted to Artificiell intelligens

augusti 14, 2003

Lär datorn sunt förnuft

Projektet Open mind - indoor common sense försöker skapa ett vardagsintelligent system.

The Open Mind Indoor Common Sense project is an attempt to make indoor mobile robots smarter by making it easy and fun for people all over the world to work together to collect the millions of pieces of ordinary knowledge that constitute "common-sense". This repository of knowledge will enable us to create more intelligent mobile robots for use in home and office enviornments.

Från What is Open Mind Commonsense?:
The goal of the Open Mind Indoor Common Sense project is to make indoor mobile robots that work in environments like homes and offices more intelligent. We want such robots to have commonsense as well as recognize objects and indoor scenes.

What commonsense knowledge would we expect such a helper robot to possess? Examples of indoor commonsense includes knowledge like coffee is made in a coffee maker which is in a kitchen; to find out if it is raining one needs to look out of an open window; master bedroom usually has a attached bath; and so on. We will be collecting indoor commonsense knowledge in the form of template and freeform sentences.

Poängen är alltså att man som användare ska befolka databasen med vardagsfakta, t.ex. vilka saker som finns nära varandra (stol och bord), idenfiera objektet på bilder (t.ex. en hund), eller relationer mellan saker och händelser. Ofta är det fråga om att fylla i ett saknat ord (på engelska) i en mening. Några exempel:

Det finns fler dokument att läsa när man väl registrerat sig, liksom länkar till relaterade projekt (såsom Cyc och ThoughtTreasure).

En trevlig sak är att man kan ladda ner databasen. Tyvärr endast i MySQL-format. I skrivande stund finns det 10284 fakta ("sunda förnufter"?) inlagda av 103 användare. De lockar med utdelning av T-shirts till storkontributörer.

Det ska bli intressant att se vad som kommer ut av detta.

Posted by hakank at 09:04 FM Posted to Artificiell intelligens

juli 09, 2003

Etik-AI

Så har vi alltså fått det första fungerande AI-programmet som klarar följande: Imagine calling a customer service line and speaking to an operator who, after listening not just to your questions but your tone of voice and assessing your overall attitude, is able to determine where she should most appropriately direct your call. ... . Det hävdas i artikeln L.V. man patents 'ethical' artificial intelligence program:

LaMuth said his innovation represents the first language analyzer that incorporates ethical and motivational terms as part of a computer system.

"It enables a computer to reason and speak in an ethical fashion," LaMuth said. "Nobody has made an application like this."

A computer with LaMuth's artificial intelligence programming would be able to hold a conversation using human qualities, therefore allowing it to function in the capacity of a human being, such as an interviewer or receptionist, he said.

Å andra sidan: If a company were to use the artificial intelligence, its computer system could act as a receptionist and limit the number of menus an individual must go through to finally talk with an actual person when calling large corporations, LaMuth said..

Så om systemet endast begränsar olika möjligheter i en meny (trädstruktur) är det inte helt omöjligt att systemet klarar det bättre än slumpen. Men det är ingen "konversation" i min bok.

Jag har nu inte läst allting (inklusive patentet) i detalj men är ändå synnerligen skeptisk till att detta verkligen funkar som vi leds att tro. Att man får något patenterat bevisar ju inte något...

Lite mer info: Semantic web-listan (från 4 juli) där LaMuth själv skriver om sitt patenterade system. Och i sci.psychology.announce. Patentet finns här.

Det står mer på en av hans bok-sidor (sök efter "artificial" för att komma till avsnittet om AI) och på www.ethicalvalues.com.

Posted by hakank at 08:02 EM Posted to Artificiell intelligens