UNCLE BERNIE'S CODEBREAKER GAME FOR APPLE-1

18 posts / 0 new
Last post
Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
UNCLE BERNIE'S CODEBREAKER GAME FOR APPLE-1

 

UNCLE BERNIE'S CODEBREAKER GAME FOR APPLE-1

 

This is a fun little game that once was very popular in the 1970 in various forms. Objective of the game is to guess a secret code of the opponent. Most of its numerous variants and knockoffs appear to have been inspired by the commercial game "Mastermind" which used colored pegs on a small game board so you had to think in colors. On the early programmable calculators like the HP-67 and the TI-59 you had to guess a number, much like the "Bulls and Cows" game that predated "Mastermind" by maybe a century. When played with pencil and paper the secret code was preferably a four letter word, limited to the first few letters of the alphabet to make it playable.

 

The latter is the variant that was found in numerous incarnations in many computer magazines of the 1970s and 1980s as a type-in listing, mostly in BASIC, and ad nauseam. As if every BASIC beginner would have wanted to tackle this game to demonstrate their newly acquired programming "skills", and ruthless editors, wanting to fill the pages of their otherwise boring advertising rags, accepted and printed that crap, and I mean "crap", because none of these beginner grade programmers had ever figured out how the computer could guess a "secret code word" made up by the human player. It still eludes me how we could have cherished all these computer magazines so much, back in the day. I still have some, and if re-read now, they look bland and trivial to me. This even applies to the once famous BYTE magazine. I have all the issues from the beginning to December 1978. Bought recently, off Ebay, of course. When I was a teen I could not afford to buy them, and I had to go through the ordeal of a  long tramway and then a subway ride to the city's main train station where there was an international book store which had them. There I would browse through the most recent BYTEs until I got shown the door. There were (and still are) a few gems in those early BYTE magazines, though, unlike most other such magazines of the time. Most magazines catering 8-bit computers died in and after the year 1988, and good riddance. BYTE morphed into a product review / advertising "telephone book thick" monstrosity targeting the PC crowd. Still, they had some gems from time to time. I remember their great in-depth articles on the first RISC CPUs --- all now gone and buried except the ubiquitous ARM. I wish I had those BYTEs in my collection.

 

WHY AND HOW I CODED THIS GAME In THE 1970s

 

Back in 1976, when the Apple-1 came out, which I did not know of, as I was a young teenager, I itched for a KIM-1. A classmate had one because his dad, a mainframe computer professional, had bought it out of his own curiosity. But my dad was busy designing rocket engines for a defense contractor so there was no way to talk him into buying me a KIM. And my pocket money and savings just had been depleted by building a digital clock of my "own" design (well, schematics taken from a book and modified for the TTLs I had desoldered from computer scrap - I only had to buy the type 7447 decoders, some 7490 counters, the crystal, and the 7-segment displays).

 

So I proceeded to design and build my own 8080 based computer with much the same functionality of a KIM-1. Having no money makes inventive minds ! The 8080 and the 2708 I got as a gift from an uncle of mine who designed telecom equipment - towards Fall 1976 they already were throwing out these obsolete three supply voltage parts from their lab drawers right into the scrap bin. But the 2114 RAMs, the 8224 clock generator, and the 7-segment displays I had to buy myself. The TTLs, again, were salvaged from computer scrap. So it became 1977 until my own 8080 based KIM-1 knockoff finally came to life. It was a weird design unlike anything ever seen in magazines. There was no 8228 system controller IC - too expensive - and due to lack of any 74138 decoder which never had appeared on any salvaged PCB the keyboard port register occupied the whole upper 32 kBytes of the 8080's address range. Hilarious ! There was no way to expand its memory. It was forever stuck at 1 kByte of RAM and 1 kByte of EPROM. My "reasoning" was that I could not afford to buy more 2114 ICs anyways. But still not bad for a teen designing his first computer. And like Woz, I learned from the experience and never made the same mistakes again. I think without the lessons learned from the disastrous Apple-1 his Apple-II would have been as terrible as most other flawed early 8-bit microcomputers you probably never heard of because they flopped and bankrupted their manufacturers. The Apple-II, however, was a sound design that was innovative and avoided all the shortcomings of the Apple-1. So it became a stellar success !

 

But back to my 8080 based contraption. Its 1 kByte machine language monitor even had a sort of "mini assembler" using labels as branch targets - I feature I had seen in the HP-67. And the first game I wrote for this machine was "Codebreaker". And yes, the player and the computer would take turns in guessing the secret code of the opponent. I had figured out an algorithm how the computer could do that with spooky efficiency. Little did I know that me, as a teen, may have matched, at least somewhat, the famous Donald Knuth with that feat. He analyzed the game in the same years, 1976 and 1977. But of course, him being a real scientist, his algorithm was far more sophisticated than the mine as he added a minmax search after the first steps needed to find a reasonable guess. So his algorithm always guesses in an optimum way. My algorithm does not do that. The human player would stand no chance if it were so, and quickly get fed up and toss the game into the digital trash can. I kept it simple and stupid even in this incarnation of the game for that reason. Any game should be fun for the human player, and not bring frustration.

 

REDISCOVERY OF MY OLD CODE

 

Just recently, when rummaging through my old notes trying to find the schematics of my 8080 computer, I found the core algorithm written by my younger self in 8080 assembly code almost half a century ago. So I decided to rewrite it in 6502 assembly language targeting the Apple-1. It is one of the few types games that is not hampered in any way by the Apple-1's incredibly slow and functionally limited video section:

 

 

