December 2003 - cypherpunks-legacy

Re: How Many Games of Chess?
by lefty＠apple.com 17 Dec '03

17 Dec '03

>p.s. i wonder if there is a "irrational" game....one that goes on to >infinity but never repeats itself.....I would imagine not as there are >only a finite number of possibilities for peices to exist on the board >it was an interesting thought whie it lasted.... I can easily think of a trivial one. Get to a point where the only pieces left on the board are the two kings. Roll an eight-sided die to determine the next move for each king. If the move would place the king in check, roll again. -- Lefty (lefty(a)apple.com) C:.M:.C:., D:.O:.D:.

1 0

Number of Legal Chess Games
by tcmay＠netcom.com 17 Dec '03

17 Dec '03

On the question someone asked about the number of chess games... My recollection is that a fairly careful calculation of the number of legal games between good players (see Note below) is about 10^140. The number of legal Go games is vastly larger, around 10^700. (Each board position has far more branch positions, the Go board being 19 x 19.) I have a bunch of Go books, and some computer chess books (Levy), but I can't find the calculation referenced. It's not a "plug in" calculation, either, as a lot of empirical cruft (good moves, winning configurations, etc.) gets taken into account. But I think the basic estimate of around 10^140 is well-accepted. It might be as "low" as 10^120 or as "high" as 10^160, for example, but that's the right ballpark, from what I've seen. As a reminder, it is estimated that there are about 10^72 particles in the entire universe. Thus, about 10^60 games of chess for each and every particle in the universe. The situation with Go is even more extreme. Welcome to the strange and exciting world of combinatorial explosion. (Note: If two infinitely powerful agents played, the number would presumably drop, as each would see the implications--chess not being a game of chance--of who made the first move and one side would resign. Lesser agents would have more games, presumably. Even lesser agents, novices, might eventually have _fewer_ games, as the games stumbled into wins earlier on. A novice against a grandmaster should also have far fewer games. as the grandmaster wins quickly. At what point of expertise the "maiximum" number of games exists is an interesting question.) For further info, I'd recommend the many good books on computer chess....I'm sure that some of them sketch out how these calculations are done. I've recently seen several new books on computer Go and computer chess, which technical bookstores and libraries should have. Also, asking on rec.games.chess and rec.games.go might produce better results than here on Cypherpunks. The question might well even be in a FAQ for rec.games.chess...now I'm curious about this and will go check. --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."

1 0

RE: How Many Games of Chess?
by Mike Markley 17 Dec '03

17 Dec '03

---------- | From: Robert M. Solovay <netmail!solovay(a)math.berkeley.edu> | To: Mike Markley | Cc: <cypherpunks(a)toad.com> | Subject: How Many Games of Chess? | Date: Friday, April 01, 1994 11:06AM | | Received: from math.Berkeley.EDU by netmail.microsoft.com with SMTP (5.65/25-eef) | id AA02131; Fri, 1 Apr 94 11:04:58 -0800 | Received: by math.berkeley.edu (8.6.8/1.33(math)Ow) | id LAA28894; Fri, 1 Apr 1994 11:06:45 -0800 | Message-Id: <199404011906.LAA28894(a)math.berkeley.edu> | In-Reply-To: Mike Markley's message of Fri, 1 Apr 94 10:20:55 | TZ <9404011831.AA05066(a)netmail2.microsoft.com> | | | mmarkley(a)microsoft.com writes: | | I seem to remember from way back in high school that the number of | potential moves by the third set of moves is on the order of billions | of legal moves. | | The number of moves in a given chess position is less than 64 | (number of starting squares) times 64 (number of destination squares) | x 4 [number of ways a pawn can promote]. Thus we get the bound 16, 384 | [which can be easily improved] which is way less than "billions of | possible moves". The same computation shows that the number of | possible games of length n grows at worst expoentially pace mr | markley. | | The right way to think about this is to get sharp upper bounds rather | than attempt a precise calculation. A crude upper bound would be | longerst possible game is about 6000 moves [using the 50 move rule]. | At most 2**16 mves per position so at most 10**[192 * 10**6] games. | I'm sure that sharper estimates are readily available. | | I should have said billions of potential states for the board after each move. If you think of the number of initial moves for the starting player its only 16 potential positions for the pawns and 4 for the knights. If the first player takes one of these positions then the second player moves he has the same 20 potential moves giving an potential state of 400 different positions after the first move. After the second move there is on the order of greater than 160,000 potential states for the board. After 3 moves it is greater than 2.56 * 10^10 potential states. I was thinking in terms of states rather than valid moves. Mike. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Mike Markley || The opinions here do not represent the mmarkley(a)microsoft.com || opinions of my employer. Attempts to || associate the two are pointless. "I want to look at life, In the available light" - Neil Peart -

1 0

Re: Anonymous phone calls.
by jamiel＠sybase.com 17 Dec '03

17 Dec '03

