This project (a class project for CSc 215 at California State University, Sacramento) is an attempt to modify Beowulf (http://www.chessbrain.net/beowulf/ 2.4a by by Colin Frayn
(University of Birmingham, UK) and Dann Corbit (USA)) to use [Trappy Minimax]
Trappy minimax is a game-independent extension of the minimax adversarial search algorithm that attempts to take advantage of human frailty.
Whereas minimax assumes best play by the opponent, trappy minimax tries to predict when an opponent might make a mistake by comparing the various scores returned through iterative-deepening.
Sometimes it chooses a slightly inferior move, if there is an indication that the opponent may fall into a trap, and if the potential profit is high.
The algorithm was implemented in an Othello program named Desdemona, and tested against both computer and human opponents.
Desdemona achieved a higher rating against human opposition on Yahoo! Games when using the trappy algorithm than when it used standard minimax
This seems mos interesting for making more entertaining engines to play against.
Thanks!
E Diaz
Two first meanings of the dutch word "leren":
1. leren [vc] (learn, larn, acquire) acquire or gain knowledge or skills.
2. leren [v] (teach, learn, instruct) impart skills or knowledge to.
pocopito wrote:This seems mos interesting for making more entertaining engines to play against.
Thanks!
E Diaz
Thanks.
First reports indicate it may actually play stronger than old Beowulf. Maybe this new search algorythm has possibilities for engine-engine play as well against humans.
I find it interesting that the linked paper describing the algorithm discusses 20 head-to-head games of standard minimax versus trappy minimax and draws conclusions from that, and then discusses the results of 50 games by each version against a varied set of human opponents (ie, the two versions did not play the same people) which gives an Elo rating difference of about 20 (due to the speculative trappy algorithm winning one more game than the standard version).
In other words, statistics are terrible and you cannot draw a conclusion from the results as presented.
It'll be interesting to see whether it's true that the trappy Beofulf is stronger than the standard version, but it'll take more than 100 or so games to convince me (and not just self-play either)...
Evert wrote:I find it interesting that the linked paper describing the algorithm discusses 20 head-to-head games of standard minimax versus trappy minimax and draws conclusions from that, and then discusses the results of 50 games by each version against a varied set of human opponents (ie, the two versions did not play the same people) which gives an Elo rating difference of about 20 (due to the speculative trappy algorithm winning one more game than the standard version).
In other words, statistics are terrible and you cannot draw a conclusion from the results as presented.
It'll be interesting to see whether it's true that the trappy Beofulf is stronger than the standard version, but it'll take more than 100 or so games to convince me (and not just self-play either)...
What you do is set up the the 2 Beowulf versions- on the same system against the same opponent- with same controls- and let both matches play the same number of games at the same time. 500 games in each match would do it for me- because if I ran 1000 games- the same people who wanted 1000 would then want 2000. That never ends. Would 500 game matches be perfect? No, but let me know when it's a perfect world.
geots wrote:What you do is set up the the 2 Beowulf versions- on the same system against the same opponent- with same controls- and let both matches play the same number of games at the same time. 500 games in each match would do it for me- because if I ran 1000 games- the same people who wanted 1000 would then want 2000. That never ends. Would 500 game matches be perfect? No, but let me know when it's a perfect world.
Unless the strength difference is dramatic, a single match of 500 games is still not enough.
It's not true though that "it never ends", because rating programs (for instance BayesElo) don't just give you a rating, but also error bars and likelihood of superiority. With 500 games it's likely that the rating difference is smaller than the error in the ratings...
But of course we should distinguish two things here: if I want to know if program A is better than program B, I can run 10000 games to satisfy my own curiosity. For a ranking or rating list, or a tournament, the goal typically isn't to measure playing strength with 99% confidence...
Interesting, thanks. Of course engines have no problems against humans but this, combined with some algorithm to avoid closed positions, could really make things even harder and should be good for entertaining too.
I'm curious - has this Trappy Minimax (or similar algorithms) been applied to other games? The original paper applied it to Othello, but without more information about their Othello program, the results in the paper were not very informative, especially given how far above humans a descent Othello program is.
Thinking about it a bit more, I don't see how the algorithm would work with the more-or-less standard PVS alpha-beta search used by most chess programs.
As I understand it, the algorithm considers laying a trap by playing some move that is not the best move at depth N, but still looks like a good move, if that move scored as bad at (much) shallower depths n < N. For instance: it looks like your opponent can win a rook, until you actually calculate deep enough to see that after winning your rook, the opponent will lose his queen.
Whether that's really a good idea or not is another discussion, but as I see it the idea can only work if you know the score history of all moves. While the paper claims that this is known in an iterative deepening framework I don't think that's true with the search used in most chess programs. Typically, I will know which move is best (and have a score for that move), and I know that all other moves are worse than my best move (so I only have an upper bound to their score), which is not good enough. Even with fail-soft alpha-beta I don't think you can trust the scores enough. Am I missing something?
Obviously I haven't looked at the modified Beowulf source, which would probably tell me if the idea can be combined sensibly with PVS.
In general I like the idea, especially because it's a way of making a program different from the rest, and because it can make for a more interesting playing style. I'm not convinced (by the paper) that it actually works though...
The situation where your PV of iteration N runs into a disastrous fail low in iteration N+1 (say: lose a Queen) is not that uncommon. If you then don't find a viable alternative, it might be a good idea to stick to the best move of iteration N, in the hope your opponent won't search deep enough. Probably better than sac a Rook on ply 1 to avert the Queen loss (but ensure the eventual game loss.)