While I was at it, I also experimented with some additional code which would make the same binary run on both the Apple-1 and the Apple-II, and on the latter, to faithfully emulate the look & feel of the Apple-1 as far as the screen output is concerned. But as none of my real Apple-II in my collection work anymore, I had to try it on a clone that was made in Taiwan in 1986, which still works without a flaw, after all these 35 years. So I don't know if my code works on any real Apple-II or not. If you have an Apple-II which works, please try it out and give me feedback ! And tell me which Apple-II you ran it with ! If I'm right with my observations I made while coding this game, which is the first program I ever wrote for the Apple-II, the Apple-II did inherit a lot of "genes" from the Apple-1 on the machine language monitor / machine language API level, far more than you would think. If I'm wrong, the game won't run. But it did work on the clone !

 

HOW TO DOWNLOAD AND USE THE GAME

 

You can find the game's manual pdf  in the download section ("Attachments") below to if probe you may like it. If so, then download one of the zipped files: for the Windows world, use the codebrk.zip file, for the Linux world, use the codebrk.gz file, which I had to rename from .tgz to .gz due to Applefritter's website not supporting the tgz file type. You should rename it to tgz before invoking gunzip.

 

The zip files contain, among other files, an AIFF file for any media player to generate the audio stream you can feed into the cassette TAPE IN port of either the Apple-1 or Apple-II.

The source code is not included, sorry. I don't want to embarrass myself with my poor programming. It does work (I believe) but it is incredibly ugly and inefficient. The core algorithm was written by my teenage self, remember, and so it is far from what I could do today in terms of efficiency and elegance. While I recoded it for the 6502 I saw how utterly inefficient the "evaluation" code was. The translation made it even worse. But it works !

 

BEWARE THE MONO / STEREO CABLE TRAP !

 

You should be able to use any audio player but be aware that if you use STEREO audio cables with the MONO inputs of these vintage machines, or MONO cables, one STEREO channel of the player may very likely get shorted to ground (the one on the "ring" of the STEREO plug). If the output amplifier of your audio player has no good built-in short circuit protection then it may get damaged. To play it safe, I recommend you to make a pair of cables specifically for use with the Apple-1 and Apple-II: take one factory made STEREO cable (they are the cheapest, MONO cables are rarer and hence, more expensive) having STEREO plugs at both ends, cut it in half, and install a MONO plug on the end(s). Only connect ground return (the shield) and the one STEREO channel which goes to the tip of the STEREO plug. This one channel connects to the tip of the MONO plug. Now, you have made two special cables for the Apple-1 and the Apple-II and as long as you plug the MONO plug into the Apple, and the STEREO plug in your media player, nothing bad can happen. Here is a photo of such a cable:

 

 

SOME PROBLEMS I'VE SEEN

 

On Windows 7, and on my notebook, the media player is a piece of crap as it sometimes makes audible gaps during playback, and the load will not work. It helped to close all open windows including the media player and restart the media player only. You can listen to the audio for these gaps in case the load fails again. Rinse and repeat. I had no such problems with the media player of Linux Mint. Seems Windows 7 is still not really able to do real multitasking. Even a web browser can freeze the machine up.

 

When loading on POM1, the Apple-1 emulator, if you want autostart, load the 'codebrk.apl' file with CTRL-L and then the "emulate keyboard entry" option. But this takes a long time to load unless you dial up the output speed. It's better not to use he "emulate keyboard entry" option and give the start command manually: 800R <return>.

 

If you find any other quirks, let me know.

 

Comments invited !

Offline
Last seen: 3 hours 7 min ago
Joined: May 4 2021 - 06:35
Posts: 32
Hi Uncle Bernie,just yo let

Hi Uncle Bernie,

just to let you know that, if you are happy with that, I've  added your Codebreaker and your RAM Challenge programs to the Apple-1 Juke-Box ROM-PACK, along with other useful stuff.

It will be available for free download in the next few days, informations will be released soon.

 

 

Thank you,

Regards,

Claudio - P-LAB

Macintosh_nik's picture
Offline
Last seen: 2 hours 6 min ago
Joined: Jan 8 2021 - 05:18
Posts: 121
Hi Uncle Bernie!

Don't use the built-in Windows 7 player, install the free VLC player. I have almost all of my Apple-1 software loaded with it. Before, I tried to load software from my smartphone, but nothing else loaded except Basic, Mastermind, Apple 30th and a couple of other programs. Strangely enough, I had been transcoding Apple II software from .dsk to .wav for several years and writing floppy disks directly from my smartphone without any problems.

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
In post #2,

Claudio wrote:

"just to let you know that, if you are happy with that, I've  added your Codebreaker and your RAM Challenge programs to the Apple-1 Juke-Box ROM-PACK, along with other useful stuff. It will be available for free download in the next few days, informations will be released soon."

 

Uncle Bernie answers:

 

Sure, Claudio, go ahead ! I coded this game for people to actually play it and to have fun with it, and not to have it sit around in a forum and nobody doing anything with it.

 

But please add a link or so in your documentation so people can find the pdf with the game's manual. Or make the pdf downloadable from your website (if you have one). A link to this Applefritter thread also would be nice so people can look up the history of this game as told by yours truly. I know it's long and convoluted but I had to write it up to show that this game, due to its historical roots, is very much "period correct" for the Apple-1, 1976-1977.

 

