From mpf@medg.lcs.mit.edu Mon Jan 20 23:37:25 1992 X-VM-VHeader: ("From:" "Sender:" "Resent-From" "To:" "Apparently-To:" "Cc:" "Subject:" "Date:" "Resent-Date:") nil X-VM-Bookmark: 1 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["890" "Mon" "20" "January" "92" "23:35:05" "EST" "Michael Frank" "mpf@medg.lcs.mit.edu " nil "26" "abalone-interest mailing list draft" "^From:" nil nil "1"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA12872; Mon, 20 Jan 92 23:37:21 EST Received: by luke (4.1/TOC-1.1C) id AA02004; Mon, 20 Jan 92 23:35:05 EST Message-Id: <9201210435.AA02004@luke> From: mpf@medg.lcs.mit.edu (Michael Frank) Sender: mpf@medg.lcs.mit.edu To: abalone-mit Subject: abalone-interest mailing list draft Date: Mon, 20 Jan 92 23:35:05 EST Folks, I've created a new mailing list, abalone-mit@medg.lcs.mit.edu, for lab people interested in the game Abalone, and especially computer programs that play Abalone. I've drafted the following people onto it: mpf (Michael Frank) cwitty (Carl Witty) torrance (Mark Torrance) rjbodkin (Ron Bodkin) milos (Milos Hauskrecht) hofmeist (Scott Hofmeister) sajit@ai.mit.edu (Satyajit Rao) If you don't really want to be on this list, let me know and I'll take you off. I've also created abalone-usa@medg.lcs.mit.edu, which adds 70621.1732@compuserve.com (Michael Gilbert), who is working on a commercial Abalone program in New Jersey. We'll have a competition between our program and his, which I'll be setting up via email using this list. Those of you who haven't seen the computer Abalone player, come down to my office some afternoon or evening and I'll show it off. -Mike Frank From mpf@medg.lcs.mit.edu Wed Jan 22 00:09:43 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2550" "Wed" "22" "January" "92" "00:07:19" "EST" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "58" "Re: Computer Abalone duel" "^From:" nil nil "1"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA14931; Wed, 22 Jan 92 00:09:31 EST Received: by luke (4.1/TOC-1.1C) id AA03697; Wed, 22 Jan 92 00:07:19 EST Message-Id: <9201220507.AA03697@luke> References: <920122034803_70621.1732_EHE49-1@CompuServe.COM> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: Michael Gilbert <70621.1732@compuserve.com> Cc: abalone-mit Subject: Re: Computer Abalone duel Date: Wed, 22 Jan 92 00:07:19 EST Michael Gilbert writes: > Hello Mike: > Lets plan for a duel by phone. We have not yet incorporated the tourn. > rules. But we can if you so desire. As it stands now the computer makes > it moves within 5 to 15 seconds on the average. This is on the 486 > machines only. However the ST version has been very well with a average > time of 30 to 45 sec per move. The ST version supports both color and > monichrome displays. So let me know what your preference is and we will > send BETA copy. Whenever your ready to duel let me know. > Looking forward to hearing from you . LATER > Michael, Let's not worry about the time limits. I'll prepare a version of our program that moves within time that's comparable to yours, and we'll leave it at that. Right now we're in the middle of cleaning up and reorganizing our code; we'll be ready in another couple of days. I'll telephone you when we're ready. In the meantime, let's think about how we're going to verbally communicate the moves over the phone. We need to be careful so that we don't misunderstand the moves. For instance, our board coordinate system maps the hexagonal board onto a rectangular x-y plane like this: 10 - - - - - - - - - - - Where 9 - - - - - @ @ @ @ @ - '@' is a white marble 8 - - - - @ @ @ @ @ @ - 'O' is a black marble, 7 - - - . . @ @ @ . . - '.' is an empty location, and 6 - - . . . . . . . . - '-' is off the board. 5 - . . . . . . . . . - 4 - . . . . . . . . - - NW NE The movement directions 3 - . . O O O . . - - - + + are named after compass 2 - O O O O O O - - - - W+ O +E directions like this. 1 - O O O O O - - - - - + + 0 - - - - - - - - - - - SW SE 0 1 2 3 4 5 6 7 8 9 10 So, for instance, we might communicate a move by saying, "3 marbles northeast from (1,1)" to indicate the marbles at (1,1), (2,2), and (3,3) all moving up and to the right. Or, "3 marbles east from (3,3) moving northeast" to indicate a broadside move, and so on. However, I realize that this coordinate system isn't standard, so if you'd rather use a different system, we could hack our coordinate-input routines to accomodate that. In the meantime, why don't you send us your Atari ST beta release. Here's the address of my colleague with the Atari: Mark Torrance 348 Franklin St. #3B Cambridge, MA 02139 I'm looking forward to our duel. Finally we'll get a feel for how well our program does against an opponent other than itself and its creators! Thanks, Mike From mpf@medg.lcs.mit.edu Sat May 16 10:47:06 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1129" "Sat" "16" "May" "92" "10:49:32" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "25" "Computer Abalone" "^From:" nil nil "5"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA26797; Sat, 16 May 92 10:45:24 EDT Received: by luke (4.1/TOC-1.1C) id AA14505; Sat, 16 May 92 10:49:32 EDT Message-Id: <9205161449.AA14505@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: piaw@peoplesparc.berkeley.edu Cc: abalone Subject: Computer Abalone Date: Sat, 16 May 92 10:49:32 EDT Piaw> I've been playing abalone lately, and I was wondering if there's a Piaw> computer version of this game. Hi Piaw. Some of us at Tech Square wrote an Abalone-playing program last January, in C++ on the sparcs. It plays pretty well, but if you know how it works you can fool it. It actually has two different search algorithms, a plain alpha-beta, and a "conspiracy theory" player (which Carl wrote). You might have heard that Dave McAllester invented conspiracy theory as a more principled and more general alternative to singular extension sorts of things. You can play the two algorithms against each other or play against one of them (or have 2 people play). Unfortunately the algorithms both use the same stupid static-board evaluator, which could use some improvement. The user-interface sucks. The board uses "ASCII-graphics" and you have to type in 5 numbers describing your move. There's also an "official" commercial Abalone player coming out for PC-compatibles someday, which probably plays better than ours (certainly I would guess they have a better board evaluator). I don't think it's out yet. -Mike From mpf@medg.lcs.mit.edu Mon May 18 16:40:15 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["194" "Mon" "18" "May" "92" "16:43:11" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " "<9205182043.AA15183@luke>" "5" "Abalone redistributable?" "^From:" nil nil "5"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA29919; Mon, 18 May 92 16:38:55 EDT Received: by luke (4.1/TOC-1.1C) id AA15183; Mon, 18 May 92 16:43:11 EDT Message-Id: <9205182043.AA15183@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: Abalone redistributable? Date: Mon, 18 May 92 16:43:11 EDT Does anyone object to me making the Abalone program freely redistributable (copylefted) and giving it to people who request it? (Including our little paper on the unreachable positions.) -Mike From mpf@medg.lcs.mit.edu Sun Jul 19 17:40:59 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1202" "Sun" "19" "July" "92" "17:41:41" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "29" "Abalone mailing" "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07129; Sun, 19 Jul 92 17:40:37 EDT Received: by luke (4.1/TOC-1.1C) id AA12314; Sun, 19 Jul 92 17:41:41 EDT Message-Id: <9207192141.AA12314@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: Abalone mailing Date: Sun, 19 Jul 92 17:41:41 EDT Abalone enthusiasts, I have just added some people to the Abalone mailing list: Jonathan Roy Andreas Thurnherr Also, I have a couple of announcements: 1. To add or remove yourself from the abalone mailing list, send mail to the list maintainers (me) at 'abalone-list@medg.lcs.mit.edu'. Don't send such requests to the main 'abalone' list. (I get several mailing lists whose volume consists of 90% "add me" and "remove me" messages. Not fun.) 2. I am going to call the American Federation of Abalone tomorrow to try to find out what their policy is, regarding people writing and giving away non-commercial computer implementations of Abalone. If I get their permission, I will set up our MIT Abalone-playing program for anonymous FTP, and all of us can feel free to exchange Abalone-playing code. Also, to try to get some activity going on this list, I will begin to periodically send out mailings, in which I will open a discussion on some interesting aspect of Abalone. Everyone should feel free to make their own comments and send them to the list. This is not a moderated mailing list. -Mike From ant@ips.id.ethz.ch Sun Jul 19 17:58:34 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["525" "Sun" "19" "July" "92" "23:58:54" "+0200" "ant@ips.id.ethz.ch" "ant@ips.id.ethz.ch" nil "12" "Re: Abalone mailing " "^From:" nil nil "7"]) Return-Path: Received: from bernina.ethz.ch by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07147; Sun, 19 Jul 92 17:58:10 EDT Received: from maggia-gw by bernina.ethz.ch with SMTP inbound id <20400-0@bernina.ethz.ch>; Sun, 19 Jul 1992 23:58:58 +0200 Message-Id: <9207192152.AA24631@sitter> Received: from julia by sitter id AA24631; Sun, 19 Jul 92 23:52:42 +0200 In-Reply-To: Your message of "Sun, 19 Jul 92 17:41:41 EDT." <9207192141.AA12314@luke> From: ant@ips.id.ethz.ch To: abalone@medg.lcs.mit.edu Subject: Re: Abalone mailing Date: Sun, 19 Jul 92 23:58:54 +0200 >2. I am going to call the American Federation of Abalone tomorrow to > try to find out what their policy is, regarding people writing > and giving away non-commercial computer implementations of > Abalone. If I get their permission, I will set up our MIT > Abalone-playing program for anonymous FTP, and all of us can > feel free to exchange Abalone-playing code. I'll do the same with my program. If the American assoc allows it, then probaly they will have checked with the French inventors. - Andreas From mpf@medg.lcs.mit.edu Sun Jul 19 18:07:43 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2095" "Sun" "19" "July" "92" "18:08:25" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "46" "'dead-end' Abalone positions " "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07162; Sun, 19 Jul 92 18:07:22 EDT Received: by luke (4.1/TOC-1.1C) id AA12348; Sun, 19 Jul 92 18:08:25 EDT Message-Id: <9207192208.AA12348@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: 'dead-end' Abalone positions Date: Sun, 19 Jul 92 18:08:25 EDT As some of you know already, it turns out that there are reachable Abalone positions for which the side to play cannot make a move. Let us call these positions 'dead-end' positions. For example, here is a dead-end position we discovered a few months ago: . . . . . . . . . . . . . . . . . . @ = white @ . . . . . . @ O = black O @ . . . . . @ O . = empty O @ . . . . @ O O @ . . . @ O O @ @ @ @ O O O O O O Black to move Note that black cannot move, unless he is allowed to 'suicide' by moving one of his own pieces off the board. We have found that this position is indeed reachable from the initial position, if the players cooperate to reach it. Probably white could not force black into this position. But for random or cooperating players, the position is theoretically possible. Thus, the Abalone rules are incomplete, in that they do not provide for a 'suicide' move, nor do they specify what happens if there are no legal moves. I called the American Federation of Abalone about this, and they were unaware of the existence of dead-end moves and did not know of any official Abalone rules that would resolve the conflict. Note that in the above position, only 13 marbles are left on each team. It turns out that there are dead-end positions that use all 28 of the marbles. Let us call such dead-end positions 'complete' dead-end positions. Here at MIT, we've come up with 3 different complete dead-end positions. Puzzle for the reader: find some different dead-end positions. See if you can find some that are complete. Send your answers to this mailing list. (You can use the above diagram as a template. If you've already seen the answers we came up with at MIT, please refrain from answering for a while so as not to spoil the puzzle for others.) -Mike From ninja@halcyon.halcyon.com Sun Jul 19 19:30:53 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["610" "Sun" "19" "July" "1992" "16:34:40" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "16" "Dead ends -- #1" "^From:" nil nil "7"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07195; Sun, 19 Jul 92 19:30:31 EDT Received: by halcyon.com id AA13377 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Sun, 19 Jul 1992 16:34:40 -0700 Message-Id: <199207192334.AA13377@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: Dead ends -- #1 Date: Sun, 19 Jul 1992 16:34:40 -0700 Here's the first I've found. Is this a MIT pre-found one? . . . . . . . . . . . . . . . . . . * = black * . . . . . . * O = white O * . . . . . * O . = empty O * . * * . * O O * * . * * O O O * * O O O O O O O As far as I see, all balls are needed, if white is to move. Side nite: In the US, Black moves first. Isn't it the same overseas? From ninja@halcyon.halcyon.com Sun Jul 19 19:32:18 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["490" "Sun" "19" "July" "1992" "16:35:52" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" "<199207192335.AA13382@halcyon.com>" "14" "Dead ENd #1- correction" "^From:" nil nil "7"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07200; Sun, 19 Jul 92 19:31:42 EDT Received: by halcyon.com id AA13382 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Sun, 19 Jul 1992 16:35:52 -0700 Message-Id: <199207192335.AA13382@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: Dead ENd #1- correction Date: Sun, 19 Jul 1992 16:35:52 -0700 Slight error... . . . . . . . . . . . . . . . . . . * = black . . . . . . . * O = white * * . . . . . * O . = empty O * . * * . * O O * * . * * O O O * * O O O O O O O Is the correct board. Notice the lack of symmetry.. From ninja@halcyon.halcyon.com Sun Jul 19 19:43:10 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["443" "Sun" "19" "July" "1992" "16:47:01" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" "<199207192347.AA13432@halcyon.com>" "12" "Dead End #2" "^From:" nil nil "7"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07207; Sun, 19 Jul 92 19:42:53 EDT Received: by halcyon.com id AA13432 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Sun, 19 Jul 1992 16:47:01 -0700 Message-Id: <199207192347.AA13432@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: Dead End #2 Date: Sun, 19 Jul 1992 16:47:01 -0700 I've struck again... . . . . . * . . . . . O * . . . . . * = black * O * . . . . . O = white O * O * . . . . . . = empty O * O * . . . . O * * . . . . O O * * * * O O O O O From ninja@halcyon.halcyon.com Sun Jul 19 19:44:34 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["39" "Sun" "19" "July" "1992" "16:48:28" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "2" "Opps" "^From:" nil nil "7"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07216; Sun, 19 Jul 92 19:44:18 EDT Received: by halcyon.com id AA13449 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Sun, 19 Jul 1992 16:48:28 -0700 Message-Id: <199207192348.AA13449@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: Opps Date: Sun, 19 Jul 1992 16:48:28 -0700 My #1 is messed, but #2 is correct... From mpf@medg.lcs.mit.edu Sun Jul 19 20:06:18 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["921" "Sun" "19" "July" "92" "20:07:04" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "25" "Re: Compilation " "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07228; Sun, 19 Jul 92 20:06:00 EDT Received: by luke (4.1/TOC-1.1C) id AA12504; Sun, 19 Jul 92 20:07:04 EDT Message-Id: <9207200007.AA12504@luke> In-Reply-To: <9207192113.AA24590@sitter> References: <9207191953.AA11199@luke> <9207192113.AA24590@sitter> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: ant@ips.id.ethz.ch Cc: abalone Subject: Re: Compilation Date: Sun, 19 Jul 92 20:07:04 EDT Andreas, I just manually carried out 2 games between your program and mine. Game 1: your prog: default parameters (3 ply) our prog: Conspiracy theory (abalone -c -p), 100000 nodes our prog moves first and wins, 6-1 or 6-2, I forget. Game 2: your prog: default parameters (3 ply) our prog: alpha-beta (abalone -a -p), 3 ply our prog moves first and loses, 5-6. It was pretty tedious entering the moves for both programs, though. We need to devise a protocol for abalone-playing between different programs, and modify both our programs to allow playing against other programs using that protocol. Kind of like how gnuchess works. Also, we need to think of unique names for our programs; right now they're both called 'abalone', which makes it hard to refer to them unambiguously. I notice yours says 'COMPALONE' on its display. That would be a fine name. I'll try to think of a name for my program. -Mike From mpf@medg.lcs.mit.edu Sun Jul 19 20:08:09 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["771" "Sun" "19" "July" "92" "20:08:56" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "20" "Re: Dead End #2" "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07233; Sun, 19 Jul 92 20:07:52 EDT Received: by luke (4.1/TOC-1.1C) id AA12511; Sun, 19 Jul 92 20:08:56 EDT Message-Id: <9207200008.AA12511@luke> In-Reply-To: <199207192347.AA13432@halcyon.com> References: <199207192347.AA13432@halcyon.com> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: Jonathan Roy Cc: abalone Subject: Re: Dead End #2 Date: Sun, 19 Jul 92 20:08:56 EDT >>>>> On Sun, 19 Jul 1992 16:47:01 -0700, Jonathan Roy said: Jonathan> I've struck again... Jonathan> Jonathan> . . . . . Jonathan> * . . . . . Jonathan> O * . . . . . * = black Jonathan> * O * . . . . . O = white Jonathan> O * O * . . . . . . = empty Jonathan> O * O * . . . . Jonathan> O * * . . . . Jonathan> O O * * * * Jonathan> O O O O O That's pretty cool! No, we didn't come up with that one here. I'll wait a few more days and then post our solutions. -Mike From mpf@medg.lcs.mit.edu Mon Jul 20 13:57:39 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2904" "Mon" "20" "July" "92" "13:58:35" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "65" "Inter-program Abalone Protocol" "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08053; Mon, 20 Jul 92 13:57:28 EDT Received: by luke (4.1/TOC-1.1C) id AA13277; Mon, 20 Jul 92 13:58:35 EDT Message-Id: <9207201758.AA13277@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: Inter-program Abalone Protocol Date: Mon, 20 Jul 92 13:58:35 EDT For communication between Abalone programs, I suggest that the underlying mechanism should be plain sockets, with a standard default range of socket numbers for communicating with Abalone programs running on a given machine. I propose (totally arbitrarily) 12600 and up. (I.e., first look for an Abalone-playing program at 12600. If it's not there, try 12601, etc. Stop when you get tired.) Now, instead of picking an inflexible inter-program protocol for all time, I think it would be nice to have an extensible framework within which we can make up new protocols and improve them without breaking older programs. So I propose that all Abalone programs that communicate with others using sockets at 12600 understand at least the following meta-protocol (this is just an idea, feel free to propose alternatives): Abalone Meta-Protocol 0.0 Two Abalone programs that have just connected using sockets should, first thing, agree on the protocol they will use, by taking turns sending text messages of the form: Abalone protocol %s\n Where '%s' is the name of the protocol being proposed by the program sending the text, and '\n' is, of course, newline. Protocol names should be ASCII text with no whitespace. The program that initiates the socket connection should make the first proposal. During this protocol-deciding phase, if either program receives text that is not in the above form, it should close the connection. Each program should make its protocol-proposals in order from the program's most-preferred protocol to its least-preferred protocol. When a program runs out of protocols it understands, it should close the connection. When a program receives a protocol-proposal, it should check the list of protocols it understands. If it understands the protocol, it must accept it and echo the protocol-proposal back to the sender, to indicate agreement. Then it may begin following the agreed-upon protocol. Likewise, when a program receives back the protocol-proposal it just sent, it should take this to mean agreement, and should begin following that protocol. End of Meta-protocol. Any comments? I volunteer to implement this meta-protocol, or whatever one we settle on, in the form of a library that I will make available for anyone to incorporate into their Abalone programs. This way, we can all easily invent new protocols and incorporate them into our own programs without breaking our program's ability to communicate with older programs. Of course, we will have to have some real Abalone protocols that are understood by all (or most) Abalone programs for this to do any good. So, everyone feel free to invent your own favorite Abalone-playing protocol, give it a name for use in the meta-protocol, and post it to this mailing list. Hopefully we will settle on a minimal Abalone protocol that all our programs will understand. -Mike From ant@ips.id.ethz.ch Mon Jul 20 16:14:21 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["365" "Mon" "20" "July" "92" "22:14:39" "+0200" "ant@ips.id.ethz.ch" "ant@ips.id.ethz.ch" "<9207202008.AA28190@sitter>" "10" "Re: Inter-program Abalone Protocol " "^From:" nil nil "7"]) Return-Path: Received: from bernina.ethz.ch by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08247; Mon, 20 Jul 92 16:13:51 EDT Received: from maggia-gw by bernina.ethz.ch with SMTP inbound id <17831-0@bernina.ethz.ch>; Mon, 20 Jul 1992 22:14:43 +0200 Message-Id: <9207202008.AA28190@sitter> Received: from julia by sitter id AA28190; Mon, 20 Jul 92 22:08:24 +0200 In-Reply-To: Your message of "Mon, 20 Jul 92 13:58:35 EDT." <9207201758.AA13277@luke> From: ant@ips.id.ethz.ch To: abalone@medg.lcs.mit.edu Subject: Re: Inter-program Abalone Protocol Date: Mon, 20 Jul 92 22:14:39 +0200 Looks interesting but, frankly, like a bit of an overkill to me. If there exists a library, I'll use it, of course. On the other hand there apparently exists a protocol which is used at the computer game olymics. Maybe we should check that one out? It's supposed to be versatile and we wouldn't have to reprogram anything in case our progs ever go there :-) ant From ninja@halcyon.halcyon.com Mon Jul 20 19:08:01 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["349" "Mon" "20" "July" "1992" "16:11:41" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "9" "Abalone/Computer Olympiad" "^From:" nil nil "7"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08618; Mon, 20 Jul 92 19:07:27 EDT Received: by halcyon.com id AA20489 (5.65c/IDA-1.4.4 for mpf@medg.lcs.mit.edu); Mon, 20 Jul 1992 16:11:41 -0700 Message-Id: <199207202311.AA20489@halcyon.com> From: Jonathan Roy To: mpf@medg.lcs.mit.edu Cc: abalone@medg.lcs.mit.edu Subject: Abalone/Computer Olympiad Date: Mon, 20 Jul 1992 16:11:41 -0700 If at least two programs enter the Computer Olympiad in a catagory, they'll be an official slot for it in the future... Thus, if both mpf and ant both entered the Olympiad, and maybe another person or two, the interest would really grow... (Since it'd be a published competiton catagory in next year's event....) Something to think about. (grin) From mpf@medg.lcs.mit.edu Mon Jul 20 20:41:01 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["451" "Mon" "20" "July" "92" "20:41:58" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "10" "Re: Inter-program Abalone Protocol " "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08672; Mon, 20 Jul 92 20:40:51 EDT Received: by luke (4.1/TOC-1.1C) id AA13473; Mon, 20 Jul 92 20:41:58 EDT Message-Id: <9207210041.AA13473@luke> In-Reply-To: <9207202008.AA28190@sitter> References: <9207201758.AA13277@luke> <9207202008.AA28190@sitter> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: ant@ips.id.ethz.ch Cc: abalone Subject: Re: Inter-program Abalone Protocol Date: Mon, 20 Jul 92 20:41:58 EDT >>>>> On Mon, 20 Jul 92 22:14:39 +0200, ant@ips.id.ethz.ch said: ant> On the other hand there apparently exists a protocol which is ant> used at the computer game olymics. Maybe we should check that one ant> out? It's supposed to be versatile and we wouldn't have to ant> reprogram anything in case our progs ever go there :-) Yes, that's a good idea. Let's wait till Jonathan hears from his source before proceeding to develop the protocol. -Mike From torrance@ai.mit.edu Mon Jul 20 22:51:47 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1282" "Mon" "20" "July" "92" "22:49:24" "EDT" "Mark Torrance" "torrance@ai.mit.edu " nil "26" "3 player abalone" "^From:" nil nil "7"]) Return-Path: Received: from life.ai.mit.edu by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08805; Mon, 20 Jul 92 22:51:21 EDT Received: from cookie-monster (cookie-monster.ai.mit.edu) by life.ai.mit.edu (4.1/AI-4.10) id AA23503; Mon, 20 Jul 92 22:52:18 EDT Received: by cookie-monster (4.1/AI-4.10) id AA01094; Mon, 20 Jul 92 22:49:24 EDT Message-Id: <9207210249.AA01094@cookie-monster> From: torrance@ai.mit.edu (Mark Torrance) To: abalone@medg.lcs.mit.edu Subject: 3 player abalone Date: Mon, 20 Jul 92 22:49:24 EDT I have played 3 player Abalone. It is an "elimination" format in which you are out of the game once you have lost 6 of your marbles. Each player begins the game with two fewer marbles than usual; the extreme left and right marbles are removed. Once one player is eliminated, the other two players take turns as usual. The eliminated player's remaining marbles may be pushed about or off as usual. Persuading your opponents that they are each other's most imminent threat turns out to be an important strategy. I believe the rules do allow a player to use 3 marbles to push a mixed set of 2 marbles consisting of one from each opponent, but I'm not positive on this one. I have considered an interesting extension using an idea borrowed from Diplomacy. In this extension, a player would be allowed to use the marbles of another player in combination with his own to push the third player, but only with the explicit verbal consent, at the time of the move, of the cooperating player. This could lead to interesting "you help me now, I'll help you later" interactions. I may not have the rules for 3 player abalone exactly correct above. I think the complete rule modifications are listed on each package of extra balls for the board game, sold separately. --Mark Torrance From pure!pure.com!piaw@uu4.psi.com Tue Jul 21 14:40:14 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["336" "Tue" "21" "July" "92" "09:03:34" "PDT" "Na Choon Piaw" "piaw@pure.com " "<9207211603.AA01547@pure.com>" "8" "n-player Abalone." "^From:" nil nil "7"]) Return-Path: Received: from uu4.psi.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA09468; Tue, 21 Jul 92 14:39:53 EDT Received: from pure.UUCP by uu4.psi.com (5.65b/4.0.071791-PSI/PSINet) id AA02113; Tue, 21 Jul 92 13:10:33 -0400 Received: from fuji.pure by pure.com (4.1/Anterior/SMI-4.0) id AA01547; Tue, 21 Jul 92 09:03:34 PDT Message-Id: <9207211603.AA01547@pure.com> Received: by fuji.pure (4.1/SMI-4.1) id AA07234; Tue, 21 Jul 92 09:04:57 PDT From: piaw@pure.com (Na Choon Piaw) To: abalone@medg.lcs.mit.edu Subject: n-player Abalone. Date: Tue, 21 Jul 92 09:03:34 PDT I remember an Abalone board for sale at Games of Berkeley that permitted up to 6 players. The board size is different, but I wonder if anyone else has seen it --- I might have remembered wrong. Piaw "At first, I thought memory was cheap. And then there were breakthroughs, and now I think memory is free!" --- Mel Nicholson, 1992. From ninja@halcyon.halcyon.com Sat Jul 25 01:19:54 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["72" "Fri" "24" "July" "1992" "22:24:11" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" "<199207250524.AA04535@halcyon.com>" "3" "Abalone distribution..." "^From:" nil nil "7"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA01422; Sat, 25 Jul 92 01:19:40 EDT Received: by halcyon.com id AA04535 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Fri, 24 Jul 1992 22:24:11 -0700 Message-Id: <199207250524.AA04535@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: Abalone distribution... Date: Fri, 24 Jul 1992 22:24:11 -0700 So, any word on teh legality of distributing abalone playing software? From mpf@medg.lcs.mit.edu Sat Jul 25 16:41:14 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["381" "Sat" "25" "July" "92" "16:42:21" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "10" "Re: Abalone distribution..." "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA01748; Sat, 25 Jul 92 16:40:55 EDT Received: by luke (4.1/TOC-1.1C) id AA01409; Sat, 25 Jul 92 16:42:21 EDT Message-Id: <9207252042.AA01409@luke> In-Reply-To: <199207250524.AA04535@halcyon.com> References: <199207250524.AA04535@halcyon.com> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: Jonathan Roy Cc: abalone Subject: Re: Abalone distribution... Date: Sat, 25 Jul 92 16:42:21 EDT >>>>> On Fri, 24 Jul 1992 22:24:11 -0700, Jonathan Roy said: Jonathan> So, any word on teh legality of distributing abalone playing Jonathan> software? Not yet. The guy at American Abalone Federation said he would get back to me; that it takes a while to get answers back from the dudes in France. I'll send mail as soon as I hear something. -Mike From ninja@halcyon.halcyon.com Fri Jul 31 18:20:35 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["223" "Fri" "31" "July" "1992" "15:25:07" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "7" "American Abalone Federation" "^From:" nil nil "7"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08994; Fri, 31 Jul 92 18:20:01 EDT Received: by halcyon.com id AA04070 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Fri, 31 Jul 1992 15:25:07 -0700 Message-Id: <199207312225.AA04070@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: American Abalone Federation Date: Fri, 31 Jul 1992 15:25:07 -0700 Has anyone out there joined the NA Abalone Federation (Or whatever the exact name is..) If so, is there any sort of newsletter or magazine one gets? Just sort of curious... I'm not a member myself, obviously. Thanks. From mpf@medg.lcs.mit.edu Mon Jul 20 14:41:16 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2507" "Mon" "20" "July" "92" "14:42:09" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "77" "Board position notation" "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08120; Mon, 20 Jul 92 14:41:02 EDT Received: by luke (4.1/TOC-1.1C) id AA13302; Mon, 20 Jul 92 14:42:09 EDT Message-Id: <9207201842.AA13302@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: Board position notation Date: Mon, 20 Jul 92 14:42:09 EDT Below is my favorite notation so far for indicating positions on the Abalone board. This is partly due to Andreas Thurnherr . Like in Andreas' program, positions are indicated by a letter-number pair, e.g., "a1", "d5", etc. The letter may be either upper or lower case. Unlike Andreas' notation, the letter indicates not a vertical column but rather a 'diagonal column', as shown: /---------\ 9 -/ @ @ @ @ @ \ 8 -/ @ @ @ @ @ @ \ 7 -/ . . @ @ @ . . \ @ = white R 6 -/ . . . . . . . . \ O = black O 5 -| . . . . . . . . . | . = empty W 4 -\ . . . . . . . . / S 3 -\ . . O O O . . / \ 2 -\ O O O O O O / \ I 1 -\ O O O O O / \ H \---------/ \ G DIAGONAL COLUMNS \ \ \ \ \ F A B C D E (If you unskew the coordinate system, the board looks skewed, like this:) 9 -| @ @ @ @ @ 8 -| @ @ @ @ @ @ 7 -| . . @ @ @ . . R 6 -| . . . . . . . . O 5 -| . . . . . . . . . W 4 -| . . . . . . . . S 3 -| . . O O O . . 2 -| O O O O O O 1 -| O O O O O ------------------ | | | | | | | | | A B C D E F G H I DIAGONAL COLUMNS I like this notation because: 1. The rows are symmetrical to the columns. 2. Marbles in a line on the board will always have either: * The same row number (a1,b1), or * The same diagonal column letter (a1,a2), or * Row and column differing by the same amount (a1,b2). 3. Representational efficiency: over 3/4 of all pairs of a number (1-9) and letter (A-I) correspond to actual board positions. This position notation can be combined with Andreas' direction notation: NW NE \ / W --O-- E / \ SW SE to produce a compact, easy-to-write, easy-to-read move notation. For example, you might represent some of black's opening moves like this: a1,ne Move marble at A1 to the north-east (line of 3) a2b2,nw Broadside, move marbles at A2 and B2 to the north-west c3-e3,ne Broadside, move marbles C3, D3, and E3 to the north-east I'm not sure what punctuation would be best. Also, for purposes of recording games, we might want to add some notation indicating pushes and ejections, like they use in chess to indicate captures, check and checkmate. -Mike From mpf@medg.lcs.mit.edu Mon Jul 20 21:00:34 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["491" "Mon" "20" "July" "92" "20:59:59" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "21" "Re: List" "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08709; Mon, 20 Jul 92 20:58:51 EDT Received: by luke (4.1/TOC-1.1C) id AA13491; Mon, 20 Jul 92 20:59:59 EDT Message-Id: <9207210059.AA13491@luke> In-Reply-To: <199207210059.AA20960@halcyon.com> References: <199207210059.AA20960@halcyon.com> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: Jonathan Roy Cc: abalone Subject: Re: List Date: Mon, 20 Jul 92 20:59:59 EDT >>>>> On Mon, 20 Jul 1992 17:59:24 -0700, Jonathan Roy said: Jonathan> How many people are on teh list? Right now, 13. mpf, \ cwitty, \ rjbodkin, \_@medg.lcs.mit.edu torrance, / barney, / milos, / hofmeist, / sajit@ai.mit.edu piaw@peoplesparc.berkeley.edu (Na Choon Piaw), 70621.1732@compuserve.com (Michael Gilbert), Jonathan Roy , Andreas Thurnherr , palmerp@math.orst.edu -Mike From mpf@medg.lcs.mit.edu Mon Jul 20 21:42:06 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["707" "Mon" "20" "July" "92" "21:43:00" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "17" "Re: Protocol \"TINY\" (Please don't laugh! :)" "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08737; Mon, 20 Jul 92 21:41:52 EDT Received: by luke (4.1/TOC-1.1C) id AA13509; Mon, 20 Jul 92 21:43:00 EDT Message-Id: <9207210143.AA13509@luke> In-Reply-To: <199207210059.AA20957@halcyon.com> References: <199207210059.AA20957@halcyon.com> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: Jonathan Roy Cc: abalone Subject: Re: Protocol "TINY" (Please don't laugh! :) Date: Mon, 20 Jul 92 21:43:00 EDT Jonathan, I don't remember the 3-player rules, but I have them at home... I'll type them in later. One person here (Ron Bodkin) is working on multi-player game-playing algorithms, which would be applicable to 3-player computer Abalone. There also exist variations for 4 and 6 players. Thanks, Jonathan, for the TINY protocol. Yes, individial bytes can be sent via Internet. However, keep in mind that internet overhead is many, many bytes per packet. I don't know how much efficiency is gained by compressing the move into such a small number of bytes. However, that representation would be great for storing and sending large numbers of moves, such as transcripts of complete Abalone games. -Mike From mpf@medg.lcs.mit.edu Mon Jul 20 21:57:17 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["889" "Mon" "20" "July" "92" "21:58:04" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "23" "Re: Olympiad" "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08744; Mon, 20 Jul 92 21:56:56 EDT Received: by luke (4.1/TOC-1.1C) id AA13520; Mon, 20 Jul 92 21:58:04 EDT Message-Id: <9207210158.AA13520@luke> In-Reply-To: <9207210110.AA00802@lode> References: <9207210110.AA00802@lode> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: Re: Olympiad Date: Mon, 20 Jul 92 21:58:04 EDT Unfortunately, I can't make the Computer Olympiad this year as I will be on vacation in Florida. Possibly someone else (Carl, Mark, Ron?) could present our program. I'll try to find the Computer Go articles, and I'll send mail to Martin Muller about the Smart Game Board. Barney.Pell> 1. I suggest you use @ for black, and O for white stones, Barney.Pell> just like we do in GO. ('+' is good for marking grid Barney.Pell> points, so isn't use as a stone marker). Ok; I suppose it would be good to follow convention. Barney.Pell> 2. I'd like to see an X-Abalone program, an IAS (internet Barney.Pell> abalone server), and XIAS (the x interface to that Barney.Pell> server). Barney, what do you mean by the IAS? A server that would allow people all over the internet to connect up and play Abalone against random other people? Perhaps you could tell us more details. Thanks, -Mike From mpf@medg.lcs.mit.edu Thu May 28 15:44:34 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["901" "Thu" "28" "May" "92" "15:48:57" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "20" "forwarded message from Michael Gilbert" "^From:" nil nil "5"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA14441; Thu, 28 May 92 15:44:05 EDT Received: by luke (4.1/TOC-1.1C) id AA22843; Thu, 28 May 92 15:48:57 EDT Message-Id: <9205281948.AA22843@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: forwarded message from Michael Gilbert Date: Thu, 28 May 92 15:48:57 EDT ------- Start of forwarded message ------- Return-Path: <70621.1732@compuserve.com> Received: from ihb.compuserve.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA14418; Thu, 28 May 92 15:33:15 EDT Received: by ihb.compuserve.com (5.65/5.910516) id AA16888; Thu, 28 May 92 15:37:55 -0400 Message-Id: <920528192240_70621.1732_DHB50-1@CompuServe.COM> From: Michael Gilbert <70621.1732@compuserve.com> To: Subject: Re: Computer Abalone Date: 28 May 92 15:22:41 EDT yes there will a pc Version of Abalone coming out soon. This version presently runs in Windows 3.0 or 3.1. You must have a supervga card and the capability of displaying 256 colors. The graphics are VERY high end with a nice user interface (some say it looks better than the real board) If more information is needed call me at 609-871-7741 between 5pm and 11:30pm EST.. ------- End of forwarded message ------- From mpf@medg.lcs.mit.edu Mon Jul 20 11:26:28 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2999" "Mon" "20" "July" "92" "11:27:06" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "75" "Re: Compilation " "^From:" nil nil "7"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07819; Mon, 20 Jul 92 11:26:00 EDT Received: by luke (4.1/TOC-1.1C) id AA13155; Mon, 20 Jul 92 11:27:06 EDT Message-Id: <9207201527.AA13155@luke> In-Reply-To: <9207200855.AA26287@sitter> References: <9207200007.AA12504@luke> <9207200855.AA26287@sitter> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: ant@ips.id.ethz.ch Cc: abalone Subject: Re: Compilation Date: Mon, 20 Jul 92 11:27:06 EDT Hi Andreas, >>>>> On Mon, 20 Jul 92 11:01:27 +0200, ant@ips.id.ethz.ch said: ant> Hi: >Game 1: > your prog: default parameters (3 ply) > our prog: Conspiracy theory (abalone -c -p), 100000 nodes > our prog moves first and wins, 6-1 or 6-2, I forget. ant> Gasp! Of course, that result doesn't mean much; to be fair, you would want both programs to search the same number of nodes, or take the same amount of time, or something like that. It wouldn't be too hard to change the alpha-beta player to do iterative deepening and stop after examining 100000 nodes. Or give both programs an n-second time limit. >Game 2: > your prog: default parameters (3 ply) > our prog: alpha-beta (abalone -a -p), 3 ply > our prog moves first and loses, 5-6. ant> Nice. I was going to have a 4-ply battle between the programs, but I got tired of entering moves. A real tournament, with time limits and such, will have to wait until we can code up the inter-program protocol. (Of course, if the programs are running on different types of machines, you can't really compare them on the basis of time, unless you handicap them by the MIPS-rating of the machine or something.) >It was pretty tedious entering the moves for both programs, though. >We need to devise a protocol for abalone-playing between different >programs, and modify both our programs to allow playing against other >programs using that protocol. Kind of like how gnuchess works. ant> That's also what I've been thinking. I don't know gnuchess, though. I ant> was thinking about maybe setting up 2 named pipes the programs could ant> connect to. GNUchess does something like that. Well, maybe it just uses stdin and stdout or something. Probably the best way is to set up sockets that can be connected to over the Internet. ant> I was also thinking about a move representation suitable for both ant> programs (this is just an idea): ant> ant> Move = Direction #_of_marbles MarbleList. ant> Direction = {0(N),1(NW),2(W),...,5(NE)}. ant> MarbleList = Position | MarbleList Position. ant> Position = See Note below. ant> I propose to number the board in the following form: ant> - Center hole = 0 ant> - continue numbering in the same direction as writing (0-4 in line ant> 5, 5-12 on line 4, ...) ant> - symetrically number the remaining holes with negative numbers ant> This scheme has the main advantage of being symmetric with respect to ant> the colors. If both progs play white, all moves can be negated to make ant> them work for black. I'll send out a separate message commenting on protocols. >Also, we need to think of unique names for our programs; right now >they're both called 'abalone', which makes it hard to refer to them >unambiguously. I notice yours says 'COMPALONE' on its display. That >would be a fine name. I'll try to think of a name for my program. ant> Ok. An old version once was called compalone; I'll rename it for ant> release. ant> - ant I was thinking about MIT-Abalone for ours. -Mike From ninja@halcyon.halcyon.com Sat Aug 15 20:26:36 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["60" "Sat" "15" "August" "1992" "17:26:31" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" "<199208160026.AA08440@halcyon.com>" "3" "Been queit." "^From:" nil nil "8"]) Return-Path: Received: from halcyon.com by MEDG (4.1/TOC-1.2S) id AA11606; Sat, 15 Aug 92 20:26:05 EDT Received: by halcyon.com id AA08440 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Sat, 15 Aug 1992 17:26:31 -0700 Message-Id: <199208160026.AA08440@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: Been queit. Date: Sat, 15 Aug 1992 17:26:31 -0700 Been real quiet... Any news from the world of Abalone? :) From mpf@medg.lcs.mit.edu Mon Aug 17 12:15:37 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1264" "Mon" "17" "August" "92" "12:11:10" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "29" "Conditional permission to distribute" "^From:" nil nil "8"]) Return-Path: Received: from laennec (LAENNEC.LCS.MIT.EDU) by MEDG (4.1/TOC-1.2S) id AA15257; Mon, 17 Aug 92 12:15:09 EDT Received: by laennec (4.1/TOC-1.1C) id AA25372; Mon, 17 Aug 92 12:11:10 EDT Message-Id: <9208171611.AA25372@laennec> In-Reply-To: <199208160026.AA08440@halcyon.com> References: <199208160026.AA08440@halcyon.com> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: Conditional permission to distribute Date: Mon, 17 Aug 92 12:11:10 EDT >>>>> On Sat, 15 Aug 1992 17:26:31 -0700, Jonathan Roy said: Jonathan> Been real quiet... Any news from the world of Abalone? :) Hi, Jonathan and abalone enthusiasts: I heard back from my contact at the Abalone Games Corporation; he talked to their president, and they say we can distribute Abalone programs free on Internet as long as they include the following information on the screen. I think this should probably go in the source, documentation, and in the opening screen of the game. We can rephrase this, but the same basic information should be in there. The game of Abalone is copyright (C) 1992 by the Abalone Games Corporation. Created by Michel Lalet and Laurent Levi. Available in board game form at your local game store. For more information on Abalone, playing tips, and strategies, call the Abalone Games Corporation at 1-800-666-5040. I think, to be safe, the notice should probably also say: The above information must be included in the source, documentation, and opening screen of all Abalone programs. However, he said to wait one or two days to begin distribution in case they think of something else they want to put in the notice. If I hear anything else from him I'll let you know. -Mike From mpf Tue Aug 18 17:30:56 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["895" "Tue" "18" "August" "92" "17:30:48" "EDT" "Michael Frank" "mpf@medg.lcs.mit.edu " nil "17" "Problems" "^From:" nil nil "8"]) Return-Path: Received: by MEDG (4.1/TOC-1.2S) id AA02610; Tue, 18 Aug 92 17:30:48 EDT Message-Id: <9208182130.AA02610@MEDG> From: mpf@medg.lcs.mit.edu (Michael Frank) To: abalone Subject: Problems Date: Tue, 18 Aug 92 17:30:48 EDT Well, the stupid Abalone Corp. called me back today, and the president or creator or somebody is having second thoughts... they want to see the program before giving permission to distribute it... I asked them what it was they wanted to know about it. The guy didn't know, but he said he would put me in contact with the head honcho himself later this week so that I can talk to him about it... I don't know whether they're worried that maybe the game isn't quite Abalone and thus shouldn't go out under that name, or maybe they're worried that if the user interface is really good, it will cut down their sales of the board game, or what... In any case, I'm annoyed because it means that anyone who writes an Abalone program will have to make sure it conforms to whatever stupid conditions they want to impose (such as a crummy user interface), which cuts down on our freedom a lot... -Mike From ninja@halcyon.halcyon.com Wed Aug 19 03:20:42 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["861" "Wed" "19" "August" "1992" "00:21:12" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "21" "Re: Problems" "^From:" nil nil "8"]) Return-Path: Received: from halcyon.com by MEDG (4.1/TOC-1.2S) id AA05163; Wed, 19 Aug 92 03:20:25 EDT Received: by halcyon.com id AA04783 (5.65c/IDA-1.4.4 for mpf@medg.lcs.mit.edu); Wed, 19 Aug 1992 00:21:12 -0700 Message-Id: <199208190721.AA04783@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu, mpf@medg.lcs.mit.edu Subject: Re: Problems Date: Wed, 19 Aug 1992 00:21:12 -0700 - they want to see the program before giving permission to distribute - it... I asked them what it was they wanted to know about it. The - guy didn't know, but he said he would put me in contact with the - head honcho himself later this week so that I can talk to him about - it... LAME! Talk about trying to stop progress... There are LOTS of chess programs out there, but they don't hurt the sales of commercial programs. Ask them if you'd have to send along each and every improvement the game, for them to "validate:. :) Do they even have a UNIX system to run the software on? Sigh. I just don't see how having some Abalone-AI discussion on the networks, and getting some competition at the Computer Olympiad (Which woould increase the awareness of Abalone, at least slightly) would hurt the board game sales! Sheesh. Just shoot them all. :) From ninja@halcyon.halcyon.com Sun Oct 11 00:15:29 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["800" "Sat" "10" "October" "1992" "21:17:52" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "14" "AI and Abalone" "^From:" nil nil "10"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA05594; Sun, 11 Oct 92 00:15:03 EDT Received: by halcyon.com id AA03615 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Sat, 10 Oct 1992 21:17:52 -0700 Message-Id: <199210110417.AA03615@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: AI and Abalone Date: Sat, 10 Oct 1992 21:17:52 -0700 My school has a Winter Term each year, where you take a single, specialized course, 5 days a week, and do alot of work on it... It looks like I"ll be taking "AI and Game Playing" this semester. Whats nice abot this course if you do all the work on a sepcifc game, of YOUR choice. :) I plan to use Abalone as my subject, if the instructor OK's it... I'll keep you all posted. Of course, I'll have to write the programs and such in Pascal, but oh well. ;) I'll post to C one day. :) F F Jonathan Roy, Vice President, Free Access Foundation. GEnie: J.ROY18 A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F "A server is a terrible thing to waste." Internet: ninja@halcyon.com "Everything that has transpired has done so according to my design." - _RotJ_ From @mitvma.mit.edu:AARONS@EARLHAM.BITNET Tue Nov 3 13:41:20 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["1151" "Tue" "3" "November" "1992" "13:45" "EST" "AARONS%EARLHAM.BITNET@mitvma.mit.edu" "AARONS%EARLHAM.BITNET@mitvma.mit.edu" "<01GQPTNW7APC000FCW@YANG.EARLHAM.EDU>" "19" "Hey, y'all! rec.games.abstract is here! irk your sysops to get it!" "^From:" nil nil "11"]) Return-Path: <@mitvma.mit.edu:AARONS@EARLHAM.BITNET> Received: from mitvma.mit.edu by MEDG (4.1/TOC-1.2S) id AA09637; Tue, 3 Nov 92 13:40:44 EST Received: from MITVMA.MIT.EDU by mitvma.mit.edu (IBM VM SMTP V2R2) with BSMTP id 1022; Tue, 03 Nov 92 13:46:07 EST Received: from EARLHAM.BITNET (AARONS) by MITVMA.MIT.EDU (Mailer R2.08 R208004) with BSMTP id 1380; Tue, 03 Nov 92 13:46:06 EST Received: from YANG.EARLHAM.EDU by YANG.EARLHAM.EDU (PMDF #12421) id <01GQPTNW7APC000FCW@YANG.EARLHAM.EDU>; Tue, 3 Nov 1992 13:45 EST Message-Id: <01GQPTNW7APC000FCW@YANG.EARLHAM.EDU> X-Envelope-To: ABALONE@MEDG.LCS.MIT.EDU X-Vms-To: ABALONE@MEDG.LCS.MIT.EDU From: AARONS%EARLHAM.BITNET@mitvma.mit.edu To: ABALONE@medg.lcs.mit.edu Subject: Hey, y'all! rec.games.abstract is here! irk your sysops to get it! Date: Tue, 3 Nov 1992 13:45 EST Okay, okay, too many !'s. anyway, see if you can't get rec.games.abstract for your newsgroup files. Unfortunately, I seem to be the only one on there. I was so excited when I saw that we got it (I had heard of its attempt to become a newsgroup) that I posted right away to ask some questions. It turned out I was the first poster. Since then (2-3 week of October?) No one has posted anything. Nothing! I really hope that Earlham College isn't the only school/group/etc. that gets rec.games.abstract, but I have seen no one else. Spread the word! Anyway, one of the things I mentioned was that I, with the help of another Abalone player/VAX user, developed a way of playing over email. I would be interested in showing you how it works. Quite simple. Maybe I should just show you all sometime. Another thing was/is that I am interested in finding any computer Abalone game, particularly for IBM+compatibles. I remember how one person said he was going to create one for his class, but are there any shareware/commercial versions out yet? Thank you for your time. Aaron G. Stock From mpf@medg.lcs.mit.edu Tue Nov 3 15:51:12 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1112" "Tue" "3" "November" "92" "15:57:00" "EST" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "28" "Re: Hey, y'all! rec.games.abstract is here! irk your sysops to get it!" "^From:" nil nil "11"]) Return-Path: Received: from lister (LISTER.LCS.MIT.EDU) by MEDG (4.1/TOC-1.2S) id AA09853; Tue, 3 Nov 92 15:50:36 EST Received: by lister (4.1/TOC-1.1C) id AA02774; Tue, 3 Nov 92 15:57:00 EST Message-Id: <9211032057.AA02774@lister> In-Reply-To: <01GQPTNW7APC000FCW@YANG.EARLHAM.EDU> References: <01GQPTNW7APC000FCW@YANG.EARLHAM.EDU> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: AARONS%EARLHAM.BITNET@mitvma.mit.edu Cc: abalone Subject: Re: Hey, y'all! rec.games.abstract is here! irk your sysops to get it! Date: Tue, 3 Nov 92 15:57:00 EST Arron, Michael Gilbert <70621.1732@compuserve.com>, who is on the Abalone list and occasionally reads his email, represents a company that has made a commercial PC version of Abalone. More info below. ------- Start of forwarded message ------- Return-Path: <70621.1732@compuserve.com> Received: from ihb.compuserve.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA14418; Thu, 28 May 92 15:33:15 EDT Received: by ihb.compuserve.com (5.65/5.910516) id AA16888; Thu, 28 May 92 15:37:55 -0400 Message-Id: <920528192240_70621.1732_DHB50-1@CompuServe.COM> From: Michael Gilbert <70621.1732@compuserve.com> To: Subject: Re: Computer Abalone Date: 28 May 92 15:22:41 EDT yes there will a pc Version of Abalone coming out soon. This version presently runs in Windows 3.0 or 3.1. You must have a supervga card and the capability of displaying 256 colors. The graphics are VERY high end with a nice user interface (some say it looks better than the real board) If more information is needed call me at 609-871-7741 between 5pm and 11:30pm EST.. ------- End of forwarded message ------- -Mike From ninja@halcyon.halcyon.com Tue Nov 3 18:46:42 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["657" "Tue" "3" "November" "1992" "15:49:34" "-0800" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "15" "Re: Hey, y'all! rec.games.abstract is here! irk your sysops to get it!" "^From:" nil nil "11"]) Return-Path: Received: from halcyon.com by MEDG (4.1/TOC-1.2S) id AA10358; Tue, 3 Nov 92 18:46:10 EST Received: by halcyon.com id AA25580 (5.65c/IDA-1.4.4 for ABALONE@medg.lcs.mit.edu); Tue, 3 Nov 1992 15:49:34 -0800 Message-Id: <199211032349.AA25580@halcyon.com> From: Jonathan Roy To: AARONS@earlham.bitnet, ABALONE@medg.lcs.mit.edu Subject: Re: Hey, y'all! rec.games.abstract is here! irk your sysops to get it! Date: Tue, 3 Nov 1992 15:49:34 -0800 Glad to hear about the newsgroup, but it hasn't shown up on my local feed. I don't think it was RFD'ed and passed as a legit group... I know _I_ never saw the ref for it.. :) I'll probably be doing AI research for Abalone in January. See ya all later!! (Anyone want to write Abalone server? I'll have the hardware to run it real soon.) F F Jonathan Roy, Vice President, Free Access Foundation. GEnie: J.ROY18 A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F "A server is a terrible thing to waste." Internet: ninja@halcyon.com "Everything that has transpired has done so according to my design." - _RotJ_ From ninja@halcyon.halcyon.com Tue Nov 3 19:14:23 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["419" "Tue" "3" "November" "1992" "16:16:59" "-0800" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "7" "Re: Hey, y'all! rec.games.abstract is here! irk your sysops to get it!" "^From:" nil nil "11"]) Return-Path: Received: from halcyon.com by MEDG (4.1/TOC-1.2S) id AA10399; Tue, 3 Nov 92 19:13:27 EST Received: by halcyon.com id AA26136 (5.65c/IDA-1.4.4 for mpf@medg.lcs.mit.edu); Tue, 3 Nov 1992 16:16:59 -0800 Message-Id: <199211040016.AA26136@halcyon.com> From: Jonathan Roy To: AARONS@earlham.bitnet, mpf@medg.lcs.mit.edu Cc: abalone@medg.lcs.mit.edu Subject: Re: Hey, y'all! rec.games.abstract is here! irk your sysops to get it! Date: Tue, 3 Nov 1992 16:16:59 -0800 A commercial Abalone is bad. Is might hurt our ability to distribute Abalone sofware over the net. :( F F Jonathan Roy, Vice President, Free Access Foundation. GEnie: J.ROY18 A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F "A server is a terrible thing to waste." Internet: ninja@halcyon.com "Everything that has transpired has done so according to my design." - _RotJ_ From eckserver!eckerd.edu!roy@uunet.uu.net Sat Dec 12 05:50:06 1992 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["990" "Fri" "11" "December" "92" "09:32:44" "EST" "Jonathan Roy" "roy@eckerd.edu " nil "24" "Software" "^From:" nil nil "12"]) Return-Path: Received: from relay2.UU.NET by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA02568; Sat, 12 Dec 92 05:49:26 EST Received: from uunet.uu.net (via LOCALHOST.UU.NET) by relay2.UU.NET with SMTP (5.61/UUNET-internet-primary) id AA07385; Sat, 12 Dec 92 05:57:23 -0500 Received: from eckserver.UUCP by uunet.uu.net with UUCP/RMAIL (queueing-rmail) id 055439.7869; Sat, 12 Dec 1992 05:54:39 EST Received: by eckserver.eckerd.edu (4.1/SMI-4.1:jhs102892) id AA04737; Fri, 11 Dec 92 09:32:44 EST Message-Id: <9212111432.AA04737@eckserver.eckerd.edu> From: roy@eckerd.edu (Jonathan Roy) To: abalone@medg.lcs.mit.edu Subject: Software Date: Fri, 11 Dec 92 09:32:44 EST One of the people out there in mailing list land has a abalone playing program written in ANSI C? Now that I've gotten gcc running on the Suns at my school, I'd like a new copy of it to try out... :) I'm taking "AI and Game Playing" this winter term (A winter term is a one-month class in January that meets every day for about 2-3 hours per day. You only take that single class.) We get to choose our own games to use... Abalone would be cool, but I'm afraid that'd be too complex for me to just jump right into... I'm thinking that I'll most likely go with Othello... Anyways, that's all I have to say for now. :) (This is ninja@halcyon.com writing from school.) F F Jonathan Roy, Vice President, Free Access Foundation. GEnie: J.ROY18 A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F "A server is a terrible thing to waste." Internet: ninja@halcyon.com "Everything that has transpired has done so according to my design." - _RotJ_ From ninja@halcyon.halcyon.com Mon Mar 29 01:36:14 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["595" "Sun" "28" "March" "1993" "22:34:45" "-0800" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "12" "Hey..." "^From:" nil nil "3"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA17259; Mon, 29 Mar 93 01:33:39 EST Received: by halcyon.com id AA00306 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Sun, 28 Mar 1993 22:34:45 -0800 Message-Id: <199303290634.AA00306@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu Subject: Hey... Date: Sun, 28 Mar 1993 22:34:45 -0800 Since there is so little traffic in here, I've posted to rec.games.abstract in responce to an Abalone competition's results about our list... It looks like 5 programs I've not heard of competed, and the two I know of did not. :( Lots of Abalone interest out there, obviously. F F Jonathan Roy, of the Free Access Foundation Email: ninja@faf.org A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F Vorlons, of the Galactic Bloodshed Development Team GEnie: J.ROY18 "Everything that has transpired has done so according to my design." - _RotJ_ From ninja@halcyon.halcyon.com Thu Apr 1 22:51:47 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["488" "Thu" "1" "April" "1993" "19:52:25" "-0800" "Jonathan Roy" "ninja@halcyon.halcyon.com" "<199304020352.AA09407@halcyon.com>" "9" "Re: HELP" "^From:" nil nil "4"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA01278; Thu, 1 Apr 93 22:50:52 EST Received: by halcyon.com id AA09407 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Thu, 1 Apr 1993 19:52:25 -0800 Message-Id: <199304020352.AA09407@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu, froument@lifl.fr Subject: Re: HELP Date: Thu, 1 Apr 1993 19:52:25 -0800 Speaking f which... Could whoever it is that runs the list let me (or us) know about how to join/exit teh list? I'd like to be able to tell people specificly how to join. F F Jonathan Roy, of the Free Access Foundation Email: ninja@faf.org A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F Vorlons, of the Galactic Bloodshed Development Team GEnie: J.ROY18 "Everything that has transpired has done so according to my design." - _RotJ_ From froument@lifl.fr Fri Apr 2 03:38:31 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1345" "Fri" "2" "April" "93" "10:35:34" "+0200" "froument@lifl.fr" "froument@lifl.fr" nil "37" "FAQs (without answers)" "^From:" nil nil "4"]) Return-Path: Received: from lifl.lifl.fr by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA01707; Fri, 2 Apr 93 03:37:48 EST Received: from blondine.lifl.fr by lifl.lifl.fr, Fri, 2 Apr 1993 10:39:08 +0200 Received: by blondine.lifl.fr, Fri, 2 Apr 93 10:35:34 +0200 Message-Id: <9304020835.AA08119@blondine.lifl.fr> From: froument@lifl.fr To: abalone@medg.lcs.mit.edu Subject: FAQs (without answers) Date: Fri, 2 Apr 93 10:35:34 +0200 > I added you to the abalone list. In future, send list maintenance > requests to abalone-request@medg.lcs.mit.edu. > > Thanks, > Mike > > P.S. Feel free to start a discussion, as nothing is happening on the > list right now. > Ok, let's go. Abalone and me. I first played Abalone four or five years ago, without being really interested. Then, I was recently offered a board as a advertising gift from a big computer company. I've been playing regularly with my friends since. What confused me at first was the lack of knowledge of any game principle, like fighting for the center, or avoiding the corners, etc. (The only other game I play is chess, where all base tactics and strategy are well-known). But I finally went past this situation and now I really enjoy it. Lots of questions come to me, though: 1) What are the general principles/tactics/opening moves of the game? 2) What is the standard notation for the games ? 3) Are there any Abalone federations/tournaments/e-mail games ? 4) Are there any board or playing programs available (commercially or by FTP) ? -- ------------------------------------------------------------------------------- Max FROUMENTIN (froument@lifl.fr) Laboratoire d'informatique fondamentale de Lille France ------------------------------------------------------------------------------- From torrance@ai.mit.edu Wed Apr 7 11:59:16 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["304" "Wed" "7" "April" "93" "11:59:40" "EDT" "Mark Torrance" "torrance@ai.mit.edu " nil "9" "Abalone board printer" "^From:" nil nil "4"]) Return-Path: Received: from life.ai.mit.edu by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA11712; Wed, 7 Apr 93 11:57:50 EDT Received: from oreo (oreo.ai.mit.edu) by life.ai.mit.edu (4.1/AI-4.10) id AA18184; Wed, 7 Apr 93 11:59:43 EDT Received: by oreo (4.1/AI-4.10) id AA26528; Wed, 7 Apr 93 11:59:40 EDT Message-Id: <9304071559.AA26528@oreo> From: torrance@ai.mit.edu (Mark Torrance) To: abalone@medg.lcs.mit.edu Subject: Abalone board printer Date: Wed, 7 Apr 93 11:59:40 EDT I've written a postscript program that produces nice pictures of Abalone boards. You can get the package from ftp.ai.mit.edu:/pub/psabalone.tar.Z . It supports showing partial boards, and putting a few bold sans-serif characters in each marble. Send me your comments or suggestions. --Mark Torrance From ant@ips.id.ethz.ch Thu Apr 8 02:40:29 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["772" "Thu" "08" "April" "93" "08:41:11" "+0200" "ant@ips.id.ethz.ch" "ant@ips.id.ethz.ch" "<9304080641.AA22407@sitter>" "23" "Some updates..." "^From:" nil nil "4"]) Return-Path: Received: from bernina.ethz.ch by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA13312; Thu, 8 Apr 93 02:39:40 EDT Received: from maggia-gw by bernina.ethz.ch with SMTP inbound id <15700-0@bernina.ethz.ch>; Thu, 8 Apr 1993 08:41:17 +0200 Message-Id: <9304080641.AA22407@sitter> Received: from maggia by sitter id AA22407; Thu, 8 Apr 93 08:41:12 +0200 From: ant@ips.id.ethz.ch To: abalone@medg.lcs.mit.edu Subject: Some updates... Date: Thu, 08 Apr 93 08:41:11 +0200 Good morning everybody: (believe me: it's morning here). The good news first: I've been working on compalone and it got faster (a lot). The bad news: it's currently in no state to be distributed. I'm getting a new job next week and should be able to work on it in the near future - meaning that I'll officially release it soon. Speaking of having a new job: my eMail address changes as well. Can somebody change it to ant@bernina.ethz.ch? This account will only be valid for a few more days. And last: has any of you seen the (relatively) new portable travel abalones? The ones with the little tunnels for the marbles? Or the kindergarten set? The huge one? As I've seen there are some new people in the list. Let's hope it will return to life again. Cheers - ant From peter@q2c.nl Thu Apr 8 05:08:30 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1141" "Thu" "08" "April" "93" "09:56:41" "+0200" "Peter Tax" "peter@q2c.nl " nil "28" "Ablone strategies" "^From:" nil nil "4"]) Return-Path: Received: from sun4nl.nluug.nl by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA13542; Thu, 8 Apr 93 05:06:43 EDT Received: from qcons by sun4nl.nluug.nl via EUnet id AA29342 (5.65b/CWI-3.3); Thu, 8 Apr 1993 11:08:39 +0200 Received: by q2c.nl (FernMail); Thu, 08 Apr 93 09:56:41 Organization: QC Consultancy Message-Id: X-Mailer: Fernmail 1.1 (unregistered, shareware fee not paid) From: peter@q2c.nl (Peter Tax) To: abalone@medg.lcs.mit.edu Subject: Ablone strategies Date: Thu, 08 Apr 93 09:56:41 +0200 Hello there, I'm new on this newsgroup. I found out about this newsgroup via the Random Game competition. I tried to compete in this competition, but this failed since the program I wrote was Macintosh program, and they could not run it. This was quite unsatisfactory; I still don't know how strong the program I wrote is compared to other programs. Is there anyone else in this group who made an Abalone program running on the Macintosh, or under a standard C environment? If so, I'd like to let our programs play against each other. Also, I guess there must have been going on some discussion about strategy in this newsgroup. Could someone update me on this subject? I found out some general criteria you can base a strategy upon: 1) distance from the edge 2) connectivity 3) the number of legal moves. (this probably can't be implemented efficiently) Are there any other agreed-upon general criteria for a stong Abalone playing strategy? --- peter@q2c.nl (Peter Tax) ? LOOK You are in a brighly lit room. There is a screen device in front of you. North and East are doors. There is a manager behind you. ? N The door is locked. ? _ From ant@ips.id.ethz.ch Thu Apr 8 09:39:16 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1868" "Thu" "08" "April" "93" "15:40:05" "+0200" "ant@ips.id.ethz.ch" "ant@ips.id.ethz.ch" nil "49" "Re: Ablone strategies " "^From:" nil nil "4"]) Return-Path: Received: from bernina.ethz.ch by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA13827; Thu, 8 Apr 93 09:38:29 EDT Received: from maggia-gw by bernina.ethz.ch with SMTP inbound id <1661-0@bernina.ethz.ch>; Thu, 8 Apr 1993 15:40:10 +0200 Message-Id: <9304081340.AA04507@sitter> Received: from maggia by sitter id AA04507; Thu, 8 Apr 93 15:40:06 +0200 In-Reply-To: Your message of "Thu, 08 Apr 93 09:56:41 +0100." From: ant@ips.id.ethz.ch To: abalone@medg.lcs.mit.edu Subject: Re: Ablone strategies Date: Thu, 08 Apr 93 15:40:05 +0200 >Is there anyone else in this group who made an Abalone program running >on the Macintosh, or under a standard C environment? If so, I'd like to >let our programs play against each other. I'll try to release compalone as soon as possible. >Also, I guess there must have been going on some discussion about >strategy in this newsgroup. Could someone update me on this subject? You're overestimating this list. Anyway, now you've started it. Problem: if you disclose everything about your prog and it contains a novel strategy then others will include it if your prog is better than theirs. Still it's good that we discuss it here. >I found out some general criteria you can base a strategy upon: >1) distance from the edge Yes, but. If you overstress this strategy programs tend to play boring. >2) connectivity Yes. Very important in my prog. >3) the number of legal moves. I took that out. Freedom does not seem to be a problem in abalone. >Are there any other agreed-upon general criteria for a stong Abalone >playing strategy? Well, I think you forgot the most obvious one: # of marbles still on the board (called area in Compalone). Actually the main parameter for success in abalone seems to be the choice of the algorithm. The prog from the MIT uses conspiracy search. To use this algo you have to build the search tree in mem. Kinda bad for PCs (and MACs) methinks. But search control (time and space) is a breeze. I still use dumb alpha-beta but I have a list of algos to try stashed somewhere. Unfortunately it's very hard to try to see the advantages of the different algos without running a great many tests (preferably automatic ones). If I see things correctly the main problem of people in this group is time. Seems that most of us got jobs somewhere (even in the university environement jobs seem to mean work sometimes). Cheers - ant From sean@susan.cs.andrews.edu Thu Apr 8 11:30:45 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["595" "Thu" "8" "April" "1993" "11:31:49" "-0400" "Sean Mattingly" "sean@susan.cs.andrews.edu " "<9304081531.AA27381@susan.cs.andrews.edu>" "15" "Newbie Question" "^From:" nil nil "4"]) Return-Path: Received: from susan.cs.andrews.edu by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA14038; Thu, 8 Apr 93 11:29:54 EDT Received: by susan.cs.andrews.edu (5.57/Ultrix3.0-C) id AA27381; Thu, 8 Apr 93 11:31:50 -0400 Message-Id: <9304081531.AA27381@susan.cs.andrews.edu> X-Mailer: ELM [version 2.4 PL21] Content-Type: text Content-Length: 595 From: sean@susan.cs.andrews.edu (Sean Mattingly) To: abalone@medg.lcs.mit.edu (abalone-list ) Subject: Newbie Question Date: Thu, 8 Apr 1993 11:31:49 -0400 (EDT) I'm one of the mentioned new people on the list, so please bear with any redundant questions. Does anybody out there know of a network abalone for UNIX/X? It doesn't have to be anything fancy....just something to let me play against other people. Also, is this mailing list essentially for discussion of abalone playing programs, or abalone in general? -- Sean Mattingly | "At least we can hope, what else do The Lone Republican | we need?" (Who was that masked man?) | _Mining the Oort_ sean@andrews.edu | by Frederik Pohl From mpf@medg.lcs.mit.edu Thu Apr 8 14:24:41 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["776" "Thu" "8" "April" "93" "14:25:35" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "18" "Re: Newbie Question" "^From:" nil nil "4"]) Return-Path: Received: from laennec (LAENNEC.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA14645; Thu, 8 Apr 93 14:24:02 EDT Received: by laennec (4.1/TOC-1.1C) id AA15936; Thu, 8 Apr 93 14:25:35 EDT Message-Id: <9304081825.AA15936@laennec> In-Reply-To: <9304081531.AA27381@susan.cs.andrews.edu> References: <9304081531.AA27381@susan.cs.andrews.edu> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: sean@susan.cs.andrews.edu (Sean Mattingly) Cc: abalone@medg.lcs.mit.edu (abalone-list ) Subject: Re: Newbie Question Date: Thu, 8 Apr 93 14:25:35 EDT sean@susan.cs.andrews.edu (Sean Mattingly) writes: > Does anybody out there know of a network abalone for UNIX/X? > It doesn't have to be anything fancy....just something to let me play > against other people. I don't know of any... for a while I was thinking of making one using the TclTcp package for Tcl and using Tk to do the graphics... It would be pretty easy. Maybe I'll still do it sometime. > Also, is this mailing list essentially for discussion of abalone playing > programs, or abalone in general? I would say that both are fine. -Mike , , __ mpf@medg.lcs.mit.edu /|/| . _ |_ _ _ | |_ _ _ ,_ |, Clinical Decision-Making Group / | | | (_ | | (_| (-' | | | (_| | | |\ MIT Lab for Computer Science From ninja@halcyon.halcyon.com Fri Apr 9 02:16:48 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1018" "Thu" "8" "April" "1993" "23:14:31" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "25" "Re: Ablone strategies" "^From:" nil nil "4"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA16123; Fri, 9 Apr 93 02:12:39 EDT Received: by halcyon.com id AA24293 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Thu, 8 Apr 1993 23:14:31 -0700 Message-Id: <199304090614.AA24293@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu, ant@ips.id.ethz.ch Subject: Re: Ablone strategies Date: Thu, 8 Apr 1993 23:14:31 -0700 I still hope to make an Abalone program with neural networks. I have some innovative ideas for teh neural net work, so I might make it my BS thesis for my CS major. :) I'll be doing a independant study this summer (Sort of a course creit, semi-overseen) in using Genetic Algorithms to evole optimal fleet configurations for teh game Phoenix. (PBEM game. Fleet combat is based on probability and statistics stuff.) Should be fun. :) Anyways, I just wanted to say I'm intereted in Abalone programming, and have the time, but not teh knowledge as of yet... I'd like to see a Abalone server soemtime, with optional hooks for computer players to be able to connect and play humans, or each other. :) F F Jonathan Roy, of the Free Access Foundation Email: ninja@faf.org A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F Vorlons, of the Galactic Bloodshed Development Team GEnie: J.ROY18 "Everything that has transpired has done so according to my design." - _RotJ_ From sean@edmund.cs.andrews.edu Fri Apr 9 10:06:15 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["592" "Fri" "9" "April" "1993" "10:06:28" "-0400" "Sean Mattingly" "sean@edmund.cs.andrews.edu " nil "18" "Re: Ablone strategies" "^From:" nil nil "4"]) Return-Path: Received: from edmund.cs.andrews.edu by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA16487; Fri, 9 Apr 93 10:04:33 EDT Received: by edmund.cs.andrews.edu (5.57/Ultrix3.0-C) id AA12744; Fri, 9 Apr 93 10:06:31 -0400 Message-Id: <9304091406.AA12744@edmund.cs.andrews.edu> In-Reply-To: <199304090614.AA24293@halcyon.com> from "Jonathan Roy" at Apr 8, 93 11:14:31 pm X-Mailer: ELM [version 2.4 PL21] Content-Type: text Content-Length: 592 From: sean@edmund.cs.andrews.edu (Sean Mattingly) To: abalone@medg.lcs.mit.edu (abalone-list ) Subject: Re: Ablone strategies Date: Fri, 9 Apr 1993 10:06:28 -0400 (EDT) > I'd like to see a Abalone server soemtime, with optional hooks > for computer players to be able to connect > and play humans, or each other. > That would be really cool. I really would like to get to play some people on the net and that would be a lot of fun. > :) > > F F Jonathan Roy, of the Free Access Foundation Email: ninja@faf.org -- Sean Mattingly | "At least we can hope, what else do The Lone Republican | we need?" (Who was that masked man?) | _Mining the Oort_ sean@andrews.edu | by Frederik Pohl From eadengle@watcgl.uwaterloo.ca Fri Apr 9 13:21:49 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["950" "Fri" "9" "April" "93" "13:21:55" "EDT" "\"Ed \\\"Cynwrig\\\" Dengler\"" "eadengle@watcgl.uwaterloo.ca" nil "21" "Abalone servers (was Re: Abalone strategies)" "^From:" nil nil "4"]) Return-Path: Received: from watcgl.uwaterloo.ca by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA16835; Fri, 9 Apr 93 13:20:22 EDT Received: by watcgl.uwaterloo.ca id ; Fri, 9 Apr 93 13:21:55 -0400 Message-Id: <9304091721.AA28682@watcgl.uwaterloo.ca> X-Mailer: ELM [version 2.3 PL11] From: "Ed \"Cynwrig\" Dengler" To: abalone@medg.lcs.mit.edu Subject: Abalone servers (was Re: Abalone strategies) Date: Fri, 9 Apr 93 13:21:55 EDT Greetings! I ran an Abalone tournament at the University of Waterloo recently. In order to make life easier for the people actually entering moves, I developed a single slot game server (ie. only one game could be played at a time, but the server would live from game to game). The server provided a valid move checker and a game recorder. In addition, the rules of Abalone were slightly modified to make computer versions more interesting. I added the restrictions that no board could repeat, and that each player only had 200 moves (surprisingly enough, no game in the tournament used up all 400 moves, every game was won by pushing off 6 marbles). The server also implemented these two restrictions. If people are interested, I could post the server onto the list. The code is fairly readable (standard client/server model using tcp Internet sockets) and should not be much of a problem for people to make clients that can use the server. Ed From mikula@ugcs.caltech.edu Fri Apr 9 14:20:40 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["747" "Fri" "9" "April" "1993" "11:25:42" "-0800" "Alf Mikula" "mikula@ugcs.caltech.edu " nil "18" "Abalone servers" "^From:" nil nil "4"]) Return-Path: Received: from through.ugcs.caltech.edu by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA17003; Fri, 9 Apr 93 14:19:50 EDT Received: from grate.ugcs.caltech.edu by through.ugcs.caltech.edu with SMTP (16.6/UGCS:4.42) id AA12578; Fri, 9 Apr 93 11:25:50 -0700 Received: by grate.ugcs.caltech.edu (16.6/UGCS:4.42) id AA03925; Fri, 9 Apr 93 11:25:47 -0700 Message-Id: <9304091825.AA03925@grate.ugcs.caltech.edu> X-Mailer: ELM [version 2.4 PL0] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Length: 747 From: mikula@ugcs.caltech.edu (Alf Mikula) To: abalone@medg.lcs.mit.edu Subject: Abalone servers Date: Fri, 9 Apr 1993 11:25:42 -0800 (PDT) A few months ago, while I was still in the AMBITIOUS state, I tried to get a local group to program a game server in C++ that was modular enough to support any number of games. Unfortunately, and I might add predictably, the project never got off the ground, but I plan to try again this summer. Abalone was to be our first game. Anyway, I'd love to see an abalone server, since there's no one left to play around here... ---------------------------------------------------------------------- God, grant me the serenity To accept the things I cannot change, Courage to change the things I can, And wisdom to know the difference. -The Serenity Prayer From mpf@medg.lcs.mit.edu Thu Apr 15 23:36:39 1993 Status: RO X-VM-v5-Data: ([nil nil nil t nil nil nil nil nil] [nil nil nil nil nil nil nil nil nil nil nil nil "^From:" nil nil nil]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA29644; Thu, 15 Apr 93 23:35:46 EDT Received: by luke (4.1/TOC-1.1C) id AA27926; Thu, 15 Apr 93 23:38:47 EDT Message-Id: <9304160338.AA27926@luke> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: abalone mailing list archive available Date: Thu, 15 Apr 93 23:38:47 EDT There is now an archive of the abalone mailing list available for anonymous FTP at medg.lcs.mit.edu, in pub/abalone/abalone-archive.mail. It is updated continually. It's a regular UNIX mail file. If you happen to have the "Alex" NFS interface to FTP, you can browse the archives simply by running your favorite mail reader on the file: /alex/edu/mit/lcs/medg/pub/abalone/abalone-archive.mail (For more information about Alex, look in pub/alex/ on medg.) -Mike , , __ mpf@medg.lcs.mit.edu /|/| . _ |_ _ _ | |_ _ _ ,_ |, Clinical Decision-Making Group / | | | (_ | | (_| (-' | | | (_| | | |\ MIT Lab for Computer Science From ninja@halcyon.halcyon.com Fri Apr 16 09:02:23 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["121" "Fri" "16" "April" "1993" "06:03:31" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "3" "Re: abalone mailing list archive available" "^From:" nil nil "4"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA00397; Fri, 16 Apr 93 09:01:09 EDT Received: by halcyon.com id AA29342 (5.65c/IDA-1.4.4 for mpf@medg.lcs.mit.edu); Fri, 16 Apr 1993 06:03:31 -0700 Message-Id: <199304161303.AA29342@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu, mpf@medg.lcs.mit.edu Subject: Re: abalone mailing list archive available Date: Fri, 16 Apr 1993 06:03:31 -0700 I have a semi-archive of old posts I can send to you if you'd like it. (If you don't have any older archives yourself.) From ulim@coli.uni-sb.de Sun Apr 18 06:39:28 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["3019" "Sun" "18" "April" "93" "12:38:03" "MET" "Ulrich Mayring" "ulim@coli.uni-sb.de " "<9304181038.AA26139@coli-gate.coli.uni-sb.de>" "61" "Abalone Implementation" "^From:" nil nil "4"]) Return-Path: Received: from iraun1.ira.uka.de by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA04458; Sun, 18 Apr 93 06:38:27 EDT Received: from sbusol.rz.uni-sb.de by iraun1.ira.uka.de with SMTP (PP) id <07457-0@iraun1.ira.uka.de>; Sun, 18 Apr 1993 12:40:35 +0200 Received: from coli-gate.coli.uni-sb.de by sbusol.rz.uni-sb.de (5.65+/v1.0) id AA13903; Sun, 18 Apr 93 12:40:45 +0200 Received: by coli-gate.coli.uni-sb.de (4.1/SMI-4.1/CL930118) id AA26139; Sun, 18 Apr 93 12:38:07 +0200 Message-Id: <9304181038.AA26139@coli-gate.coli.uni-sb.de> X-Mailer: ELM [version 2.3 PL11] From: ulim@coli.uni-sb.de (Ulrich Mayring) To: abalone@medg.lcs.mit.edu Subject: Abalone Implementation Date: Sun, 18 Apr 93 12:38:03 MET DST Hello whoever you are, I have been told this address is one, where I could get onto an Aabalone mailing list and talk to some other Abalone enthusiasts. Please forgive me if you are not the right person to talk to, maybe you could then forward this letter provided you know whereto. You may be interested in the following (prepared and thus unpersonal) text: Well, here's the story on how far we got with implementing Abalone. I bought the game, liked it and told my friends about it. One of them, a fairly expert Pascal coder immediately set his heart towards a computer implementation. He got pretty far by now, however, the program is still in a somewhat un- functional state. Features included are: Can be run as a PBM-game, which we will at least try to get launched, since it keeps a very interesting hall of fame of all players, which is updated after every move of either of the players. Many parameters are included for intro- ducing alternative rules, since standard Abalone seems to run about 200 moves a game, which would make it somehow lengthy for a PBM-game. Some of the parameters, which can be changed to produce different sets of rules, are: -Number of players (two or three per board) -Board size (It will, however, always be a hexagon) -Number of pieces at start of game -Number of pieces you need to throw out in order to win the game. -Length of chains (in standard Abalone you cannot move more than 3 pieces in a row and a chain of 3 pieces is always secure. Here we can change that number to 4, 5 or more, or even down to 2.) The game can also be run as an automaton you can play against. This is what we currently are working on. We implemented a Minimax algorithm with Alpha- Beta Pruning and did some routines in assembler, so right now search depth 3 has a time penalty of 20 seconds. This can be further optimized once we have a reasonable board analysis, but we still struggle on some of the parameters It is not easy at all to come up with a set of useful parameters that really tell if the game situation is 'good' or 'bad' for the player. The automaton is already playing very well, even at search depth 1, where it instantly moves. Once we get the parameters sorted out, we expect depth 3, which already beats depth 1, to be strong enough to beat us sometimes. Games are saved in DBaseIII format, so you can look at them with DBase and easily build up a large library of games. We also made a viewer, which takes any game in DBaseIII format and lets you toggle moves forward and backwards with the cursor keys. The board for the viewer and the automaton is shown in a pretty VGA-graphic and moves can be entered with the mouse. If there are any Abalones out there, which are free to look at or at least for a reasonable price, we would very much like to look into them and eventually match our automaton against them. (BTW: Copyright issues are still unresolved, we'd be interested in any info we could get on that, too) Ulrich Mayring EMail: ulim@coli.uni-sb.de From peter@q2c.nl Mon Apr 19 04:09:39 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["3742" "Fri" "16" "April" "93" "15:32:04" "+0200" "Peter Tax" "peter@q2c.nl " nil "87" "Re: subscribe" "^From:" nil nil "4"]) Return-Path: Received: from sun4nl.nluug.nl by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA05336; Mon, 19 Apr 93 04:08:40 EDT Received: from qcons by sun4nl.nluug.nl via EUnet id AA26277 (5.65b/CWI-3.3); Mon, 19 Apr 1993 10:11:13 +0200 Received: by q2c.nl (FernMail); Fri, 16 Apr 93 15:32:04 Organization: QC Consultancy Message-Id: X-Mailer: Fernmail 1.1 (unregistered, shareware fee not paid) From: peter@q2c.nl (Peter Tax) To: abalone@medg.lcs.mit.edu Subject: Re: subscribe Date: Fri, 16 Apr 93 15:32:04 +0200 > A friend of mine who does not have Internet access has programmed > a game playing program using alpha-beta pruning of the game tree > and is interested in contacting others who have done similar things. Hello Kevin, I made an Abalone-playing program for the Macintosh myself, and I use alpha-beta pruning as well. I started using a minimax strategy (same without pruning), but found out it is hardly possible to go three plies deep this way. Several people (among them Ed Dengler, also in this list) pointed out I should use alpha-beta pruning instead, and this really helped. Using a simple (but fast) board evaluation function, the program can go three plies deep and still perform acceptably on a Mac. I don't know exactly what your friend wants to know or see; if it's source code, my program as a whole is very Mac-specific, but the strategy part of it is more or less plain C. But since your friend already made a program himself, he is most likely more interested in a general description of some possible strategies, so he can incorporate them in his program. Ed Dengler recently organised a contest for Abalone-playing programs, and there were (I think) 5 entries other than mine, so it should be possible to get some general ideas for strategies via him. (Ed, if you read this, I did not receive the descriptions of the other programs, so I don't know if you posted them. If you did, kmc@netcom.com would be interested in them, and so would I) In my program, I implemented a few very similar strategies. The strategies are all based on positional value, sometimes combined with connectivity. A reasonably strong, but still very simple board evaluation function is: board_value = 0 for all fields, do: if the current player has a ball on it board_value += 1024 board_value -= positional_value (field) for all six direct neighbours do if this player also has a ball on this neighbour field board_value += 32 else if a different player has a ball on it: same computation, but with the signs reversed return board_value The interesting thing here is obviously the positional value assigned to the field. For this, I use the following function (the values should be stored in a table for efficiency, of course): postional_value (field) pos_value = 0 in all six directions do dist = distance from the edge in this direction pos_value += 1 << (10 - dist) return pos_value / 6 You can use many variations on the positional value/connectivity theme, of course, but this is a good starter. Alternative, but definately weaker strategies, I already tried are: - use the minimal distance from the edge in postional_value instead of the weighted average - don't use connectivity at all - don't use positional value at all - use a lineair relation between positional value and edge-distance Improvements are possible by using a more subtle connectivity measure (field/direction-dependant). I have one strategy that is slightly better than the simple one described here. I'd be interested to hear from your friend; if he comes up with some nice ideas, I'd like to hear abour them, and maybe add them as new strategies to my program (if he doesn't mind, of course). Also, I'd be interested in completely different approaches. By the way, if your friend has (access to a) Mac, you can download my program from the most important Mac archives (mac.archive.umich.edu, sumex-aim.stanford.edu) or mirroring sites. Peter Tax (peter@q2c.nl, a512hjal@diamond.sara.nl) --- peter@q2c.nl (Peter Tax) ? LOOK You are in a brighly lit room. There is a screen device in front of you. North and East are doors. There is a manager behind you. ? N The door is locked. ? _ From kmc@netcom.com Fri Apr 23 16:27:09 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2083" "Fri" "23" "April" "93" "13:24:04" "PDT" "Kevin McCarty" "kmc@netcom.com " nil "51" "Re: alpha-beta" "^From:" nil nil "4"]) Return-Path: Received: from netcom4.netcom.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA17356; Fri, 23 Apr 93 16:21:14 EDT Received: by netcom4.netcom.com (5.65/SMI-4.1/Netcom) id AA28491; Fri, 23 Apr 93 13:24:05 -0700 Message-Id: <9304232024.AA28491@netcom4.netcom.com> In-Reply-To: ; from "Peter Tax" at Apr 16, 93 3:32 pm X-Mailer: ELM [version 2.3 PL11] From: kmc@netcom.com (Kevin McCarty) To: peter@q2c.nl (Peter Tax) Cc: abalone@medg.lcs.mit.edu Subject: Re: alpha-beta Date: Fri, 23 Apr 93 13:24:04 PDT In reply to Peter Tax, my friend Mark Perkins replies: Hello Peter, I am glad to hear from another Abalone programmer. I am also anxious to try out your board evaluation function in comparison to my (simpler) function. The board evaluation function which I am currently using is even simpler than yours in that it does not consider connectivity at all. The position values I use are: 10 12 15 12 10 12 40 45 45 40 12 15 45 60 65 60 45 15 12 45 65 80 80 65 45 12 10 40 60 80 100 80 60 40 10 etc. board_value = 0 for all fields, do: if the current player has a ball on it board_value += 200 + positional_value (field) else if a different player has a ball on it: same computation, but with the signs reversed return (board_value - 2800); This seems to give reasonable behavior (at least against my meager abilities), although it can be overly defensive at times. I have never played my program against another program, but I have played against it quite a bit myself. Recently, I set it up my program so that it would take as input an actual game and provide as output (1) the minimax value of the actual player's move, (2) the minimax value of the computer's best move, and (3), the computer's best move. I have then been running this on the games recorded as part of the "Waterloo Arbitrary Game Competition". I can then look at the results to see, for example, how much other programs agree with mine, or in what kind of situations there is strong disagreement. Looking down 5 levels, it takes an average of about 1 minute per move per player to generate the output I described above (on a Dell 486P/50 PC running DOS). In the not-to-distant future, I hope to implement your board evaluation function in a version of my program so I can try it out against mine. If and when I complete that task, I'll let you know how it turns out. Mark Perkins -- Kevin McCarty (kmc@netcom.com) From kmc@netcom.com Fri Apr 23 16:28:48 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["3529" "Fri" "23" "April" "93" "13:30:27" "PDT" "Kevin McCarty" "kmc@netcom.com " nil "69" "position evaluation" "^From:" nil nil "4"]) Return-Path: Received: from netcom4.netcom.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA17380; Fri, 23 Apr 93 16:27:26 EDT Received: by netcom4.netcom.com (5.65/SMI-4.1/Netcom) id AA28900; Fri, 23 Apr 93 13:30:28 -0700 Message-Id: <9304232030.AA28900@netcom4.netcom.com> X-Mailer: ELM [version 2.3 PL11] From: kmc@netcom.com (Kevin McCarty) To: abalone@medg.lcs.mit.edu (Abalone Mailing List) Subject: position evaluation Date: Fri, 23 Apr 93 13:30:27 PDT Let me add some to Mark's reply. He and I have had discussions in the past about the general strategy of game tree search for games like Abalone. I would be interested in provoking a general discussion of this topic. Game tree search, aided by alpha-beta pruning, assumes the validity and relevance of the evaluation function used at the leaves of the search tree. The fact that you can look deep into the game tree and evaluate the strength of positions there gives advantage over evaluating the strength of the current position only in two cases: 1) The depth of lookahead allows you to discover a forced win, or avoid a fatal blunder (a forced win by your opponent). 2) The positional strength-- as evaluated by your function-- of the position at the end of the principal continuation is significantly different from that of the current situation. At one extreme, if we had position evaluation functions that were sophisticated enough, we wouldn't need to look very far ahead. In other words, the value of lookahead as in 1) would be subsumed by the evaluation in 2). The downside is that sufficiently smart evaluation functions would be very expensive to compute. At the other extreme, if we could look far enough ahead in the game tree, we wouldn't need very sophisticated position evaluation functions. If you look ahead far enough, the only evaluation function you ever need is "did someone win yet?" In other words, being in a strong position is in the end irrelevant; the only thing that matters is whether you win or not. The meaning of 2) is ultimately completely subsumed in 1); the ultimate position evaluation function returns the result: "this position guarantees a win/loss". So, as a practical matter, searching a game tree always involves a tradeoff between depth of search you can afford to make and cost of computing a position evaluation at the leaves. Cost of computing a position evaluation is proportional to how realistically the position evaluation takes account of what's most important for a truly strong position. If you dumb down your position evaluation function (or if you're not sure what it takes to make a smart one), you can afford to search deeper in the tree. But if you can't search deep enough to see wins or losses, significant positional gains detected as in 2) above may be completely delusional. Conversely, if you could tell just by looking what makes a position strong, you wouldn't need to search so deep. Thus it is interesting to see what elements various people think to include in position evaluation. One can differentiate three categories of elements (in increasing order of computation expense): material, position (e.g. distance from edge), and configuration. Question: what elements of configuration (e.g. connectivity, shape) are signficant for Abalone, and how can they be cheaply computed? One way to do a scientific investigation of this effect is to look at how the evaluation of a given position and its possible moves changes as the depth of search is increased. An evaluation function is "good" to the degree to which it can succesfully predict the result of searching the game tree further. It is "bad" or misleading to the extent that the identification of the principal continuation fluctuates significantly as the search depth increases. (Note however that this may sometimes just be due to the fact that some positions contain critical possibilities and pitfalls for the two players.) -- Kevin McCarty (kmc@netcom.com) From mpf@medg.lcs.mit.edu Fri Apr 23 16:46:11 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1345" "Fri" "23" "April" "93" "16:47:43" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "28" "my abalone evaluation function" "^From:" nil nil "4"]) Return-Path: Received: from laennec (LAENNEC.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA17440; Fri, 23 Apr 93 16:45:22 EDT Received: by laennec (4.1/TOC-1.1C) id AA03558; Fri, 23 Apr 93 16:47:43 EDT Message-Id: <9304232047.AA03558@laennec> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: my abalone evaluation function Date: Fri, 23 Apr 93 16:47:43 EDT Since everyone seems to be talking about board evaluation functions, I might as well throw mine out there... For each pair of one of A's marbles and one of B's marbles, I measure the length of the line segment from A *through B* to a wall. I add up this length for all the pairs. The total measures how far player A is from having B backed up against a wall. The negative of this quantity measures how close A is to having B backed up against a wall. Then you do this the other way around (measure the lengths from B's marbles through A's marbles to a wall) and then find the difference between the two totals. This measures how much better A's position is compared to B's. One nice thing about this quantity is that if the enemy backs up some of your marbles against an edge, and there's no way for you to immediately move away from the edge, this measure will make you kind of squirt out sideways, because, although you aren't any farther from the edge, you are farther from being pushed off the edge by the enemy, if you see what I mean. Currently I only use this positional quantity to distinguish between states having the same number of marbles; so my program will sacrifice any quality of position in order to push off an enemy. This is actually a pretty bad strategy; the positional quantity should have a larger weight. -Mike From ant@bernina.ethz.ch Mon Apr 26 05:19:06 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["970" "Mon" "26" "April" "93" "11:20:56" "+0200" "ant@bernina.ethz.ch" "ant@bernina.ethz.ch" "<9304260918.AA19971@MEDG.lcs.mit.edu>" "19" "Re: alpha-beta " "^From:" nil nil "4"]) Return-Path: Received: from bernina.ethz.ch by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA19971; Mon, 26 Apr 93 05:18:10 EDT Message-Id: <9304260918.AA19971@MEDG.lcs.mit.edu> Received: from localhost by bernina.ethz.ch with SMTP inbound id <7404-0@bernina.ethz.ch>; Mon, 26 Apr 1993 11:20:59 +0200 In-Reply-To: Your message of "Fri, 23 Apr 93 13:24:04 PDT." <9304232024.AA28491@netcom4.netcom.com> From: ant@bernina.ethz.ch To: abalone@medg.lcs.mit.edu Subject: Re: alpha-beta Date: Mon, 26 Apr 93 11:20:56 +0200 >This seems to give reasonable behavior (at least against my meager >abilities), although it can be overly defensive at times. I have I think that for game trees the size of abalone ones an evaluation function based on more information should be used. The fact that (some) abalone programs play overly defensive is in my opinion due to a game design flaw; I should not be possible for a player to be able to block all progress. Although I have never seen a proof of this assumption it still looks intuitively true (no good reason, I know). I think that simple AlphaBeta is not ideal for abalone due to the large branching factor of the game-trees. The MIT program for example won easily with conspiracy number search against an earlier version of compalone although it seemed to have the a worse static evaluation (both using AlphaBeta, my program won). I therefore think that real success in Abalone playing progs involves some algorithm ``research''. Cheers - ant From mpf@medg.lcs.mit.edu Mon Apr 26 13:18:58 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2450" "Mon" "26" "April" "93" "13:21:29" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "50" "Re: my abalone evaluation function" "^From:" nil nil "4"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA20666; Mon, 26 Apr 93 13:17:51 EDT Received: by luke (4.1/TOC-1.1C) id AA13916; Mon, 26 Apr 93 13:21:29 EDT Message-Id: <9304261721.AA13916@luke> In-Reply-To: <9304260723.AA05684@coli-gate.coli.uni-sb.de> References: <9304232047.AA03558@laennec> <9304260723.AA05684@coli-gate.coli.uni-sb.de> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: ulim@coli.uni-sb.de (Ulrich Mayring) Cc: abalone Subject: Re: my abalone evaluation function Date: Mon, 26 Apr 93 13:21:29 EDT ulim@coli.uni-sb.de (Ulrich Mayring) writes: > Well, let's see if I got this one right: Your evaluation function does in > fact like it when you push your opponent against the edge of the board, > but it doesn't distinguish if you do that with an equal number of > marbles, a lesser or a greater one? So, in fact you would score high, when > you pushed three marbles of your opponent against the edge, while only > having two to do the job? Yeah, it's true that having 2 marbles hovering over 3 enemy marbles that are against the edge gives you about the same static score as having 2 marbles hovering over 3, all else being equal. But I think that's ok; it's good to have lots of enemy marbles against the edge; it means fewer in his main body. Even if we don't have enough force to push them off right away, having more of them there decreases the chances that they'll all be able to escape before we can bring in more marbles to push them off. > I should think you would need some kind of sumito-evaluator, or do > these discrepancies even out over the long run/tree? Or does your > function work like this: When you have three marbles against two you > measure the distance three times for your side and only two times > for your opponent's side, thus giving you a better score. No, your earlier interpretation was correct. > Still, from my experience of gaming (not a lot, actually) I think > that a sumito-position in the early game, when the two > marble-structures are still relatively intact, is much more > important than any evaluation function I can think of is capable to > compute. The thing about checking for sumito opportunities in the evaluation function is that it's basically like trying to stuff one extra level of search into the positional evaluator. It seemed to me like it would be better to make the evaluator fast and simple and truly positional, and do the look-ahead for good moves in the search routine, where it belongs. You should try it out---it's amazingly good for its simplicity. The main deficiencies in our program's play seem to be due to the fact that it weighs pushing off enemy marbles so much more than positional strength. But this would be easy enough to adjust. By the way, another advantage of this evaluation function is that's it's easy to change it incrementally as we explore the game tree---so we don't have to compute it from scratch on every position. > Greetings, Ulrich -Mike From mpf@medg.lcs.mit.edu Mon Apr 26 13:30:54 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1162" "Mon" "26" "April" "93" "13:33:17" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "24" "Re: alpha-beta " "^From:" nil nil "4"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA20700; Mon, 26 Apr 93 13:29:38 EDT Received: by luke (4.1/TOC-1.1C) id AA13944; Mon, 26 Apr 93 13:33:17 EDT Message-Id: <9304261733.AA13944@luke> In-Reply-To: <9304260918.AA19971@MEDG.lcs.mit.edu> References: <9304232024.AA28491@netcom4.netcom.com> <9304260918.AA19971@MEDG.lcs.mit.edu> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: abalone Subject: Re: alpha-beta Date: Mon, 26 Apr 93 13:33:17 EDT ant@bernina.ethz.ch writes: > I think that simple AlphaBeta is not ideal for abalone due to the large > branching factor of the game-trees. The MIT program for example won > easily with conspiracy number search against an earlier version of > compalone although it seemed to have the a worse static evaluation (both > using AlphaBeta, my program won). I therefore think that real success in > Abalone playing progs involves some algorithm ``research''. Speaking of advanced search strategies, there is a very interesting paper by two guys at NEC that describes a new algorithm for game-tree search. It uses probability distributions instead of single numbers to evaluate nodes, and it expands the tree in those places that have the highest expected utility. It's very elegant. You can FTP it at external.nj.nec.com, file /pub/eric/game.ps.Z. > Cheers > - ant , , __ mpf@medg.lcs.mit.edu /|/| . _ |_ _ _ | |_ _ _ ,_ |, Clinical Decision-Making Group / | | | (_ | | (_| (-' | | | (_| | | |\ MIT Lab for Computer Science 545 Technology Sq. rm. 421, Cambridge, MA 02139. (617) 253-2351 (fax -5060) From ninja@halcyon.halcyon.com Mon Apr 26 19:38:31 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["424" "Mon" "26" "April" "1993" "16:38:56" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" nil "8" "Re: alpha-beta" "^From:" nil nil "4"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA21526; Mon, 26 Apr 93 19:37:30 EDT Received: by halcyon.com id AA27034 (5.65c/IDA-1.4.4 for abalone@medg.lcs.mit.edu); Mon, 26 Apr 1993 16:38:56 -0700 Message-Id: <199304262338.AA27034@halcyon.com> From: Jonathan Roy To: abalone@medg.lcs.mit.edu, ant@bernina.ethz.ch Subject: Re: alpha-beta Date: Mon, 26 Apr 1993 16:38:56 -0700 Where can I get info on conspiracy theory? I'll be trying some sort of neural network approach myself. :) F F Jonathan Roy, of the Free Access Foundation Email: ninja@faf.org A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F Vorlons, of the Galactic Bloodshed Development Team GEnie: J.ROY18 "Everything that has transpired has done so according to my design." - _RotJ_ From peter@q2c.nl Tue Apr 27 05:34:40 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2321" "Tue" "27" "April" "93" "11:04:52" "+0200" "Peter Tax" "peter@q2c.nl " nil "69" "" "^From:" nil nil "4"]) Return-Path: Received: from sun4nl.nluug.nl by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA22082; Tue, 27 Apr 93 05:33:55 EDT Received: from qcons by sun4nl.nluug.nl via EUnet id AA07298 (5.65b/CWI-3.3); Tue, 27 Apr 1993 11:36:48 +0200 Received: by q2c.nl (FernMail); Tue, 27 Apr 93 11:04:52 Organization: QC Consultancy Message-Id: X-Mailer: Fernmail 1.1 (unregistered, shareware fee not paid) From: peter@q2c.nl (Peter Tax) To: kmc@netcom.com Cc: abalone@medg.lcs.mit.edu Subject: Date: Tue, 27 Apr 93 11:04:52 +0200 Hello Mark@Kevin, > The board evaluation function which I am currently using is even simpler > than yours in that it does not consider connectivity at all. The > position values I use are: 10 12 15 12 10 12 40 45 45 40 12 15 45 60 65 60 45 15 12 45 65 80 80 65 45 12 10 40 60 80 100 80 60 40 10 etc. I think this evaluation function sprouts from the same general idea every programmer trying a positional evaluation function should come up with; at least, it looks pretty familiar to me. Did you start with something like 10 10 10 10 10 10 20 20 20 20 10 10 20 30 30 30 20 10 10 20 30 40 40 30 20 10 10 20 30 40 50 40 30 20 10 etc. too? That's what I did; I then tried correcting going from worst-direction only to some average giving positional values similar to yours. I then convinced myself the danger in a direction decreases exponentially with the distance from the edge, giving the positional values in the function I described to you. I tried it, and it does play stronger than the (almost) lineair positinal values I used before. Giving the program you have, it should not be difficult to implement this; just a matter of stuffing some other values in the positional values. > Looking down 5 levels, it takes an average of about 1 > minute per move per player to generate the output I described above > (on a Dell 486P/50 PC running DOS). Seems like you're an efficient programmer, and the Dell is a fast machine. More than three levels is way too slow on my Mac, in a minute, I can look about 4 plies deep. > In the not-to-distant future, I hope to implement your board evaluation > function in a version of my program so I can try it out against mine. If > and when I complete that task, I'll let you know how it turns out. I'm looking forward to our small contest. --- peter@q2c.nl (Peter Tax) ? LOOK You are in a brighly lit room. There is a screen device in front of you. North and East are doors. There is a manager behind you. ? N The door is locked. ? _ From peter@q2c.nl Wed Apr 28 11:55:46 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1244" "Wed" "28" "April" "93" "16:17:27" "+0200" "Peter Tax" "peter@q2c.nl " nil "31" "Re: alpha-beta " "^From:" nil nil "4"]) Return-Path: Received: from sun4nl.nluug.nl by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA25997; Wed, 28 Apr 93 11:53:34 EDT Received: from qcons by sun4nl.nluug.nl via EUnet id AA14229 (5.65b/CWI-3.3); Wed, 28 Apr 1993 17:56:38 +0200 Received: by q2c.nl (FernMail); Wed, 28 Apr 93 16:17:27 Message-Id: X-Mailer: Fernmail 1.1 (unregistered, shareware fee not paid) From: peter@q2c.nl (Peter Tax) To: abalone@medg.lcs.mit.edu Subject: Re: alpha-beta Date: Wed, 28 Apr 93 16:17:27 +0200 Hello, >>This seems to give reasonable behavior (at least against my meager >>abilities), although it can be overly defensive at times. I have In an earlier reply about this, ant wrote: >I think that for game trees the size of abalone ones an evaluation >function based on more information should be used. The fact that (some) >abalone programs play overly defensive is in my opinion due to a game >design flaw; I should not be possible for a player to be able to block >all progress. Although I have never seen a proof of this assumption it >still looks intuitively true (no good reason, I know). I think it is theoretically impossible to block ALL progress. To do this, you'd need a block of marbles that is three deep in all directions, so that would at least be a hexagonal block with sides of length three. That's 3 + 4 + 5 + 4 + 3 > 14 marbles, so you can't. In practice, I must agree an overly defensive strategy gets boring. I do believe, however, a positional strategy is not necessarily boring. This depends on the values you choose. --- peter@q2c.nl (Peter Tax) ? LOOK You are in a brighly lit room. There is a screen device in front of you. North and East are doors. There is a manager behind you. ? N The door is locked. ? _ From ulim@coli.uni-sb.de Wed Apr 28 15:49:05 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["784" "Wed" "28" "April" "93" "21:47:20" "MET" "Ulrich Mayring" "ulim@coli.uni-sb.de " nil "22" "Alpha-Beta abolished" "^From:" nil nil "4"]) Return-Path: Received: from iraun1.ira.uka.de by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA26802; Wed, 28 Apr 93 15:47:20 EDT Received: from sbusol.rz.uni-sb.de by iraun1.ira.uka.de with SMTP (PP) id <03144-0@iraun1.ira.uka.de>; Wed, 28 Apr 1993 21:50:08 +0200 Received: from coli-gate.coli.uni-sb.de by sbusol.rz.uni-sb.de (5.65+/v1.0) id AA08912; Wed, 28 Apr 93 21:50:01 +0200 Received: by coli-gate.coli.uni-sb.de (4.1/SMI-4.1/CL930118) id AA17169; Wed, 28 Apr 93 21:47:23 +0200 Message-Id: <9304281947.AA17169@coli-gate.coli.uni-sb.de> X-Mailer: ELM [version 2.3 PL11] From: ulim@coli.uni-sb.de (Ulrich Mayring) To: abalone@medg.lcs.mit.edu Subject: Alpha-Beta abolished Date: Wed, 28 Apr 93 21:47:20 MET DST Hi folks What do you think of the following (theoretical and impractical) idea: Abolish Alpha-Beta Pruning and instead store the complete tree for depth n in RAM or on disk somewhere. Once the computation for depth n is carried out the best move according to Minimax is carried out. The next n/2-1 moves can be carried out without any kind of computation, since you only have to look in the stored proof tree. Now, if you made your program compute a tree of depth 150 (impossible, I know), you would be able to play a whole game without any delay waiting for the computer's moves :-) Anyways, the question I ask myself: Is there any depth of the search-tree, where this strategy is time-efficient, enough RAM being available for the sake of the argument. Joking (?!?), Ulrich. From ulim@coli.uni-sb.de Wed Apr 28 15:56:33 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["3315" "Wed" "28" "April" "93" "21:55:14" "MET" "Ulrich Mayring" "ulim@coli.uni-sb.de " "<9304281955.AA17219@coli-gate.coli.uni-sb.de>" "63" "Re: my abalone evaluation function" "^From:" nil nil "4"]) Return-Path: Received: from iraun1.ira.uka.de by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA26824; Wed, 28 Apr 93 15:54:58 EDT Received: from sbusol.rz.uni-sb.de by iraun1.ira.uka.de with SMTP (PP) id <03260-0@iraun1.ira.uka.de>; Wed, 28 Apr 1993 21:57:55 +0200 Received: from coli-gate.coli.uni-sb.de by sbusol.rz.uni-sb.de (5.65+/v1.0) id AA09246; Wed, 28 Apr 93 21:57:52 +0200 Received: by coli-gate.coli.uni-sb.de (4.1/SMI-4.1/CL930118) id AA17219; Wed, 28 Apr 93 21:55:15 +0200 Message-Id: <9304281955.AA17219@coli-gate.coli.uni-sb.de> In-Reply-To: <9304261721.AA13916@luke>; from "Michael P. Frank" at Apr 26, 93 1:21 pm X-Mailer: ELM [version 2.3 PL11] From: ulim@coli.uni-sb.de (Ulrich Mayring) To: abalone@medg.lcs.mit.edu Subject: Re: my abalone evaluation function Date: Wed, 28 Apr 93 21:55:14 MET DST >From a private conversation with Mike Frank about his evaluation strategy: > > ulim@coli.uni-sb.de (Ulrich Mayring) writes: > > Well, let's see if I got this one right: Your evaluation function does in > > fact like it when you push your opponent against the edge of the board, > > but it doesn't distinguish if you do that with an equal number of > > marbles, a lesser or a greater one? So, in fact you would score high, when > > you pushed three marbles of your opponent against the edge, while only > > having two to do the job? > > Yeah, it's true that having 2 marbles hovering over 3 enemy marbles > that are against the edge gives you about the same static score as > having 2 marbles hovering over 3, all else being equal. But I think > that's ok; it's good to have lots of enemy marbles against the edge; > it means fewer in his main body. Even if we don't have enough force > to push them off right away, having more of them there decreases the > chances that they'll all be able to escape before we can bring in more > marbles to push them off. > > > I should think you would need some kind of sumito-evaluator, or do > > these discrepancies even out over the long run/tree? Or does your > > function work like this: When you have three marbles against two you > > measure the distance three times for your side and only two times > > for your opponent's side, thus giving you a better score. > > No, your earlier interpretation was correct. > > > Still, from my experience of gaming (not a lot, actually) I think > > that a sumito-position in the early game, when the two > > marble-structures are still relatively intact, is much more > > important than any evaluation function I can think of is capable to > > compute. > > The thing about checking for sumito opportunities in the evaluation > function is that it's basically like trying to stuff one extra level > of search into the positional evaluator. It seemed to me like it > would be better to make the evaluator fast and simple and truly > positional, and do the look-ahead for good moves in the search > routine, where it belongs. Well, what you are saying is, that if we already implemented a nice Minimax strategy, why not use it? This is a valid statement, but do you know how many plies commercial chess evaluators search? Methinks at most 7 (correct me here), so search depth doesn't appear to be the one-all of board evaluation. Also, with your search strategy you may not find a good sumito position, because it means giving up a center position. But if the two marble-structures meet in the middle of the board, the one, who wants to attack must make a sumito move AWAY from the center. If he will not do that, because of positional value, he may well be playing very boring. Is that not a main problem of your automaton? > > You should try it out---it's amazingly good for its simplicity. The > main deficiencies in our program's play seem to be due to the fact > that it weighs pushing off enemy marbles so much more than positional > strength. But this would be easy enough to adjust. > By the way, another advantage of this evaluation function is that's > it's easy to change it incrementally as we explore the game tree---so > we don't have to compute it from scratch on every position. > > -Mike > Ulrich. From mpf@medg.lcs.mit.edu Wed Apr 28 17:47:22 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1107" "Wed" "28" "April" "93" "17:49:37" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "21" "Re: my abalone evaluation function" "^From:" nil nil "4"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA27042; Wed, 28 Apr 93 17:45:52 EDT Received: by luke (4.1/TOC-1.1C) id AA18079; Wed, 28 Apr 93 17:49:37 EDT Message-Id: <9304282149.AA18079@luke> In-Reply-To: <9304281955.AA17219@coli-gate.coli.uni-sb.de> References: <9304261721.AA13916@luke> <9304281955.AA17219@coli-gate.coli.uni-sb.de> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: ulim@coli.uni-sb.de (Ulrich Mayring) Cc: abalone Subject: Re: my abalone evaluation function Date: Wed, 28 Apr 93 17:49:37 EDT ulim@coli.uni-sb.de (Ulrich Mayring) writes: > Well, what you are saying is, that if we already implemented a nice > Minimax strategy, why not use it? This is a valid statement, but do > you know how many plies commercial chess evaluators search? Methinks > at most 7 (correct me here), so search depth doesn't appear to be > the one-all of board evaluation. Also, with your search strategy you > may not find a good sumito position, because it means giving up a > center position. But if the two marble-structures meet in the middle > of the board, the one, who wants to attack must make a sumito move > AWAY from the center. If he will not do that, because of positional > value, he may well be playing very boring. Is that not a main > problem of your automaton? Actually, in situations like you're describing, my evaluation function often *does* rate the sumito move as being better than staying at the center, because it pushes enemy marbles closer to the edge. What I'm saying is that my eval func doesn't do the *lookahead* to find the sumito move; I just let the search take care of that. -Mike From ant@bernina.ethz.ch Thu Apr 29 02:34:03 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["755" "Thu" "29" "April" "93" "08:35:48" "+0200" "ant@bernina.ethz.ch" "ant@bernina.ethz.ch" nil "16" "Re: Alpha-Beta abolished " "^From:" nil nil "4"]) Return-Path: Received: from bernina.ethz.ch by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA27892; Thu, 29 Apr 93 02:33:14 EDT Message-Id: <9304290633.AA27892@MEDG.lcs.mit.edu> Received: from localhost by bernina.ethz.ch with SMTP inbound id <5848-0@bernina.ethz.ch>; Thu, 29 Apr 1993 08:35:59 +0200 In-Reply-To: Your message of "Wed, 28 Apr 93 21:47:20 +0700." <9304281947.AA17169@coli-gate.coli.uni-sb.de> From: ant@bernina.ethz.ch To: abalone@medg.lcs.mit.edu Subject: Re: Alpha-Beta abolished Date: Thu, 29 Apr 93 08:35:48 +0200 >What do you think of the following (theoretical and impractical) idea: >Abolish Alpha-Beta Pruning and instead store the complete tree for depth n >in RAM or on disk somewhere. Once the computation for depth n is carried out >the best move according to Minimax is carried out. The next n/2-1 moves can >be carried out without any kind of computation, since you only have to look in >the stored proof tree. Not good, because the closer you get to the leafs the worse your minimax value gets. If you can expand the whole search tree then you actually solved the game (as has been done with connect-four) and store this tree once and can always play ideally. Reusing older trees to improve move-ordering is however a widely used technique. Cheers - ant From ulim@coli.uni-sb.de Thu Apr 29 22:10:45 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["1784" "Thu" "29" "April" "93" "23:46:15" "MET" "Ulrich Mayring" "ulim@coli.uni-sb.de " "<9304292146.AA06303@coli-gate.coli.uni-sb.de>" "30" "I still don't like positional values..." "^From:" nil nil "4"]) Return-Path: Received: from iraun1.ira.uka.de by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA00607; Thu, 29 Apr 93 22:09:39 EDT Received: from 134.96.7.7 by iraun1.ira.uka.de with SMTP (PP) id <00812-0@iraun1.ira.uka.de>; Thu, 29 Apr 1993 23:50:03 +0200 Received: from coli-gate.coli.uni-sb.de by sbusol.rz.uni-sb.de (5.65+/v1.0) id AA06511; Thu, 29 Apr 93 23:49:00 +0200 Received: by coli-gate.coli.uni-sb.de (4.1/SMI-4.1/CL930118) id AA06303; Thu, 29 Apr 93 23:46:19 +0200 Message-Id: <9304292146.AA06303@coli-gate.coli.uni-sb.de> X-Mailer: ELM [version 2.3 PL11] From: ulim@coli.uni-sb.de (Ulrich Mayring) To: abalone@medg.lcs.mit.edu Subject: I still don't like positional values... Date: Thu, 29 Apr 93 23:46:15 MET DST Well, Leaving aside for a moment the fact that our program will right now not win a single game against a positional evaluator, I still don't like the idea of doing positional evaluation solely dependent on who is in the center of the board. I think with the broad trees that abalone generates a minimax strategy is bound to fail against a good human player, if it is based on positional value alone. An improvement would e.g. be to compute 'clusters' that are marginally stronger in the center of the board than in some place between the center and the edges and lots stronger than any not-clustered position, where the marbles don't connect to each other well, even if some of them occupy center positions. We did implement this cluster strategy and it appears to do, well say 20% better than positional value based on the center of the board. But it is not enough to beat a good human player. Also, to get a little philosophical here, any strategy based on minimax is not a strategy, but an accumulation of tactics. We found that if we present the automaton with a set of moves (as a minimax does) it sometimes delays good moves, because they are of equal worth when done later. Of course the opponent almost always foils the scheme then, if given the chance. Also, a set (or if you like set of sequences) of moves is a somehow arbitrary collection of do-this do-thats, once the evaluator becomes too intelligent. The program does not play Abalone, it merely computes it. Of course, it is now our turn to come up with a more intelligent evaluation strategy and so far no-one has seen or played against our prog. I can only say that my partner got a little frustrated with the minimax way of doing things stupidly, but fast. Is there a better way? I'll keep you informed... Uli. From mpf@medg.lcs.mit.edu Fri Apr 30 12:39:33 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["681" "Fri" "30" "April" "93" "12:36:21" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "15" "Re: I still don't like positional values..." "^From:" nil nil "4"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA02085; Fri, 30 Apr 93 12:32:30 EDT Received: by luke (4.1/TOC-1.1C) id AA21543; Fri, 30 Apr 93 12:36:21 EDT Message-Id: <9304301636.AA21543@luke> In-Reply-To: <9304292146.AA06303@coli-gate.coli.uni-sb.de> References: <9304292146.AA06303@coli-gate.coli.uni-sb.de> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: ulim@coli.uni-sb.de (Ulrich Mayring) Cc: abalone@medg.lcs.mit.edu Subject: Re: I still don't like positional values... Date: Fri, 30 Apr 93 12:36:21 EDT Ulrich has a very good point, that minimax (and related current techniques) are a very poor and limited way of doing game-playing; very different from the way humans play, showing no long-term strategy at all. AI people have tried, and mostly failed, to make progress along this front. In my Master's research, I am trying to work out general algorithms for working with abstract, long-term goals. One application of this is to improve the state-of-the-art in game playing by showing how to write programs that can do real strategy, in a top-down way, working from high-level goals to low-level tactics and moves. If I have any success at this, I'll let you folks know. -Mike From peter@q2c.nl Mon May 3 04:02:41 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["5725" "Thu" "29" "April" "93" "12:25:53" "+0200" "Peter Tax" "peter@q2c.nl " "" "122" "Re: alpha-beta " "^From:" nil nil "4"]) Return-Path: Received: from sun4nl.nluug.nl by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA06033; Mon, 3 May 93 04:02:35 EDT Received: from qcons by sun4nl.nluug.nl via EUnet id AA03282 (5.65b/CWI-3.3); Mon, 3 May 1993 10:05:53 +0200 Received: by q2c.nl (FernMail); Thu, 29 Apr 93 12:25:53 Message-Id: X-Mailer: Fernmail 1.1 (unregistered, shareware fee not paid) From: peter@q2c.nl (Peter Tax) To: mpf@medg.lcs.mit.edu (Michael P. Frank) Cc: abalone@medg.lcs.mit.edu Subject: Re: alpha-beta Date: Thu, 29 Apr 93 12:25:53 +0200 Hello Michael, First, a request, and then a statement that might lead to some interesting discussion. >You can FTP it at external.nj.nec.com, file /pub/eric/game.ps.Z. Request: Would it be possible to mail me a text-only copy? I don't think I have anything that recognizes .ps.Z format on my Mac, and I'd be very interested to see what this new tree search strategy would mean for Abalone. From what I read in this newsgroup, there are basically two problems in implementing a good Abalone-playing program using a statical board evaluator and an alpha-beta search strategy, namely: 1) Statical board evaluators play too defensively; 2) Alpha-beta does not allow you to think deep enough. Since I believe I have an elegant solution for 1), I'd be interested in a solution for 2) as well. About problem 1): In the University of Waterloo contest, I tried to get a discussion started about the following statemement (which didn't work, so I'll try again here): Statement: The risk for a single ball of being pushed off in a certain direction decreases exponentially with its distance from the edge in that direction. If this statement is true, which I'll try to make plausible below, this gives a nice basis to build a positional evaluation function upon. So, why would this be true? Read on! My first idea was to start with a very simple evaluation function: the closer a ball is to the edge, the worse. This means simply giving each of the 61 fields on the board a positional value determined by the distance (minimal or average or whatever) from the edge. Since you can think of a ball pushed off the board as having a distance of zero from the edge, it's not difficult to understand this should more or less work. With this approach, the evaluation of a board is very simple. Sum all the values of the fields you have a ball on, substract all the values of the fields your opponent has a ball on, and thatUs it. Now take care: I did NOT tell you HOW to derive a positional value from a distance. You may have assumed a simple lineair relation would do fine, and of course this is what I first trie too. This basic strategy more or less works: when given weak or random counterplay, this strategy groups all its balls in the centre of the board, and then effectively does nothing. It just tries to keep or regain the centre, and then tries to stay there. Quite boaring. I soon realised that to make the strategy play more agressively, it should not just be rewarding to move towards the center, but also to push your opponent away from the center, even if this means moving away from the center yourself! Now it may appear to be impossible to assign positional values to the individual fields that make this behaviour appear 'automatically', but the nice thing is, itUs not. It does, however, pose some interesting constraints to the positional values. (Now IUm getting to my statement.) In my program, I decided to assign a ball an 'arbitrary' value of 1024, and give each field a number of 'malus points' (the opposite of bonus points). A ball actually on the board always has a value of 1024 - the malus points for its position at a minimum distance of n from the edge, called M(n); only a hypothetical ball at an infinite distance from the edge would really have the theoretical maximum value of 1024. Now how should the malus points be assigned to make the strategy both agressive as well as oriented towards the center? Consider this example: you have two balls at D4 and C3 (distance from the edge: 4 and 3) lined up with an enemy ball at B2 (distance from the edge: 2). Suppose you want to have a strategy that 'likes' to push the enemy ball outwards, what would this mean for the 'malus points' M(4), M(3) and M(2) for the fields? Assuming the strategy simply adds all your malus points, substracts all your opponents malus points, and tries to minimize the result the following should be true: M(4) + M(3) - M(2) > M(3) + M(2) - M(1) (M(n) ::= malus points for a field at a min. distance n from the edge) Of course, the strategy would stink if, given the opportunity, it would't push off the ball next move, so also M(3) + M(2) - M(1) > M(2) + M(1) - M(0) and in general: M(n+3) + M(n+2) - M(n+1) > M(n+2) + M(n+1) - M(n) <=> M(n+3) > 2 * M(n+1) - M(n) <=> M(n) > 2 * M(n+1) - M(n+3), making the equation M(n) = 2 * M(n+1) - M(n+3) interesting. I'm not a mathematician, so you won't get an exact solution from me, but if you neglect the small -M(n+3) term, and solve the simpler M(n) = 2 * M(n+1), a solution is M(n) = C * 2**(-n). Anyhow, you can see the malus points should decrease very rapidly with increasing n. In my program, I choose 2**(10-n), which is easy to implement in C and would make a ball pushed off really be gone since 1024 - 2**(10-0) is 0 (so far for arbitrary values). I'm not suggesting every good positional strategy should necessarily be this 'agressive'; for example, you could consider a strategy that does not favour pushing its opponent away from the center in a 2-to-1 position, but does do so in a 3-to-2 position, in which case you could do with a slightly slower but still faster-than-lineair decreasing M(n). But I do believe that, in general, an (almost) exponentially decreasing malus points function is required to make a positional strategy sufficiently bloodthirsty. Sounds convincing, doesn't it? Combined with some tree search algorithm superior to Alpha-Beta, this may play quite strong, I think. -------- --- peter@q2c.nl (Peter Tax) ? LOOK You are in a brighly lit room. There is a screen device in front of you. North and East are doors. There is a manager behind you. ? N The door is locked. ? _ From ulim@coli.uni-sb.de Mon May 3 10:59:48 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2963" "Mon" "3" "May" "93" "13:22:21" "MET" "Ulrich Mayring" "ulim@coli.uni-sb.de " nil "65" "Re: alpha-beta" "^From:" nil nil "5"]) Return-Path: Received: from iraun1.ira.uka.de by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA06402; Mon, 3 May 93 10:57:01 EDT Received: from sbusol.rz.uni-sb.de by iraun1.ira.uka.de with SMTP (PP) id <21048-0@iraun1.ira.uka.de>; Mon, 3 May 1993 13:25:36 +0200 Received: from coli-gate.coli.uni-sb.de by sbusol.rz.uni-sb.de (5.65+/v1.0) id AA00708; Mon, 3 May 93 13:25:08 +0200 Received: by coli-gate.coli.uni-sb.de (4.1/SMI-4.1/CL930118) id AA27801; Mon, 3 May 93 13:22:22 +0200 Message-Id: <9305031122.AA27801@coli-gate.coli.uni-sb.de> In-Reply-To: ; from "Peter Tax" at Apr 29, 93 12:25 pm X-Mailer: ELM [version 2.3 PL11] From: ulim@coli.uni-sb.de (Ulrich Mayring) To: abalone@medg.lcs.mit.edu Subject: Re: alpha-beta Date: Mon, 3 May 93 13:22:21 MET DST > > Hello Michael, > > >You can FTP it at external.nj.nec.com, file /pub/eric/game.ps.Z. > > Request: Would it be possible to mail me a text-only copy? > I don't think I have anything that recognizes .ps.Z format on my Mac, > and I'd be very interested to see what this new tree search strategy > would mean for Abalone. ========================================================================== Please send it to ulim@coli.uni-sb.de too. That's me. I have managed to get rid of the .Z (hint: use uncompress FILE), but the .ps is tough, since I don't have a Postscript printer to my disposition. ========================================================================== > From what I read in this newsgroup, there are basically two problems > in implementing a good Abalone-playing program using a statical board > evaluator and an alpha-beta search strategy, namely: > > 1) Statical board evaluators play too defensively; Only when doing a certain kind of board analysis, in our case a center-based positional evaluation. Other analyses are imaginable where the clustering of marbles is only one parameter of several. Say, you have three more para- meters, namely No. of marbles of opponent and myself, No. of secure positions (i.e. three marbles in a row) and No. of marbles at the very edge of the board. The last one is completely unpositional, of course, but since it is only one of four parameters, it evens out. Now, with these four parameters you definitely have an automaton, which doesn't play boring at all. I can say that, because we tried it. The problem with this approach is that the suggested parameters above are too arbitrarily chosen. They do not work so well together as to promote a real strategy. But this is IMHO only a problem of selecting the right parameters and maybe making this selection dependent on the game situation. Then you write: > 2) Alpha-beta does not allow you to think deep enough. > Please clarify this one. I always thought that Alpha-Beta is an optimization of Minimax, so it should allow you to search deeper than Minimax alone. > Statement: The risk for a single ball of being pushed off in a certain > direction decreases exponentially with its distance from the edge > in that direction. > > If this statement is true, which I'll try to make plausible below, this > gives a nice basis to build a positional evaluation function upon. > So, why would this be true? Read on! [I did and found it interesting. Then you conclude:] > Sounds convincing, doesn't it? > Combined with some tree search algorithm superior to Alpha-Beta, > this may play quite strong, I think. It appears to be pretty good for a positional evaluator, because it is not center-bound. But tell me one more thing, which I didn't quite grasp: Does every board position have the base value of 1024, or do the center ones have slightly more? It may even be feasible to give them something like 1100 or so, what do you think? Ulrich From mpf@medg.lcs.mit.edu Mon May 3 14:06:23 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["3014" "Mon" "3" "May" "93" "14:06:33" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "57" "Re: alpha-beta " "^From:" nil nil "5"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA06852; Mon, 3 May 93 14:02:32 EDT Received: by luke (4.1/TOC-1.1C) id AA10273; Mon, 3 May 93 14:06:33 EDT Message-Id: <9305031806.AA10273@luke> In-Reply-To: References: From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: peter@q2c.nl (Peter Tax) Cc: abalone@medg.lcs.mit.edu, mpf@medg.lcs.mit.edu (Michael P. Frank) Subject: Re: alpha-beta Date: Mon, 3 May 93 14:06:33 EDT peter@q2c.nl (Peter Tax) writes: >>You can FTP it at external.nj.nec.com, file /pub/eric/game.ps.Z. > Request: Would it be possible to mail me a text-only copy? > I don't think I have anything that recognizes .ps.Z format on my Mac, > and I'd be very interested to see what this new tree search strategy > would mean for Abalone. Unfortunately, I don't have a plain text copy. If you really want to read the paper and you don't have a Postscript printer or previewer, you might try contacting the authors: Eric B. Baum and Warren D. Smith , and they would probably give you their TeX source, which would be more readable than the postscript. Bear in mind that the paper is pretty technical. I'll go ahead and type in the abstract, and you can determine from that whether you want to go to more trouble to get it: Title: Best Play for Imperfect Players and Game Tree Search Authors: Eric B. Baum and Warren D. Smith DRAFT April 23, 1993 Abstract: We propose a new approach to game tree search. We train up an evaluation function which returns, rather than a single number estimating the `value' of a position, a probability distribution P_L(x). P_L(x) is the probability that if we expanded leaf L to some depth, the backed up value of leaf L would then be found to be x. We describe how to propagate these distributions efficiently up the tree so that at any node n we compute without approximation the probability node n's negamax value is x given that a value is assigned to each leaf from its distribution. After we are done expanding the tree, the best move is the child of the root whose distribution has highest mean. Note that we take means at the child of the root *after* propagating, whereas the normal (Shannon) approach takes the mean at the leaves before propagating, which throws away information. Now we model the expansion of a leaf as selection of one value from its distribution. The total utility of all possible expansion is then by definition the ensemble sum over those possible leaf configurations for which the current favorite move is inferior to some alternate move, weighted by the probability of the leaf configuration and the amount the current favorite move is inferior. We propose as the natural measure of the expansion importance of leaf L, the expected absolute change in this utility when we expand leaf L. We support this proposal with several arguments including an approximation theorem valid in the limit that one expands until the remaining utility of expansion becomes small. In summary, we gather distributions at the leaves, propagate exactly all this information to the root, and incrementally grow a tree expanding approximately the most interesting leaf at each step. Under reasonable conditions, we accomplish all of this in time O(N), where N is the number of leaves in the tree when we are done expanding. That is, we pay only a small constant factor overhead for all of our bookkeeping. -Mike From ninja@halcyon.halcyon.com Tue May 4 00:03:18 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["141" "Mon" "3" "May" "1993" "21:04:05" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" "<199305040404.AA15558@halcyon.com>" "3" "Re: alpha-beta" "^From:" nil nil "5"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07801; Tue, 4 May 93 00:01:17 EDT Received: by halcyon.com id AA15558 (5.65c/IDA-1.4.4 for mpf@medg.lcs.mit.edu); Mon, 3 May 1993 21:04:05 -0700 Message-Id: <199305040404.AA15558@halcyon.com> From: Jonathan Roy To: mpf@medg.lcs.mit.edu, peter@q2c.nl Cc: abalone@medg.lcs.mit.edu Subject: Re: alpha-beta Date: Mon, 3 May 1993 21:04:05 -0700 That BPIP paper is pretty neat. My mentor is reviewing it right now to let mw know whether or not to spend time trying to implement it. :) From mpf@medg.lcs.mit.edu Tue May 4 13:24:47 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["450" "Tue" "4" "May" "93" "13:27:41" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "11" "Re: alpha-beta" "^From:" nil nil "5"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08755; Tue, 4 May 93 13:23:37 EDT Received: by luke (4.1/TOC-1.1C) id AA11459; Tue, 4 May 93 13:27:41 EDT Message-Id: <9305041727.AA11459@luke> In-Reply-To: <199305040404.AA15558@halcyon.com> References: <199305040404.AA15558@halcyon.com> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: Jonathan Roy Cc: abalone@medg.lcs.mit.edu, mpf@medg.lcs.mit.edu, peter@q2c.nl Subject: Re: alpha-beta Date: Tue, 4 May 93 13:27:41 EDT Jonathan Roy writes: > That BPIP paper is pretty neat. My mentor is reviewing it right now to > let mw know whether or not to spend time trying to implement it. :) Be careful; the authors told me they don't have a working implementation yet. However, they seem to have figured out basically how everything will work. If you need more details to figure out how to implement it, they are very helpful via email. -Mike From ninja@halcyon.halcyon.com Tue May 4 15:30:00 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["931" "Tue" "4" "May" "1993" "12:31:17" "-0700" "Jonathan Roy" "ninja@halcyon.halcyon.com" "<199305041931.AA07801@halcyon.com>" "21" "Re: alpha-beta" "^From:" nil nil "5"]) Return-Path: Received: from halcyon.com by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA09004; Tue, 4 May 93 15:28:37 EDT Received: by halcyon.com id AA07801 (5.65c/IDA-1.4.4 for mpf@medg.lcs.mit.edu); Tue, 4 May 1993 12:31:17 -0700 Message-Id: <199305041931.AA07801@halcyon.com> From: Jonathan Roy To: mpf@medg.lcs.mit.edu, ninja@halcyon.halcyon.com Cc: abalone@medg.lcs.mit.edu, peter@q2c.nl Subject: Re: alpha-beta Date: Tue, 4 May 1993 12:31:17 -0700 Yeah, I've mailed them a few times. They are working on a larger COnnect-4 varient, and Kalah I think... I'd probably try to apply BPIP towards Abalone or something like that... :) I'm also interested in doing some research into using graphs for future moves instead of trees. Just have to decide what to spend my time on this summer :) (I've already start work on some of the CG software I want to write... Sigh.) Not enough hours in the day. :) Is there any standard for Abablone programs to play each other yet? Is anyone still interested in making one? (I remember the discussion from way back..) See ya. F F Jonathan Roy, of the Free Access Foundation Email: ninja@faf.org A Mail faf@halcyon.com for information, or FTP to halcyon.com: /pub/faf/ F F Vorlons, of the Galactic Bloodshed Development Team GEnie: J.ROY18 "Everything that has transpired has done so according to my design." - _RotJ_ From ulim@coli.uni-sb.de Tue May 11 07:24:17 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil t nil nil nil nil] ["1544" "Tue" "11" "May" "93" "13:21:59" "MET" "Ulrich Mayring" "ulim@coli.uni-sb.de " "<9305111122.AA13635@coli-gate.coli.uni-sb.de>" "31" "Tested Peter Tax's program" "^From:" nil nil "5"]) Return-Path: Received: from iraun1.ira.uka.de by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA07858; Tue, 11 May 93 07:22:02 EDT Received: from sbusol.rz.uni-sb.de by iraun1.ira.uka.de with SMTP (PP) id <10736-0@iraun1.ira.uka.de>; Tue, 11 May 1993 13:25:11 +0200 Received: from coli-gate.coli.uni-sb.de by sbusol.rz.uni-sb.de (5.65+/v1.0) id AA18494; Tue, 11 May 93 13:25:06 +0200 Received: by coli-gate.coli.uni-sb.de (4.1/SMI-4.1/CL930118) id AA13635; Tue, 11 May 93 13:22:03 +0200 Message-Id: <9305111122.AA13635@coli-gate.coli.uni-sb.de> X-Mailer: ELM [version 2.3 PL11] From: ulim@coli.uni-sb.de (Ulrich Mayring) To: abalone@medg.lcs.mit.edu Subject: Tested Peter Tax's program Date: Tue, 11 May 93 13:21:59 MET DST Hi folks, Am I actually the only one on this list beside Peter Tax, who tested his Abalone version on the Mac? If not, I would be interested in hearing what you think of its playing strength. (BTW: Peter, I lost your EMail address, please send me message.) Anyways, I played a few games against the three different computer oppo- nents (Terminator III, Darth Vader and Bill Gates IV). Except for the fact that the Mac seems to hang itself, whenever Darth Vader is playing at 3 plies or more and further excepting the fact that Terminator III thinks overly long on some moves, the program works really fine. Moves can be entered with the mouse and the Computer moves are not made immediately, but they are foreshadowed by some blinking on the screen in order to make it visible what the Computer wants to do. The three computer opponents do not seem to play a lot different, but I only played two or three games against each, so I may not be able to really tell. What surprised me was, how good they actually are. If I am not careful they can beat me. Only if I put together all my concentration and really think about moves can I beat them. However, then I beat them every time. (On the other hand it may be said that when I play non- chalantly, they beat me about half the time). Since I don't know how good I actually am, this does not tell me a lot, but Peter, who must have a lot of experiences with his program, may bring some light into it. So, how do you do against it? Further detailed comments later, I gotta run now... Ulrich From mpf@medg.lcs.mit.edu Tue May 11 13:56:44 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["127" "Tue" "11" "May" "93" "13:57:37" "EDT" "Michael P. Frank" "mpf@medg.lcs.mit.edu " nil "4" "Re: Tested Peter Tax's program" "^From:" nil nil "5"]) Return-Path: Received: from luke (LUKE.LCS.MIT.EDU) by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA08596; Tue, 11 May 93 13:53:11 EDT Received: by luke (4.1/TOC-1.1C) id AA05210; Tue, 11 May 93 13:57:37 EDT Message-Id: <9305111757.AA05210@luke> In-Reply-To: <9305111122.AA13635@coli-gate.coli.uni-sb.de> References: <9305111122.AA13635@coli-gate.coli.uni-sb.de> From: mpf@medg.lcs.mit.edu (Michael P. Frank) To: ulim@coli.uni-sb.de (Ulrich Mayring) Cc: abalone@medg.lcs.mit.edu Subject: Re: Tested Peter Tax's program Date: Tue, 11 May 93 13:57:37 EDT I've played Peter Tax's Mac Abalone program too. It's nice. I should have a battle sometime between it and MITAbalone. -Mike From tcela!la.tce.com!gilles@uunet.uu.net Tue May 11 19:27:27 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1527" "Tue" "11" "May" "93" "15:30:16" "PDT" "Gilles Boccon-Gibod" "gilles@la.tce.com " nil "33" "Re: Tested Peter Tax's program" "^From:" nil nil "5"]) Return-Path: Received: from relay2.UU.NET by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA09566; Tue, 11 May 93 19:24:45 EDT Received: from spool.uu.net (via LOCALHOST.UU.NET) by relay2.UU.NET with SMTP (5.61/UUNET-internet-primary) id AA28008; Tue, 11 May 93 18:30:28 -0400 Received: from tcela.UUCP by spool.uu.net with UUCP/RMAIL (queueing-rmail) id 182915.5757; Tue, 11 May 1993 18:29:15 EDT Received: from ksi.tcela by la.tce.com (4.1/SMI-4.1) id AA09952; Tue, 11 May 93 15:30:16 PDT Message-Id: <9305112230.AA09952@ la.tce.com> From: gilles@la.tce.com (Gilles Boccon-Gibod) To: abalone@medg.lcs.mit.edu Subject: Re: Tested Peter Tax's program Date: Tue, 11 May 93 15:30:16 PDT I've played with Peter Tax's Mac Abalone too, and found it very easy to use. My first conclusion are: It plays well for a simple strategy. The three strategies are quite alike, If you don'y have a quadra, you should not use the 3-plies depth, but this is not a big problem, because the program is not much different at 1 or 2 plies than at 3. The major problem in my opinion are that the program is not aware that a given position can yield the end of the game, so if you already have pushed 5 of his balls out and offer one of your balls as a sacrifice (i.e. if it pushes it out, then you can also push on of his), it will accept it so you will win. I am not a good player (I have hardly played more than a dozen games against a human player), though I can beat the program each time. But may be this is due to the fact that I found a tactic that works all the times with this program (to concentrate a block in the center of the board, then begin to push-and-retract until the opponent is too much spread over the board, then push his balls out). I've read Peter Tax's sources I'd very much like to be able to try other programs if some exist. I am currently writing my own abalone-playing program on a mac (and on unix too), so that I can test it against other programs or humans. I've read that there was an MITAbalone, and I would love to try it if any one could mail it to me (I don't have FTP yet). Could anyone give some advice on good books on computer-game-playing strategies and algorithms. Thanks. -- Gilles -- From ulim@coli.uni-sb.de Wed May 12 07:07:03 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["3767" "Wed" "12" "May" "93" "12:57:36" "MET" "Ulrich Mayring" "ulim@coli.uni-sb.de " nil "73" "re: Tested Peter Tax's program" "^From:" nil nil "5"]) Return-Path: Received: from iraun1.ira.uka.de by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA10322; Wed, 12 May 93 06:57:41 EDT Received: from sbusol.rz.uni-sb.de by iraun1.ira.uka.de with SMTP (PP) id <11363-0@iraun1.ira.uka.de>; Wed, 12 May 1993 13:00:55 +0200 Received: from coli-gate.coli.uni-sb.de by sbusol.rz.uni-sb.de (5.65+/v1.0) id AA03769; Wed, 12 May 93 13:00:42 +0200 Received: by coli-gate.coli.uni-sb.de (4.1/SMI-4.1/CL930118) id AA00660; Wed, 12 May 93 12:57:39 +0200 Message-Id: <9305121057.AA00660@coli-gate.coli.uni-sb.de> In-Reply-To: ; from "Peter Tax" at May 11, 93 4:15 pm X-Mailer: ELM [version 2.3 PL11] From: ulim@coli.uni-sb.de (Ulrich Mayring) To: abalone@medg.lcs.mit.edu Subject: re: Tested Peter Tax's program Date: Wed, 12 May 93 12:57:36 MET DST > > Hello Ulrich, > > Glad to read you more or less appreciate my program, > after all the trouble you went through getting it. > Thanks for the posting of the short review too. > I do appreciate it very much, my criticism is just to show you some problems you may not be aware of. > You did not mention the nice sounds - they took me 2 days to record, > and they're even more or less useful- they draw your attention when > the Mac makes a move. Well, unfortunately the sounds are lost on me, because here is a Terminal- room, where people want to work, so I can't really turn it up... > The same. The best strategy of the three is, I think, Terminator III. > It's sometimes very slow indeed at 3 plies indeed, especially when it's > in deep trouble - I think this is somehow a consequence of using > alpha-beta. > I usually play it at 2 plies, and try to lose no balls at all, > to make it a real challenge. > At 2 plies, I think 6-2 is about my average score. > At 3 plies, I usually win too, but, like you, I have to be careful to > keep concentrated, and 6-3 or 6-4 is more typical, although I still > keep getting better in beating my own program. Hmm... strange, I think Darth Vader at 2 plies is the best. Most definetly Bill GAtes at 3 can be beaten 6-0, but I also lost against him, when I wasn't careful. But all this can to some extent be attributed to my own style of play, which tends to forsake position every once in a while. So we all seem to agree that your program plays good enough to beat anyone of us at least sometimes. That's a very good result for a first try, Peter. However, there's one problem: (In addition to the one, that no end-check is made). If I place my marbles all on the outermost circle, the computer# will not make good on this. Instead it moves senselessly about in the center of the board. Unfortunately that get me nowhere either, so it's a stalemate. Another thing is that whenever I succeed in controlling the center of the board, it's a big win everytime, because the program can't really do any- thing against that. On the other hand if it occupies the center it becomes very hard for me. So that is an argument for Abalone being a purely positional game. The problem is that in the beginning of the game very often a stalemate position can occur, unless I make offensive moves. If I play defensively the program doesn't attack me, so even a novice should be able to score a draw against the program everytime. Also, I only played games where the program was black, on that one occasion where I had black I occupied the center easily and won the game shortly after. All this being said, the program still plays amazingly well, unless you treat it like a computer and make 'stupid' moves to confuse it. And, I think these experiences will be relatively the same for all programs based mainly on positional evaluation. If you allowed use of a larger board, I think a positional strategy will become worse and worse the larger the board becomes, because then it will need a real strategy. Is this something you could implement easily? I think that would be very interesting. Finally, the last problem is the one of perception. As humans we tend to 'overlook' moves, sometimes we move amazingly stupid and sometimes amazingly intelligent. An algorithm is more balanced, I think. The thing here is now, that the board on the screen is a little too small, so I find myself making more stupid moves than on my 'real' Abalone board. (Of course that may partly be attributed to 3D vs. 2D. But making the window a bit bigger or even scalable is another suggestion I find useful. Good, that's enough for today and I would like to say thank you to Peter for making this great program available to all of us. Ulrich From peter@q2c.nl Thu May 13 09:53:47 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["4342" "Thu" "13" "May" "93" "15:45:05" "+0200" "Peter Tax" "peter@q2c.nl " nil "86" "re: Tested Peter Tax's program" "^From:" nil nil "5"]) Return-Path: Received: from sun4nl.nluug.nl by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA12699; Thu, 13 May 93 09:51:09 EDT Received: from qcons by sun4nl.nluug.nl via EUnet id AA03501 (5.65b/CWI-3.3); Thu, 13 May 1993 15:54:54 +0200 Received: by q2c.nl (FernMail); Thu, 13 May 93 15:45:05 Message-Id: X-Mailer: Fernmail 1.1 (unregistered, shareware fee not paid) From: peter@q2c.nl (Peter Tax) To: ulim@coli.uni-sb.de (Ulrich Mayring) Cc: abalone@medg.lcs.mit.edu Subject: re: Tested Peter Tax's program Date: Thu, 13 May 93 15:45:05 +0200 > However, there's one problem: (In addition to the one, that no end-check > is made). If I place my marbles all on the outermost circle, the computer# > will not make good on this. Instead it moves senselessly about in the center > of the board. Unfortunately that get me nowhere either, so it's a stalemate. Yes, that's true. According to the evaluation function, the computer is in a very good position, and the only improvement it is able to see, is to push you even closer to or over the edge. To see the moves that would actually push marbles off, more plies would be needed. The funny thing is, unexpirienced players often end up in this utterly hopeless position (believe me; I tested the program on some friends): they get kicked out of the center, get pushed to the outer circles, and can save most of their marbles only by leaving them there. The frustrating thing about this is, whenever you try to 'regroup', you move marbles inward, often getting them in touch with the computer's marbles, and the computer, now 'seeing' your marbles, pushes them out again, so whether it's initially a stalemate position by your own choise or not, in the end, the computer chooses to keep it that way. > Another thing is that whenever I succeed in controlling the center of the > board, it's a big win everytime, because the program can't really do any- > thing against that. Also true. If you beat a positional strategy on its own terms, it's completely defeated. But this must be true for strategies in general. > If you allowed use of a larger board, I think a positional strategy > will become worse and worse the larger the board becomes, > because then it will need a real strategy. Maybe, maybe not. My intuition tells me you're probably right, but it also tells me the world is flat. The added complexity may make it more difficult not to oversee the obviously good (counter)moves. > Is this something you could > implement easily? I think that would be very interesting. Not easily, because I did not anticipate this, and there are some hard- wired tables in the program. On the other hand, it looks like a useful and interesting generalisation, so I may take a closer look at it. > Finally, the last problem is the one of perception. As humans we tend > to 'overlook' moves, sometimes we move amazingly stupid and sometimes > amazingly intelligent. An algorithm is more balanced, I think. I think so too; what this appears to mean to me is, in computer terms, humans use a different, 'risky' pruning strategy. If I'd have to try to program a 'humanoid' playing strategy, I think I should start with a positional evaluation function similar to the one I have now, and concentrate on the pruning mechanism. It's completely normal for a human player to think 8 plies deep, and it's also completely normal to overlook an obviously good move at only 0, 1 or 2 plies deep. Together, this suggests some very rigorous pruning. Thinking about it, doesn't 'having a plan' (which is what we usually claim to do) just mean considering ONLY the moves that seem to contribute to the plan in the near future, discarding all others? Something like 'This doesn't look good; let's not think about it' Anyhow, I received the Game Tree Search paper yesterday. I haven't read it yet (it looked a bit too difficult to read after a day's work), but I'm curious if there is some nice pruning mechanism described in it that's more advanced than pruning out what you *know* is wrong (alpha-beta pruning). > The thing here is now, that the board on the screen is a little too > small, so I find myself making more stupid moves than on my 'real' > Abalone board. (Of course that may partly be attributed to 3D vs. 2D > But making the window a bit bigger or even scalable is another > suggestion I find useful. Click the size box in the upper right corner of the window to get the bigger window size. The small size is the default size; I made the default size that small so people with a compact Mac (plus, SE) can use the program 'as is'. The size you last selected is saved in the preferences file. The bigger size looks better on a 640*480 monitor. --- peter@q2c.nl (Peter Tax) ? LOOK You are in a brighly lit room. There is a screen device in front of you. North and East are doors. There is a manager behind you. ? N The door is locked. ? _ From peter@q2c.nl Mon May 17 03:05:54 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["753" "Fri" "14" "May" "93" "15:21:25" "+0200" "Peter Tax" "peter@q2c.nl " nil "22" "re: Very silly question" "^From:" nil nil "5"]) Return-Path: Received: from sun4nl.nluug.nl by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA19263; Mon, 17 May 93 03:04:37 EDT Received: from qcons by sun4nl.nluug.nl via EUnet id AA06408 (5.65b/CWI-3.3); Mon, 17 May 1993 09:08:29 +0200 Received: by q2c.nl (FernMail); Fri, 14 May 93 15:21:25 Message-Id: X-Mailer: Fernmail 1.1 (unregistered, shareware fee not paid) From: peter@q2c.nl (Peter Tax) To: Lord Chaos Cc: abalone@medg.lcs.mit.edu Subject: re: Very silly question Date: Fri, 14 May 93 15:21:25 +0200 Hello Douglass, > Hello there, I just subscribed to the abalone mailing list and > was reading of your program. I would like to grab a copy to > take a look at it. Is it available via anonymous ftp someplace ? The program is available via anonymous ftp at all important Mac archive sites (e.g. mac.archive.umich.edu and its mirrors). Requirements: a Macintosh running system 7. The source code (C, partly very Mac-specific) is not available via anonymous ftp, but at request, since I don't want someone to make any kind of commercial use of the source. --- peter@q2c.nl (Peter Tax) ? LOOK You are in a brighly lit room. There is a screen device in front of you. North and East are doors. There is a manager behind you. ? N The door is locked. ? _ From hwloidl@risc.uni-linz.ac.at Wed Sep 1 03:16:38 1993 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1762" "Wed" "01" "September" "93" "09:28:38" "+0200" "Hans Wolfgang Loidl" "Hans.Wolfgang.Loidl@risc.uni-linz.ac.at" nil "36" "Variants of the rules" "^From:" nil nil "9"]) Return-Path: Received: from melmac.risc.uni-linz.ac.at by MEDG.lcs.mit.edu (4.1/TOC-1.2S) id AA16478; Wed, 1 Sep 93 03:15:04 EDT Received: from localhost by melmac.risc.uni-linz.ac.at with SMTP id AA17707 (Sendmail 5.65c/IDA-1.4.4 for ); Wed, 1 Sep 1993 09:28:44 +0200 Message-Id: <199309010728.AA17707@melmac.risc.uni-linz.ac.at> From: Hans Wolfgang Loidl To: abalone@medg.lcs.mit.edu Subject: Variants of the rules Date: Wed, 01 Sep 93 09:28:38 +0200 Dear Friends! I have only played a few games of abalone so far, but I had the impression that in total it's a rather `static' game. At least I found it very difficult to defeat a player who is extremely defensive. Usually, the attacker exposes a weakness in his position in his effort to make a strong attack and thereby takes a high risk of losing the game if the defender exploits this weakness. I know from friends, who tried to change the rules such that a series of up to 5 stones can be moved to make the game more dynamic. However, that games ended up in a race to the center and whoever takes the center first will probably win the game. Now, my question is: Has anybody of you experiences with variants of the rules of the game and the effect to the optimal strategy that should be used for this variant? P.S.: Is there any public domain X-Prg available for playing abalone over the net? A guy at our institute implemented an ASCII based version, but that's quite ugly, of course. Greetings, -- Hans Wolfgang Loidl hwloidl@risc.uni-linz.ac.at ---------------------------------------------------------------------------- | RISC-Linz | Phone: +43 7236 3231-66 | | Research Institute for Symbolic Computation | FAX: +43 7236 3231-30 | | Johannes Kepler University | | | A-4040 Linz, Austria, Europe | Bitnet: K318576@ALIJKU11 | |--------------------------------------------------------------------------| | Vanitas Vanitatum! | ----------------------------------------------------------------------------