At 6:25 AM 04/01/94 -0800, GRABOW_GEOFFREY(a)tandem.com wrote: > I know how to suppress the transmission of your phone number (caller >id) with *67, but I've heard that there is a way to force the routing of One point here- you are not actually suppressing the transmission of your phone number. It is transmitted *between switches* in any case- you are simply suppressing the transmission from a switch to the destnation phone. This is important in relation to the phone company recieving data, as well as the distinct possibility that a clever person could still get this. I got the above info out of Phrack Magazine (_Caller ID Technical Details_ by Hyperborean Menace #45-06, still being issued as I write this). >call through multiple long distance companies. Since the LDCs don't talk >to one another, this should increase the difficulty of tracing and/or >tapping a call. Does anybody know how to do this? Don't know, but from what little I know about the phone company, I would assume using the demand-dial numbers (like 102880) for ATT) from another long distance phone would be a start. jamie

1 0

Re: the rest of the key
by Carl Ellison 17 Dec '03

17 Dec '03

> >I understand the Skipjack review committee will be looking into the key >generation process at Mykotronx also. The procedures originally proposed >for burning in the keys has some annoying flaws that have been pointed out >frequently, like the existence of both halves in the same room at the same >time, which would be a tempting target for somebody siphoning them off to >a private single-site escrow. :) Various people have suggested that the >two halves of the key could be burned in at separate locations, so that the >only place they're put together is in the key itself; this was not part of >the proposal as we've seen it so far out here. > ..but what of at least the original description which had the key generated by a function within the sacrificial laptop (a PRNG driven by the two key pieces supplied by the escrow agents)? K_i = PRNG( E_1, E_2, i ) ; If PRNG is secret (a high power NSA algorithm), it might be a *truly* high quality one-way-function -- which happens to be independent of E_1 and E_2. No one would be the wiser -- and the NSA's job would be a lot easier, in the event that some chips get stolen or someone bombs the escrow center and its backup sites. - Carl

1 0

Re: patent search service (fwd)
by rarachel＠photon.poly.edu 17 Dec '03

17 Dec '03

Incase you need to sneak up on some patents, you have your chance next week... These guys are doing a >FREE< patent search for a week because they're testing their systems... I thought I'd pass this on to you incase you'd like to look up the finer points of crypto, the MicroSoft-Stacker patents wars, etc... Forwarded message: > From spo_patent(a)spo.eds.com Mon Mar 28 22:56:07 1994 > Date: Mon, 28 Mar 94 21:11:48 CST > From: spo_patent(a)spo.eds.com > To: uunet!photon.poly.edu!rarachel(a)uunet.UU.NET > Sender: spo_patent(a)spo.eds.com > Subject: Re: patent search service > Message-Id: <19940328_162456_spo14_5430> > Return-Receipt-To: spo_patent(a)spo.eds.com > > EDS-SPO ELECTRONIC MAIL PATENT SEARCH SERVICE > PHASE TWO FREE TESTING PERIOD > April 4-April 15, 1994 > > CONCEPT VERSUS BOOLEAN SEARCHES > > Key word searches are now obsolete. EDS' Shadow Patent Office (SPO) > has developed a computerized, concept search method that utilizes the > Internet Information Superhighway. This on-line, computerized method > analyzes input text and compares it against EDS-SPO's database of 1.7 > million US utility patents. > > THE TECHNOLOGY BEHIND CONCEPT SEARCHES > > The EDS-SPO concept search method utilizes massive databases with huge > memory (20 gigabytes), parallel hardware and software, and client > -server technology. The EDS-SPO computer's combination of advanced > hardware and software maximizes fast access to its main memory. > Consequently, EDS-SPO can offer customers a fast, accurate, and cost > effective patent search. EDS-SPO has offered patent searching since > 1992. > > PHASE II TESTING > > The Phase II testing period will occur April 4, 1994 through April 15, > 1994. During this time, each participant will be allowed 3 free patent > searches per day. After April 15, 1994, there will be fees associated > with the type of patent search requested. > > For the Phase II testing period, users may request Subject Search > reports by providing 50-1000 words of text and keywords in electronic > mail format. An Infringement Search report is also available. A user > requests this report by providing a patent id number and keywords in > electronic mail format. A report will be electronically mailed back to > the user requesting either type of report. Each report will contain the > following information for the 50 closest patents to the search criteria. > > o Patent ID > o Issue Date > o Class > o Title > o Inventor > o Assignee > o Abstract > > Any organization or individual researching and/or developing a non- > patented product or service will want on-line access to this powerful > search tool. Areas of potential research include, but are not limited > to: electronics, chemicals, pharmaceuticals, software, petroleum, and > mechanics. > > HOW TO REGISTER > > Prior to performing a patent search, you must be registered with EDS-SPO. > To register, fill out the form below and send it to the following > Internet address: spo_patent(a)spo.eds.com. > > PLEASE ANSWER THE FOLLOWING QUESTIONS > > 1) Company Name: ___________________________________________ > 2) Customer Name____________________________________________ > 3) Title: _________________________________________________ > 4) Address: (street)________________________________________ _________________________________________________________ > City: _____________ State: ____________ County:_______ > Zip: ______________ Country: __________ > 5) E-Mail address: ________________________________________ > 6) Telephone Number:________________________________________ > 7) Fax Number: _____________________________________________ > > When the above information is provided, EDS-SPO will send you > a tutorial via the Internet. > > > CONTACTS > > Contact EDS-SPO by sending an e-mail message to spo_patent(a)spo.eds.com. > > > CONFIDENTIALITY AGREEMENT BETWEEN CUSTOMER AND EDS-SPO > > The EDS-SPO network and system are separated from the rest of EDS. > EDS-SPO agrees to keep all customer information confidential and will > allow only those staff members with a need to know to have access to > such information. Customer information shall include, but not limited > to, search disclosures, customer names, report requests, and any other > written, electronic, or oral correspondence between EDS-SPO and its > customer. >