The more people play this game, the more happy I am !

 

I noticed your jukebox address range is one byte more. Which would be the Apple-II style checksum at the end of the recording. Did you extract the code from the AIFF file ? Or how come that added byte appeared ?

 

 

 

 

Offline
Last seen: 3 hours 7 min ago
Joined: May 4 2021 - 06:35
Posts: 32
Hi,no problem, I'll add PDF

Hi,

no problem, I'll add PDF and links to this thread.

About the extra byte: it's perfectly normal.

Juke-Box Program Manager always shows the Start Address and the first free Address... "it's a feature, not a bug"...   :-D

 

My plans are to release the ROM-PACK by the end of the day, I'll open a new topic for that.

 

Thank you,

Regards,

Claudio - P-LAB

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
One omission from the manual...

... I did not mention how to correct input mistakes because it is the same as with the Wozmon: hit ESC to purge the current user input and start over. You even get the same '\' prompt. However, once the 4th character of any input group is entered, you can't undo this input group anymore. But so far I never needed that. Mistakes are rare and usually happen in the first three input characters.

 

Maybe this should be added to the docs but Applefritter does not allow to change anything after it's posted, sorry. I did not see any issue with not mentioning this because any Apple-1 user who really uses the machine should know about the ESC key and how it works.

Macintosh_nik's picture
Offline
Last seen: 2 hours 6 min ago
Joined: Jan 8 2021 - 05:18
Posts: 121
Hi Uncle Bernie!

 

Great game, I did not immediately understand how to play, but I figured it out. Can't win yet, but it's only a matter of time. Thanks a lot! If there is something similar I would be very happy to test it.

 

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
Some Tips & Tricks (hints) on how to play the 'Codebreaker' game

Hi Macintosh_nik -

 

thanks for your post #7 praising my 'Codebreaker' game, and let me give you some hints !

 

