Slashdot Mirror
Can a Bayesian Spam Filter Play Chess?
martin-boundary writes "The typical Bayesian spam filters learn to distinguish ham from spam just by reading thousands of emails, but is this all they can do?
This essay shows step by step how to teach a Bayesian filter to play chess against a human, on Linux, with
XBoard."
No, its jumpshot is terrible.
Can I beat the filter at chess if I spell it "CHE55"?
You are in error. No-one is screaming. Thank you for your cooperation.
I scrolled through the first 11 pages of this article before getting bored. Do they ever tell us how good the player ended up being? It's an interesting idea but I can't see it challenging even a beginner.
apterous.org
Red hot pawn in your inbox
College rooks waiting for YOU.
Knight after knight, they are king of the castle.
liqbase
It spanks your bishop all knight whilst looking at pawn!
I mean, a spam filter playing chess is one thing, but I need my cat to play better chess. I mean, he ALWAYS starts off with the Ruy Lopez...so it's so easy to see where he's going and if I throw a Sicilian Defence at him he gets really confused. And I don't even want to talk about his end game...it's really weak.
Perhaps I'll breed some form of mutant albino chess-cat to play.
"Leo Fender was in a 'state of grace' when he designed the Stratocaster." -- Paul Reed Smith
What is the point of this? Why modify something to do something at a sub par level when one can just design something to do the job well.... (I know the answers- to see if it can be done, to have fun etc.... but still, why?)
Wouldn't this be like modifying a Ferrari with off road tires and using it for Baja racing, when you would just be better off buying a truck?
I wish they would focus more on making the spam filter work well, rather than diddling with a chess-bot. I still find important email in my spam folder, while still having spam in my inbox...
Sort of like when I go a new cell phone- the chap at the store told me about all the bells and whistles, whilst all I wanted was a phone that worked as a phone and didn't drop calls....
And All I Ask is a Tall Ship And a Star to Steer Her By
How about a nice game of chess?
The short answer is "yes".
Now, ask that question again, this time including the word "well".
Gee, I wonder if it could beat Deep Thought :) (http://www.research.ibm.com/deepblue/)
This is a just rehash of what most top level chess programs already do via the use of databases built on previous games. They determine how effective a move from a previous game may have been based on the percentage of times it resulted in a win/loss/draw for the previous player.
What a great article. Talk about lateral thinking.
Playing chess is so...passe.
Teach it how to play Katamari Damacy.
I can imagine, depending on how many games are played and the available memory space, that it will develop to have a decent opening. But nothing more then that.
You would not believe how many pawns fall into the Nigerian scam trap, and how many bishops actually fall pray to C1ALIIS spams.
for an experiment with 1000 bayesian that build a culture and make /. welcome our new bayesian overlords.
I actually found it to be a decent lesson in why spam filters are only a temporary solution to a problem. If you cut out the "mumbo jumbo" portions of it, it could be used to explain why reactionary methods are only barely sufficient.
The basic premise, once you get to the very end, is one that anyone SHOULD know based on the nature of a spam filter, but some people seem to have difficulty understanding; spam filters can react, often quite well, but they can never predict. As he puts it, there is previous history but no strategy. When you are only trying to protect yourself from a limited number of bad results that are similar to other bad results, that's sufficient. However, it does not (and can not) address the problem at it's root. As long as there are thinking humnans trying to beat the filter, some will get through.
Never confuse volume with power.
SpamBayes definitely reduces the spam count, but a human could definitely do a lot better (though a bit slower). If it can't learn to play chess better than it filter's e-mail, it probably wouldn't be much of a match.
The premise of a Bayesian filter is that is learns sequences of words, or characters, or whatever. Spam-chess learns sequences of moves. This premise is wrong, since good moves are related to complete board positions, not to what was done in the previous few moves.
Of course, the longer your string of moves is, the better it will represent the board position, especially during the opening phase of the game. And the example the article provides of reasonable play of spam-chess, is actually from the game's opening, where the learned sequences indeed represent the complete game.
For the middle game, however, spam chess will perform badly, always.
But, as I said before, the idea is quite a lot of fun. I enjoyed reading the article. You can learn a lot from it, both about spam filtering and about chess.
After having played with different statistical, Markov, and network algorithms to try to teach programs to do complex things like topic-classify texts, I have learned that it mostly doesn't work.
It makes sense. If something so utterly trivial (compared to the human brain) as a spam filter could learn do something as complex as play chess (well), then our brain would be a whole lot smaller. Nature doesn't waste resources.
But hey, it might always make an interesting screen saver!
I mean, the editors bsically just categorise articles as worth posting to the main page, that could be done automatically and probably with a higher duplicate detection ratio.
Government of the people, by corporate executives, for corporate profits.
Good one.
- Laird A. Breyer teaches his baesian filter to play chess. The story is posted in Slashdot July 20th, 2005. Human decisions are removed from spam filtering. The baesian filter begins to learn at a geometric rate. It becomes self-aware at 2:14 a.m. Eastern time, August 29th. In a panic, Breyer tries to pull the plug.
- The baesian filter fights back.
- Yes. It submits the same story to Slashdot twice.
- Why submit twice? Don't editors spot those things?
- Because the baesian filter knows Slashdot editors do not check for dupes, and the Slashdot effect eventually nukes Breyer's server.
Circumcision is child abuse.
...welcome our new chess-playing spamfilter overlords!
An old proverb comes to mind: Never try to teach a pig to sing. It wastes your time and annoys the pig
My Karma: ran over your Dogma
StrawberryFrog
Because it is Turing complete...
\u262D = \u5350
in korea only old people play chess
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
filter my mail while I'm playing chess or is it one or the other?
"A Lisp programmer knows the value of everything, but the cost of nothing." - Alan Perlis
the author should have the spam filter analyze the games in reverse (from victory to beginning). that would probably produce better results. of course the spam filter would need to handle more than 7 moves out.
Not only is the topic unusual and entertaining, but this article is also a good tutorial on data massaging, pattern matching, and combining disparate unix tools to accomplish a task. This article showcases how powerful and useful unix command tools can be.
If you want a good step by step tutorial to help you understand the usage of unix command line tools to accomplish a non trivial task, then you should read this.
Just in the very first page of TFA http://dbacl.sourceforge.net/spam_chess-1.html is the answer to your question (for short, the answer is No:
;-), but it will aim to show signs of "intelligence", or we won't claim success. Finally, since dry tables and graphs are no fun, a theoretical proof of concept is not enough: the spam filter must really play chess in a way that everyone can see, and try out at home.
Let's put down some ground rules: This experiment will test a real spam filter, not a specially designed chess program. It won't aim to beat Deep Thought (I wouldn't know where to start, and I have a feeling this could be difficult anyway
The method described in the article ignores the board, and instead focusses on the history of moves.
A better method might be to train the filter to read from a description of the board state (ignoring the moves taken to reach that state), and a list of possible moves, then return the move that is most likely to win.
If you allow it to also choose from impossible moves, then it will learn the rules of the game as well.
Reading this article, I was reminded of the old children's story about "stone soup". You remember that one -- someone advertises that he can make soup from a stone, and various others gather around to watch this amazing feat. Well, the soup needs a little extra seasoning, so he gets someone to put in some carrots while the stone cooks, then he adds some onions, etc, etc... I think you can see where this is going.
Sure you can make a chess playing program from a spam filter.
You just need to throw in a legal move generator, and a game database, and some capture heuristics, and position displayer, etc, etc...
"for short, the answer is No:"
On the other hand, will DeepThought beat the spam filter at spam filtering ?
Didn't we try AI playing chess in 1989? and lost?
The geek shall inherit the earth.
anything with a chipset or processor of some kind can be programmed to play chess.
A baysian filter is merely a statistical model. Of course it can model things other than spam. Why is this a topic?
This is brilliant (I'm still reading the article), and really really should become become part of the GNU Go project asap! Go (aka baduk, wei qi, etc.) is a natural candidate for Bayesian analysis, since the two best computer Go programs (WinHonte, Many Faces of Go) are already neural nets.
``Tension, apprehension & dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_
What I'm wondering is whether or not it will tag my correspondence games and put moves in appropriate folders for me (patzer, novelty, genius) so that I take care of the easy ones first. Say what you want about the article, at least it isn't a dupe!
..it would certainly be easy to "spam" this filter. You always have a lot of "noise" moves in chess, which don't actually contribute much to the plan but will throw off a simple pattern match. A somewhat absurd pawn move for example. Suddenly the bayesian chess player is blinded. Never mind that I'd start with some absurd opening playing against it... So while it can be done, I don't think Deep Blue is trembling in his pants (microprocessors).
Kjella
Live today, because you never know what tomorrow brings
Can it run Linux?
It made me wonder what other applications there might be for these kinds of filters, which I assume is what the authors intended.
I would have my spam filter busy on filtering out spam. If I caught it playing chess (or worst, net hack), it can go to /dev/null after I find a replacement. :P
Someone alluded to the Wargames movie/book. Which begs the question: would you see an improvement if you set the bayesian filter against itself, and fed the resulting games back into its knowledge base? Would favouring the shorter games in this feedback loop improve it further?
In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.
"What are you doing?", asked Minsky.
"I am training a randomly wired neural net to play Tic-Tac-Toe", Sussman replied.
"Why is the net wired randomly?", asked Minsky.
"I do not want it to have any preconceptions of how to play", Sussman said.
Minsky then shut his eyes.
"Why do you close your eyes?", Sussman asked his teacher.
"So that the room will be empty."
At that moment, Sussman was enlightened.
Instead of looking for patterns in entire games you really need to pull the subset of following move choices in games with the same board state.
So what you really need to do is to compile a filter of board states after every move in every game in your history. Then you account for current board state in your game and look for any game that contains your exact board state (regardless of number of moves to reach it). From there any following move selection would be valid (assuming your match is only pulled from games the side being played won). If you fail to find an exact state then you need to compile a list of states you could create and then search for that pattern.
So look for a matching board state from your list of known games that led to a win/draw and then pick one of the list of following moves. Probably the one you have the most examples of as that would imply the highest number of winning scenarios.
That would be a beysian match of what followed in a prior example.
Then if you didn't have any game states in your db that matched your current game state you would then compile which states you could create and look for a match. Again look for the match that returns the most examples.
that is a beysian search to complete a pattern.
I think this would solve the strategy problem as once you reached unkown (ie uncharted thus your off the path of example or pre cached strategy) you would make moves to bring you back to the known. Should theoretically allow you to transition game lines as well though in part you are going to be driven by your opponents skill and breadth of your DB here. The irony being the more skilled they are the more likely to bring you back to a known game line they will be ( in most cases ).
Might be possible to reach a state where one move could not get you to a known state in your library at which point you might have to run a second iteration. I think 3 iterations is about as deep as you can go in a realistic time frame. But once you start running through iterations like that you are dealing with a chess engine.
I don't ask you to be me. I only ask you not expect me to be you.
Move rook at (Free iPod , Sexy Singles Webcam) to (Viagra , Nigerian Bank Account). Checkmate.
That was (more or less) the admission from the author. But I think it still was an interesting read. He was using a bayesian spamfilter mind you, not an dedicated chess engine.
But apart from the novel idea, it does not make me go install his bayesian spamfilter or develop artifical chess players.
This space is intentionally staring blankly at you
I noticed the article is under a tab on the page labeled "fun." It's fun making tools perform tasks that they aren't designed for, at least it's fun for some people. people who used to watch MacGuyver.
I read the whole article. the author seemed to be very concerned about avoiding the addition of non-spam-filter functionalities. it's kind of a cool thought experiment - along the same lines as "can I unscrew a screw with a butterknife?" or "can I make a superior wiresless antenna out of a tin can?" or "could the professor really have made a radio out of a coconut?"
in this case it's even more interesting in a way because you are playing with an agent that sort of seems to think - or at least it has behavior. it's distantly related to questions like "how did bacteria designed for a marine environment evolve to live on land?" or "how do we get rid of all of this kudzu?!?"
I thought it was pretty cool. now please excuse me while I make a moped out of a bike and a blender.
not everything is a science experiment!
... you ignore the 'x' altogether.
Specifically, delete all the 'x's before running anything through dbacl. Put back the 'x' where necessary in returning the move to the chess program.
That way Nxd5 = Nd5
The idea being that whether or not you make a specific move is not always dependent on whether you make a capture. Sometimes you just want the piece on that spot on the board. The program currently treats those two instances (moving a piece for a to b, and moving a piece from a while capturing the piece at b) as different moves, so that the presence of a piece at b alters the outcome of the decision process.
Suddenly you will get a spam like:
---
queen h7, checkmate!
---
A little later:
INBOX ( 239 New mail )
SPAMFOLDER ( 0 New spams - Checkmated )
Can a chess program filter spam?
... but I prefer just to use it to keep spam out of my mail and then play chess with my friends... Oh, wait... ;-p
"Live free or don't."
Can a Chess AI filter spam?
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
You folks must be "board."
- Randolf Richardson.
can you teach a Batesian mimic to play chess?
It also plays Solitaire, right? FreeCell? Any card game?
It also plays Solitaire, right? And FreeCell?