1 0

RSA contact info needed
by Don Melvin 17 Dec '03

17 Dec '03

Hi! I seem to have lost some files. One of them had contact information for RSA and a comment that they are resonable in their licensing pratices. If someone could email that info to me, I'd be very appreciate. Thanks, Storm

1 0

How Many Games of Chess?
by collins＠newton.apple.com 17 Dec '03

17 Dec '03

>This is tangentially related to crypto. I've been reading A.K. Dewdney's >_The New Turning Omnibus_ recently to refresh my memory of all that stuff >I learned in undergrad that I'm going to see again on the Comp Sci GRE >shortly. :-) Anyway, I was glancing through the chapters on complexity, >computabilty, and minimax trees, and I got to wondering something: how >many possible games of chess are there? I know that it has to be a finite >number, but I'm not sure how to go about finding this number. Any >pointers would be appreciated. First, I think there are a finite number of games only if all stale-mates are are required to terminate. Second, here's one way if `just walking the tree` is too boring for you: 0 - Start your computer on this while you hop in a starship and circle in local space at a significant fraction of C. 1 - Generate every legitimate board position (don't forget, pawns may be promoted to other pieces) without regard for playing games. A board position might be expressed as a 64 digit, base 13 number. More efficient representation is probable (and desirable). Plainly the number of board positions is something vastly smaller than 13^64 which is 1.96e71 or 196053476430761073330659 760423566015424403280004 115787589590963842248961 At this time, use two extra bits per state to note the mate condition. Additionally, the total number of games must be less than or equal to the total number of permutations of every possible board position. Thus the total number of possible chess games is something (again vastly) less than (13^64)! (i.e., factorial --- sorry, Mathematica found this a little too daunting to give me an estimate). 2 - Connect nodes with edges representing possible moves. For each position, there can be no more than 64 pieces that might move, and for each, no more than 63 possible results (including pawn promotion), so the maximum number of edges is (13^64)*64*63 or about 7.90e74. At this time, or slightly later, use the mate bits to indicate stale-mates. 3 - Remove all subgraphs unreachable from the distinguished node that represents the starting position. 4 - Count the number of distinct paths through the graph that end in a mate or a stale-mate. 5 - Land your spaceship, collect your answer and find out how much money accumulated in your hedge-fund while you were gone. Scott Collins | "That's not fair!" -- Sarah | "You say that so often. I wonder what your basis 408.862.0540 | for comparison is." -- Goblin King ................|.................................................... BUSINESS. fax:974.6094 R254(IL5-2N) collins(a)newton.apple.com Apple Computer, Inc. 5 Infinite Loop, MS 305-2D Cupertino, CA 95014 ..................................................................... PERSONAL. 408.257.1746 1024:669687 catalyst(a)netcom.com

2 1

Re: How Many Games of Chess?
by pcw＠access.digex.net 17 Dec '03

17 Dec '03

> >This is tangentially related to crypto. I've been reading A.K. Dewdney's > >_The New Turning Omnibus_ recently to refresh my memory of all that stuff > >I learned in undergrad that I'm going to see again on the Comp Sci GRE > >shortly. :-) Anyway, I was glancing through the chapters on complexity, > >computabilty, and minimax trees, and I got to wondering something: how > >many possible games of chess are there? I know that it has to be a finite > >number, but I'm not sure how to go about finding this number. Any > >pointers would be appreciated. > >First, I think there are a finite number of games only if all stale-mates >are are required to terminate. There is that curious rule that ends a game when the same board position occurs three times in the course of the game. I wonder if there were any real cool endgames where the underdog was able to manipulate the overdog into repeating the position three times? Peter Wayner * 4129 Roland Ave. #1B, Baltimore, MD 21211-2038 410-366-1452

1 0

The President's Analyst
by jim＠bilbo.suite.com 17 Dec '03

17 Dec '03

I saw a movie last night called "The President's Analyst". The movie was made in the mid 60's. It's an action comedy that stars James Coburn as the President's psychiatrist who sneaks away from the job because he doesn't like it. Most of the movie consists of silly scenes of spies from the world's major countries chasing after Coburn under the assumption he knows all the President's secrets. At one point in the movie the Russian spy is talking to the US spy... Russian spy: You mean all the phones in the country are tapped? But this is America, not the Soviet Union!! It's a moderately funny movie that contains more truth now than when it was first shown. I recommend it as a cheap laugh and somewhat relevant to today's issues. Jim_Miller(a)suite.com

1 0