(WARNING: long post ! Don't read unless you want to learn the fine points of the game !)

 

First of all, as spelled out in the manual, the responses don't give positional information where the 'matches' are. Your responses to the computer look as if you put the response character in the same place where the corresponding 'guess' character is. This is fine, you can do that, but the computer will not use this additional information: it just counts how many '*' and '+' are in the response, and builds its next guess from this information. So a response like '*-+*' is the same information as '**+-', and this is how the computer makes its responses: '*' (the 'long' flashes in the spy story) come first, then the '+' (the 'short' flashes), and the '-' are just fillers to complete the input group.

 

Secondly, you can't win against the computer if you use weak guesses which do not exploit all the information on the table.

 

For the sake of completeness in this post, let me repeat your first three guesses and the responses from your screenshot (which is way too large, BTW, please don't do this again, it ruins the whole thread for all people with third-world internet connections, like here in the USA, if you don't want to pay "their" usurious rip-off prices nor their foul tricks and their fraudulent billing in case of fixed data rates --- gangsters, all of them !).

 

OK, here are your first three guesses and the responses of the computer:

 

       BEEE <---- the secret code shown for sake of this discussion

#01 ABCD  +---

#02 BAEF  **--

#03 BEFA  **--

 

Your first guess was ABCD and the response was +---, so one of the four characters has a match but is not in the right place. This guess is OK as it causes no contradictions with previous guesses - there are none yet. But still, it is a questionable first guess. In chess notation, you would comment this move as "!?" - but after the response is seen, you were quite lucky as it gives you a lot of information.  Because you were lucky - not because it is a good guess.

 

Before I get to this, let me give some advice on making the first guess, which is critical: scientists have proven that the game can only be solved in minimum number of steps if the first guess is in the form AABB, or any other combination of two randomly chosen pairs of letters, such as EFFE, or DADA, all equivalent in strength. But for some specific subgroups of all the possible code words, these are not the best start. However, you can't know which subgroup the secret code word belongs to, so the mentioned strategy for the first guess still is optimal.

 

Now about the information from your first guess. One letter has a match but it's not in the right place. You also know now that three of these four letters don't exist in the secret code word. You just don't know yet which of them is the 'right' one. But you know, if i.e. 'A' is the right one, then 'B' and 'C' and 'D' can't be part of the secret code. So it makes no sense to have any further next guess with 'BA' in it. 'B' would exclude 'A' and vice versa. If 'C' would be the right one, there can't be no 'A', no 'B' and no 'D'. At this point you could roll dice which letter you probe as the 'right' one in further guesses, any choice is good. But then, you have only one letter. You need three more ! Since the set of letters in the "rookie" level is A,B,C,D,E,F and the first four have been probed and only one match was found, the remaining three letters must be a combination of the yet unprobed letters 'E' and 'F'.

 

I think you correctly had concluded this because your second guess has 'EF' in it. Smart move ! But if 'B' is there (your valid random pick ?) then 'A' can't be there. So a more efficient second guess would have been BEEF. Or BFEE. There are eight possible optimum second guesses if you assume 'B' was the letter that matched in the first guess. Since you can't know at this early stage of the game which of the four letters did match (you just were lucky in this case to pick the correct 'B'), there are 4 x 8 = 32 possible optimal second guesses. There are 6 ^ 4 = 1296 possible secret code words. This is quite a reduction in search space ! It even gets more important in the higher difficulty levels.

 

All this information can be extracted just from the first guess.

(Wow !)

 

You might now wonder (if you are a programmer) how the hell can this kind of reasoning be programmed into a computer and in only 2 kByte of code. It eerily reeks of "Artificial Intelligence". Which is impossible to do on a humble 6502 and in a mere 2 kByte. Well, let me tell you the 'secret': like most "Artificial Intelligence" programs it has nothing to do with machine intelligence, but with brute force. If I wanted to be snarky I would say the game's algorithm is a swindle, a fraud, as all the other ""Artificial Intelligence" hoaxes done on computers since such machines exist. Remember the 1960s "ELIZA" program which could converse with you in normal English language and which pretended to be a psychoanalyst for you, the patient ? It was so stunning that people really believed the computer is intelligent and cares for them. Not so. It was a hoax. But it worked, at least on the weak of mind ;-)

 

So how is it done in this game ? Please let me take a brief detour into the real world of codebreaking to show you the similarity of this fine game with the real thing. Did you know that the German WWII cipher machine, the famous "Enigma", had a fatal design flaw which allowed to break its code relatively easily, and that this fatal design flaw was the key "inventive feature" they had got the patent for ? Isn't that hilarious ? This feature is the "reflector plate" at the end of the scrambler disk stack. The electrical signal goes through the scrambler disks and unlike earlier cipher machines does not go to the lamps from there, but is reflected back into the scrambler disks and then goes to the lamps. The (very stupid) idea was that now instead of having the signal being scrambled by i.e. only three disks, it passes though the three disks twice, allegedly giving better scrambling as if there were six disks. Or so they argued. A fallacy ! A fatal mistake ! Because this "innovative feature" made the Enigma unable to encode any letter to itself, i.e. a 'B' never could turn into a 'B'. And this was the feature the Bletchley Park Codebreakers used to stop the search for the secret code word in their codebreaking machines. These machines simply tried all possible starting positions of the disks (the "key"). Whenever a tape with ciphertext ran through without decoding any letter to itself, the process stopped and a bell rang. Then a human operator would note down the candidate encryption key and restarted the machine to look for more candidates. The candidate encryption keys were then probed manually on clones of the Enigma if they would produce good German cleartext and not just gibberish. With this method, the Brits could decipher almost all "secret" Enigma messages within a few hours. Which changed the course of the war in a big way. Without these great codebreakers of Bletchley Park, all of Europe, down to Gibraltar, now would speak Russian and be part of the great Soviet Empire. Japan ? They had a super lousy cipher machine, too, which was far more complex than the Enigma, but much easier to break, and the Americans broke its code early in the war. Lesson learned:if you design a cipher machine, keep it simple, so you can understand how to break it. I would not use a cipher that has not been broken.

Because if it has been broken, it has been understood, and all you need to do to make it useful again is to increase the key space so they can't break it anymore in a useful amount of time (not possible to make this improvement in all cases, but then the cipher is trash anyways and always has been trash, like Keeloq). Any cryptographer knows there is no "safe" encryption. There only are ciphers which have been broken and those who have not been broken yet. Some have built-in backdoors obscured by complexity. (search for Crypto AG scandal). Buyer beware !

     

Now you can see the similarities between the game and the real world. To find the secret code word (the "key" in real world cryptography), you search though candidate keys and weed out those who cause contradictions with any prior information found. Within my game code there is an algorithm which, like the Bletchley Park codebreaking machines, cycles through all possible combinations of letters and then looks for contradictions with the results of previous guesses. If such a contradiction is found, then this letter combination can't be the secret code word. It is discarded and the next one is taken. Rinse and repeat. Once there are no contradictions, a valid guess has been found and is presented to the player.

 

Now, knowing this codebreaking method, let's apply it to your second guess:

 

If the second guess BAEF is the secret code word you seek, which result would your first guess have had ?Let's see:

 

#02 BAEF <---- assume this to be the secret code word.

#01 ABCD ++-- 

 

Hmmm. You see the contradiction ? BAEF can't be the secret code word because for your first guess, ABCD, it did not generate the same response, +---. So your 2nd guess has a fault. And this fault makes your guess weaker.

 

Another example: your third guess is BEFA. If that is the secret code word, which results would it generate for your first two guesses ?

 

#03 BEFA <---- assume this to be the secret code word.

#02 BAEF *+++

#01 ABCD ++--

 

But for your first guess the answer (seen at the beginning of this post) was +--- and for your second guess the answer was **--.

So BEFA can't be the secret code word and if used as a guess wastes chances again. Besides, it has the same fault as your first guess, having both 'A' and 'B' in it. One of them must go.

 

This is how the computer "thinks". All candidate guesses, by the rules of the game, must generate exactly the same responses as all previous guesses did, if the candidate guess is used as the unknown secret code word. And if all possible candidate guesses are exhausted and all of them had a contradiction, there is no valid solution and somebody has cheated.

 

Of course, this is a mechanical approach, an algorithm, suited for computers. The human brain is smarter and can use better reasoning, like I have demonstrated in the discussion of your first guess, how certain letters can be quickly excluded based on a given response.

 

Although all of this looks deceptively simple, it is not so. This game has been studied by real scientists and cryptographers over many decades and it is a deep rabbit hole to invest time into making conjectures and proofs about it. Although it is trivial to calculate i.e. the number of possible secret codes, it is not trivial to mathematically prove how many steps, on average, are required to guess the secret code. It also is not trivial to program a really "optimum" algorithm for this game: it is more difficult than the minmax search used in chess programs, for instance. This may be surprising, but unlike the game of chess, where all the facts are on the board (literally), this game deals with unknowns and probabilities, and this makes it much more difficult to tackle it in a computer program. So I did not do that, I just kept the algorithm to the bare minimums. Otherwise I would have wasted too much of my precious RQLT and you would have zero chance to ever win against the computer !

 

Like with any game of strategy and reasoning, this one also has a learning curve, but it is steep and quick. Once you know the above "secrets" and pay attention to them while you play (don't allow yourself mental lazyness and poor guesses), then you will soon be in par with the computer, and have a lot of fun playing the game.

 

Just a footnote to close the above: the "official story" of the "Mastermind" game on Wikipedia states that its inventor, a certain "Mordecai Meirowitz" worked for the Israeli Post Office. As "Postmaster" and "Telecommunications Expert". Sure. Do you believe this is the whole story ?

 

Let me tell you my conjecture: historically, long before email did exist, many nations were hiding their codebreakers / cryptographers in their government's postal services. The proximity to millions of letters which sometimes may have contained secret codes of foreign spies operating in the country is an advantage. Once the spy ring is under observation, it's easy to fish out their letters from the stream, open them, and copy the ciphertexts for later decryption, and then close the letters again and put them back into the stream.

 

So, in my humble opinion, it's highly likely that Mr. Meirowitz was a real codebreaker, possibly working for a branch of the Mossad. Despite the process has been simplified as much as possible to make the game suitable for kids above the "age of reason" (in some religious circles, 7 years old), it has so many similarities with the real world codebreaking process (although at a beginner level) that it is highly unlikely the inventor was only a normal postal clerk. But as said, this is only a conjecture of mine.

 

Offline
Last seen: 3 hours 7 min ago
Joined: May 4 2021 - 06:35
Posts: 32
This could easily become the

This could easily become the most played, loved and at the same time hated game for Apple-1.

I love it, I'm thinking of integrating it into the FW of  the "RetroShield 6502" on my desk so I don't have to boot the Replica every time I want to play.

:-D

 

Cheers,

Claudio - P-LAB

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
Uncle Bernie's response to post #9:
 
p-lab wrote:

"This could easily become the most played, loved and at the same time hated game for Apple-1."

 

Uncle Bernie answers:

 

You are probably right. Even back in the day, in the early 1970s, when Mastermind became popular, the smart kids loved it and the dumb kids hated it. The only difference today, almost half a century later, is that the smart kids turned into smart adults who have (or had, if retired) a well paying job and hence can afford to build an Apple-1 to play the game, while the dumb kids of the 1970s turned into dumb adults who never had a well paying job, who can't afford to own an Apple-1, and, most importantly, as long as they are drunk, or under the influence of drugs, fat, lazy, diabetic from junk food on their couch in front of their huuuuge flatscreen TV which spouts mental diarrhea and propaganda 24/7, they could not care less what an Apple-1 actually is. They might have an iPhone, though, because of status symbol and such. But they would never, ever consider to play this game, not even once, as it requires brains.

 

So, my money is on "most loved" and maybe a little bit of hate, for a while, until the player has mastered it. I know how it feels to lose against a computer in such an apparently simple game. But when mastered, especially in the higher levels, you actually can win most of the time unless it's a draw, which happens quite often in the higher levels but never should happen in the "rookie" level. You just need to play it with mental precision, without any wasteful guess. Then you have better chances to win than the computer, because your move comes first.

 

All this can be proven mathematically, of course, but designing such a proof is beyond most mathematicians and computer scientists, even if they have a Ph.D. --- so this apparently simple game is not trivial at all.

 

It's a really fine game that can be run on very limited hardware and still be fun and challenging to play ! The first fully functional version I had ran on my 8080 machine which had 1 kByte of RAM and only a six digit 7 segment display, much like the KIM-1. I fondly remember how exciting that was - such a small machine and being so "smart" to guess the player's secret code so efficiently. Nobody else had accomplished that at the time being. My previous attempt to make the computer guess the secret code, programmed in BASIC on the WANG2200S of my high school, had failed miserably, because it was far too slow. But the algorithm as such was tested there. So at least the WANG was good for something. My Assembler for the 8080 also ran on it but soon I found that coding in 8080 machine language was more efficient for me (because of the time on the WANG had to be booked and was scarce). The only significant improvement (other than adding the text I/O) for the Apple-1 version was the "permanent brain": the computer thinks while you are thinking. This was the last missing piece to perfect the game.

 

Macintosh_nik's picture
Offline
Last seen: 2 hours 6 min ago
Joined: Jan 8 2021 - 05:18
Posts: 121
Hi Uncle Bernie!

Thank you for your detailed tips on playing Codebreaker, they were very helpful to me. It took me about 2 hours to win, and that's probably because the code was simple with 3 of the same letters. So the second name of this game is "Time Snatcher". There is a question: if the word I riddled has only one letter A, and the computer makes the assumption of two, what should I answer him? Suppose A is not in its place, so +, but the second how? I ask because your game several times defended me "technical defeat" and called a cheater!

By the way, I remembered playing a similar game in a pioneer camp in 1988. I think it was called "ram", we played against each other and the answers were written on a piece of paper, Soviet pioneers did not have computers. I remember the year very well, because I was a very short pioneer, in the spring of 1988 I was the last in my class to take the oath, in the summer I went to a pioneer camp to help fight for the harvest, and the next spring I was kicked out of the organization because I was a bully! Luckily after a few months there was no Pioneer Organization, no USSR, so this did not affect me in any way in the future.

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
Clarification of the "rules":

In post #11, macintosh_nik asked:

 

"If the word I riddled has only one letter A, and the computer makes the assumption of two, what should I answer him? Suppose A is not in its place, so +, but the second how? I ask because your game several times defended me "technical defeat" and called a cheater! "

 

Uncle Bernie answers:

 

If you look at the wiki page for Mastermind and follow the links to Donald Knuth's paper on the game, he noted that even the manufacturer of the game was obviously unable to state the rules for the '+' matches in an unambigous way.

 

I tried my best to word it more precisely in the manual I wrote but maybe this is another failed attempt to clarify the rule.

 

Let me try to explain it:

 

Simply put, once a letter has any match, BOTH these letters in the guess and in the secret code can't produce any other match anymore.

 

Here is a method I recommend until you can do it in your head:

 

Write your secret code word on a piece of paper. Make a line below it. Write the computer guesses just below your secret code word. Now compare each letter position for a perfect match and make a circle around the matching letter of the computer guess. Example:

 

        abcd____

#01  CBBA

         ^

I marked the "perfect match" with a '^'  in lieu of the circle and I used lower case for the secret code word to allow us to distinguish the letters. Here, we have one perfect match, the 'B' with the 'b', which makes one '*' in the answer.

 

So far, so good. We then look for the non perfect matches (correct letter but at the wrong place), from left to right in the guess: 'C' is matched with 'c' (gets a '+'). We skip the 'B' in the second position as it was a perfect match.  The 'B' in the third position would match with the 'b' but this 'b' was already perfectly matched (seen by the circle on the corrsponding 'B' below it). No letter can be matched more than once, so we don't give a '+' here, but a '-' (miss). Another way to look at it is to say: there is no second 'B' in the secret code word, hence, the second 'B' is wrong and is a "miss". Finally, the 'A' has a match with 'a', which still has had no other match, and earns another '+'.  So the response is: *++-

 

To play it absolutely safe, you can use the circles on BOTH perfectly matching letters, and then cross out any further matches which generate a '+' in BOTH the guess and the secret code word letter so as to avoid any further (illegal) match on this letter pair. This is how the computer program does it. It works on nibbles (4 bits) for each letter position and if there is a match, it will set the highest bit of both matching nibbles (one nibble each in the secret code word and in the guess) to avoid any further match of these letters. This is used both in the creation of the computer's response to the player's guess and in the thinking process of the computer. And this is the reason why there are no more than eight possible letters ...

 

Alas, on a piece of paper, unlike the bits in the computer, you can't delete the markings on your secret code word anymore, so you may need to write it down again to be "clean" before the next computer guess.

 

This complication - which however is no problem anymore once the player is experienced - may have been the reason why the original "Bulls and Cows" game did not allow repeat letters: each letter can appear only once in a group of four. So no "BAAA" ! But this makes the game more boring and less challenging.

 

To close this topic, you may also have been accused by the computer unjustly. The current version of the game has a bug which causes every 6th guess of the computer to break and then the computer can't find the solution and accuses you of cheating. I discovered this bug just yesterday evening (yes I do also waste a lot of time playing this game).  Since I can crack most of the computer's secret codes in 5-6 guesses (even in the highest level) and with some exceptions the computer could guess my secret code in just 5 guesses (only a few constellations need more guesses), I did not see this bug any earlier. The remedy is described in the next post (which will be #13 - superstition ?) ! The bug is already fixed !

 

 

 

 

 

 

 

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
Uncle Bernie found a bug, sorry ! Call for beta testers !

I love to play this game myself and I have played it for months almost daily while I was working on my toolchain.

 

And I believed it to be bug free, which it once was, until the very last "polished" version. In which I foolishly have planted a bug that is not immediately obvious. This came about when I changed the begin address of the zero page addresses so as to avoid collisions with Apple-II systems software. For the Apple-1, this change was not needed and for the Apple-II it was just nice to have. But after changing that begin address from $28 to $60 and a re-assembly the "bunch of spies" hiding in the computer may falsely accuse you, the "Master Codebreaker", to cheat ! Which happens only if the computer needs a 6th guess. Each 6th guess of the computer fails and hence, the false accusation of cheating. Unfortunately, even in the higher difficulty levels, it is quite rare that this occurs. Even in "Genius" mode I can guess the computer's secret code in only 5-6 guesses most of the time and unless I "cheat" and make up my own secret code word on the fly (but still following the rules !) to slow the computer down, it will correctly guess my own code word in just 5 guesses (or less) most of the time. So it rarely needs a 6th computer guess which always is broken. In the "Rookie" mode it is exceedingly rare that this bug strikes, so most players may not have noticed it yet (or scratch their heads which part of the rules they don't seem to understand).

 

Finding the root cause of the bug and fixing it was a matter of a mere five minutes, I just had to undo the last change and the bug was gone. But this would not work all too well on the Apple-II (which was the reason for this last "polishing" step). To keep the $60 begin address for the game's zero page variables, I had to move the computer's guess/response table to the beginning of this block, so it would not cross the $80 threshold after which no computer guess can work (which happend to be the 6th guess/response slot, addresses $82, $83, $84 in the bug-ridden version).

 

But before I go through the tedium of updating the tarballs and post them I would like to ask those of you who still like the game to act as beta testers for this - hopefully - bug-free and "final" version. I do not believe in the "Banana Strategy" for software development used by many of the big corporations ("Our software ripens at the customer !") but being a one man show with no beta testers and limited RQLT to spend I can't always meet the high quality standards I normally have for my own work.

 

So, dear prospective beta testers, please contact me via the Applefritter message system and I will send you a binary and .apl file of the corrected version. After I got the OK of all of you, I will make new tarballs and upload them here.   

 

 

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
More info about the 'Codebreaker' game strategy

Hi 'Codebreaker' fans !

 

Some of you have contacted me to publish the bug corrected version, while others wanted to know more about the strategy to beat the computer. A few have accused me to brag because I claimed I can beat the computer even in the 'genius' level and they could not do beat it by themselves (the fallacy, of course, is to assume everybody else must be dumber than oneself is).

 

All this got a bit too much to answer individually (I did not expect so much resonance for this small and simple game).

 

To address and answer these questions, here are my responses:

 

a) the bug corrected version is still in beta test. I do not want to repack all the tgz files and post yet another potentially buggy version. The corrected version must be bug free ! So please be patient and play the 'Rookie' level where the bug rarely manifests because in 'Rookie' level the game can be solved by a good human player in no more than 5 or 6 guesses, so it never comes to a 6th guessing attempt of the computer, which has the bug.

 

b) I need more beta testers. Anyone sending me a message via applefritter's message system asking to become beta tester will get the corrected 'Codebreaker' version for beta test (at the moment only AIFF files available, so you need an ACI card).

          

