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 cente