c) I have attached a screenshot which shows how to beat the computer in the 'Genius' level.It shows my proven strategy. With this strategy I can beat the computer often enough to be in par with it. You can do the same. (Now don't accuse me again of swindle, because it's only one match, just be assured the strategy is sound).

 

Here is the screenshot:

 

 

My recommended strategy seen in the first three columns works as follows:

 

In the first few guesses I try to find out which letters are in the secret code word of the computer and which are not there. I do not care too much about letter positions yet. And I do not re-probe any letters unless I know at least three of the four (but still, I don't care about their positions).

 

You can see a general scheme in my first three guesses: AABB, CCDD, EEFF. Using pairs is important. Order is not important. In this example, after three guesses I know that three letters out of the set A, B, E, F must be in the secret code word, and I know that there is no C and no D in it. I also know (thanks to the pairs) that there is no second A or B otherwise the answer to guess #01 would have been **-- or *+--). Letters G or H have not been probed yet.

 

At this point it would be inefficient to guess GGHH to probe these. The answer would not make me much wiser, only a little bit, which is not enough information gained for one guess spent. So I try to maximize the information I can get out of the 4th guess. I could use any combination which fits all of the above criteria. But I don't know enough yet about E and F. The secret code word could contain EE, EF, FF (from guess #03). So I chose FF to be able to find out which of the three possibilities apply. (I also could have chosen EE or EF - this is the random element in the game, but despite being random, every proper guess in such a situation has the same chance to win). Since the answer #03 means that that if the FF produced the two '+', they can't be in positions 3 and 4 (otherwise there would have been two '*'), so the the new guess must have FF in positions 1 and 2. If this is correct, then none of the A in guess #01 could have generated the '*'. So another letter that must be in the secret code word is B. It can only be put into positions 3 or 4 of guess #04 because of the FF already in positions 1 and 2.

I randomly chose position 3. This leaves one empty position 4. For which each of the yet unprobed letters G or H may be chosen. I randomly chose G. (Note that there could be three E or F in the secret code word. But I'm not done with eliminating G and H yet, and elimination of letters has priority over everything else.)

 

So guess #04 shall be FFBG. I verified it against the answers of guesses #01-#03 and if FFBG would be the secret code word it would indeed have generated the same answers. So FFBG is a good, efficient guess.

 

The answer is *---. Oops ! Bad luck ! Three '-', so three of the letters in the guess must be wrong, they are not in the secret code word. Now I know for certain that it has no two F (otherwise there would be more than one match). So at least one F must be thrown out, which due to response #03 means an E must be substituted for it. Meaning we have an EF somewhere.

 

If an EF is in the secret code word, the '*' in the answer for guess #04 must have been one of the F's. This also implies that both B and G of guess #04 must be wrong and not be part of the secret code word. Which means that due to the result of guess #01, an A must be either in position 1 or 2.

 

Then, again from guess #04, a 'F' must be in positions 2 or 1. So the possible choices are AF or FA. I randomly chose FA for the first two letters of my next guess, #05.

 

An E also must be in there since I decided for EF. This E can only be at positions 3 or 4 (I chose position 3).

 

From all the above follows that the last letter of the new guess can only be the yet unprobed H.

 

So guess #05 shall be FAEH. Again, it was tested against all the previous responses and indeed it generates the same. So FAEH is a good, efficient guess.

 

Answer for #05 FAEH: **++.

 

I now know all the letters in the secret code word, which should be the case at this stage of the match. I know that two of them are not yet at the right places and must be swapped against each other.

 

By knowing all of the above facts, not all possible swaps make sense. For instance, neither A nor F could occur at positions 3 or 4, they must stay at positions 1 and 2. Same applies for E and H, which must stay at positions 3 and 4. If in doubt, you may re-read the above line of reasoning.

 

So now I know that either the letters of pair FA or the pair HE need to change places within the pair. Which pair needs the change I can't say. Again, a random choice, each of them being valid and having the same chances to be correct.

 

Im the example, I randomly chose to swap the last two, and - bingo ! - I won with my guess #06. Otherwise I would have won in the 7th round unless the computer would have correctly guessed my own secret code (CBGG) with its 6th guess (which inevitably would have happened, you can see this from the progress of its guesses when you apply reason and logic to them).

 

So it's not possible to win against the computer all the time, the odds actually are equal and the human player only has a slight edge because he guesses first. But most players squander this edge by suboptimum guessing, hereby lose tempo, and then the computer wins more often than it should.

 

You can greatly increase your chances to beat the computer if you 'cheat', as I have explained in the instructions pdf of the game. This is Uncle Bernie's evil little twist for this game, otherwise the rules have not been changed from the original.

 

The idea of 'cheating'  is to delay the progress of the computer as much as possibly by making up your own 'secret code' on the fly,  choosing responses which minimize the knowledge the computer gains by his last guess. Of course, you must eventually be able to arrive at a 'secret code' which yields consistent results for all the guesses of the computer - otherwise he will accuse you of cheating and win (to penalize you).

 

It also is unwise to be too stingy and use too many '-' as this will allow the computer to quickly eliminate letters.

 

So from time to time you have to throw him a bone. This is evident in my two first responses to the computer's guesses. Actually, his second guess is somewhat sub-optimal, but I deliberately allowed this to happen. While the famous Donald Knuth (and some lesser computer scientists after him) who have studied the game have given us optimum search strategies for guessing, it seems none of them ever had the idea the human player (or the computer) could cheat to slow down the opponent. So no strategy has been developed yet for optimum cheating. Maybe I will look into that when I have nothing else to do. This apparently simple game still asks so many questions ... and has not been fully explored yet, even after half a century.

 

Comments invited !

 

Macintosh_nik's picture
Offline
Last seen: 2 hours 6 min ago
Joined: Jan 8 2021 - 05:18
Posts: 121
Hi Uncle Bernie!

Your Codebreaker is fascinating, but not an easy game! Using your tactics from the post above I have several times determined the right letters, but the computer still always beat me by one move. I'll attach a photo, I don't know what rule I broke, but I was very close to winning. My word DEFA, played on the corrected version from your letter. Thanks in advance!

 

Offline
Last seen: 11 hours 55 min ago
Joined: Apr 1 2020 - 16:46
Posts: 252
Response to the previous post

Hi Macintosh_nik !

 

Thanks for beta testing my game !

Here is my comment on your screenshot:

 

The computer accusing you to cheat is justified. Your answer to computer guess #04 was -++*, or, if we order it, as would be usual: *++-

 

Note that the answer has NO meaning in the order, according to the rules of the game. In the spy story, long flashes ('*') first, then short flashes ('+') and the rest needs be filled up for which we use '-' ... maybe I should have taken blanks to make this point clearer. But now it is like it is. The game accepts any order, it just counts the number of '*' and the number of '+'.

 

But back to your 'cheating':

 

DEFA <--- your secret code

GDFA <--- computer guess #04

-+** <--- the correct answer. If you would order it as usual, you would have entered **+-

 

But you entered -++* as the answer. Wrong !

 

So you did cheat the computer, although I think it was not intentional. And I saw immediately that this can't be the bug of the 'bad' version because my thorough analysis of the bug has proven that it only occurs at the 6th computer guess, and not any earlier.

 

It also looks to me you did lose some tempo with your guesses #03 and #04. After your guess #02 you already knew three of the four letters in the secret code (to be more precise, various possible sets of three, not the exact set) so you could have started to move letters around while probing for the yet unknown fourth letter. This "moving around" would have given you additional information about which two letters were at the right places and generated the '*'.

 

The idea is to get as much additional information from each guess as possible. If you keep the guess pattern the same for too long, you don't get much additional information. In your example, I think you could have beaten the computer if you would have started shuffling letters beginning with guess #03. But, alas, your wrong answer to the computer guess deprived you from that chance.

 

This game is not difficult to play. Chess is much, much more complex. The difference is the random element, unlike Chess,  where all the information is on the board, with 'Codebreaker' you have to deal with unknowns. People who know how to play Chess (or any other board game lacking random elements) find this confusing at first, but after a while your brain will develop the addititional neural circuits needed to deal with these unknowns in a logical and systematic way.

 

So I could even blatantly claim that the 'Codebreaker' game makes your brain grow !

 

Which other computer game can claim such a beneficial effect !

 

So don't give up !  Continue to play the game and scrutinize (self criticize) your moves. With growing experience (growing brain cells !) you will start to see the inefficiencies of your guesses and you will get better and better. 

 

I know you can beat the computer because I did not put some known refinements into the computer's thinking process. It only uses the bare bones algorithm I had discovered as a teenager  and as you can see it does not even use the efficient probing process for yet unknown letters except in its very first guess.

 

This means the computer can't be smarter than you !

 

And if the computer ain't smarter than you, you will win !

 

 

 

 

 

Macintosh_nik's picture
Offline
Last seen: 2 hours 6 min ago
Joined: Jan 8 2021 - 05:18
Posts: 121
Hi Uncle Bernie!

Looks like there's nothing wrong with your Codebreaker game, and I've already learned how to win. By the way, I recently played another Codebreaker, only there you have to guess colors instead of letters.

 

Offline
Last seen: 1 month 1 week ago
Joined: Sep 27 2021 - 06:36
Posts: 7
Thanks Uncle Bernie!

I will definitely try this out as soon as I get my keyboard and encoder board for my Apple 1!

 

/Anders

Log in or register to post comments