Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #1022 > unrolled thread

Suggestions for improving speed of .SYS program.

Back to article view | Back to comp.sys.apple2.programmer

Contents

  Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-01 21:40 +1300
    Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-01 09:15 -0800
      Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-02 08:18 +1300
        Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-01 14:44 -0600
          Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-02 21:38 +1300
            Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-02 04:49 -0600
              Re: Suggestions for improving speed of .SYS program. Steven Hirsch <snhirsch@gmail.com> - 2014-01-02 07:26 -0500
                Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-02 18:23 -0600
          Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-03 21:42 +1300
            Re: Suggestions for improving speed of .SYS program. David Schmidt <schmidtd@my-deja.com> - 2014-01-03 08:15 -0500
              Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-03 10:26 -0600
              Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-04 10:47 +1300
                Re: Suggestions for improving speed of .SYS program. Michael J. Mahon <mjmahon@aol.com> - 2014-01-04 04:11 -0600
                  Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-05 12:53 +1300
              Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-03 23:55 -0800
                Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-05 13:58 +1300
                  Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-04 20:24 -0800
                    Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-06 11:11 +1300
                      Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-08 20:43 +1300
                        Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-08 15:41 -0800
                          Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-09 21:34 +1300
                            Re: Suggestions for improving speed of .SYS program. Michael J. Mahon <mjmahon@aol.com> - 2014-01-09 03:42 -0600
                              Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-11 17:12 +1300
                                Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-10 23:59 -0800
                                  Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-12 07:47 +1300
                                  Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-12 11:39 +1300
                                    Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-11 16:43 -0800
                                      Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-13 13:57 +1300
              Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-03 23:50 -0800
          Re: Suggestions for improving speed of .SYS program. ol.sc@web.de (Oliver Schmidt) - 2014-01-08 20:08 +0000
            Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-08 18:39 -0600
              Re: Suggestions for improving speed of .SYS program. Oliver Schmidt <ol.sc@web.de> - 2014-01-09 00:55 -0800
                Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-09 05:51 -0600
            Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-09 21:44 +1300
              Re: Suggestions for improving speed of .SYS program. Oliver Schmidt <ol.sc@web.de> - 2014-01-09 01:20 -0800
                Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-09 05:56 -0600
                  Re: Suggestions for improving speed of .SYS program. David Schmidt <schmidtd@my-deja.com> - 2014-01-09 11:09 -0500
                    Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-09 09:29 -0800
                      Re: Suggestions for improving speed of .SYS program. David Schmidt <schmidtd@my-deja.com> - 2014-01-09 12:48 -0500
                        Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-09 18:17 -0600
                          Re: Suggestions for improving speed of .SYS program. aiiadict@gmail.com - 2014-01-09 20:57 -0800
                            Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-10 05:41 -0600
                              Re: Suggestions for improving speed of .SYS program. David Schmidt <schmidtd@my-deja.com> - 2014-01-10 07:56 -0500
                                Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-10 19:49 -0600
                            Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-10 08:39 -0800
                              Re: Suggestions for improving speed of .SYS program. aiiadict@gmail.com - 2014-01-10 15:58 -0800
        Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-01 22:28 -0800
          Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-03 08:40 +1300
            Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-02 18:33 -0600
            Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-02 21:05 -0800
              Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-03 20:20 +1300
    Re: Suggestions for improving speed of .SYS program. "Anton Treuenfels" <teamtempest@yahoo.com> - 2014-01-02 18:58 -0600
      Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-03 21:05 +1300
        Re: Suggestions for improving speed of .SYS program. "Anton Treuenfels" <teamtempest@yahoo.com> - 2014-01-03 18:17 -0600
          Re: Suggestions for improving speed of .SYS program. "Bill Buckels" <bbuckels@mts.net> - 2014-01-03 21:32 -0600
          Re: Suggestions for improving speed of .SYS program. gids.rs@sasktel.net - 2014-01-03 23:15 -0800
            Re: Suggestions for improving speed of .SYS program. "Anton Treuenfels" <teamtempest@yahoo.com> - 2014-01-04 19:30 -0600
          Re: Suggestions for improving speed of .SYS program. Matt <matt@clickertraining.co.nz> - 2014-01-05 12:50 +1300

Page 3 of 3 — ← Prev page 1 2 [3]

#1096

On Thursday, January 9, 2014 4:17:01 PM UTC-8, Bill Buckels wrote:
> "David Schmidt" <> wrote:
> 
> >I think fish always look annoyed.
> 
> I think the other really annoying thing about fish wearing lipstick, is that 
> unless one is experienced enough to know the difference from the real thing, 
> they can end-up marrying the fish instead of eating it.
> 
> Stay away from fish wearing lipstick whether they look annoyed or are 
> smiling is the best advice I can give. 
> 

holy ship!  we're capsizing....

and the fish I'm with I thought was a woman...

and she smells like fish.

and I ate her!

and she wears lipstick.

but her heart is cold.

and she hates it when I argue on the internet.

because it is time I wasted, because I could
have argued with her.


happy fishing.

10 print "hello fish"

[toc] | [prev] | [next] | [standalone]

#1097

<aiiadict@gmail.com> wrote:
>10 print "hello fish"
Rich,

You get the "go fish" award for this thread.

Bill

[toc] | [prev] | [next] | [standalone]

#1099

On 1/10/2014 6:41 AM, Bill Buckels wrote:
> <aiiadict@gmail.com> wrote:
>> 10 print "hello fish"
> Rich,
>
> You get the "go fish" award for this thread.

Ah, no, Bill - that award goes to you.

[toc] | [prev] | [next] | [standalone]

#1105

"David Schmidt" <schmidtd@my-deja.com> wrote:
>Bill Buckels wrote:
>> You get the "go fish" award for this thread.
>Ah, no, Bill - that award goes to you.
Did I paint myself into a corner again David? Oh well... you still can't put 
lipstick on a fish and call it inline assembly.

Hey, in real-life as well as fishing for a living (chopping up live fish and 
so forth so people can eat) we take-in  ferrel cats and fix them and 
humanize them. Aztec C is like a ferrel cat, and that is all I am going to 
admit.  Writing cc65 programs is trivial and does not get my retro-juices 
flowing.

I'll need to leave the excellence up to you guys while I flog this thing to 
death. But it seems rather remarkable the mileage that I have got out of it. 
That's one thing for sure. Whether that is stupid or not I'll need to leave 
to the reader to decide, and whenI finally publish the book, it will be sure 
to disappear off the planet just like Apple II itself  which is another 
ferrel beast that catches my heart.

Bill

[toc] | [prev] | [next] | [standalone]

#1100

> > >I think fish always look annoyed.

> > I think the other really annoying thing about fish wearing lipstick, is that 
> > unless one is experienced enough to know the difference from the real thing, 
> > they can end-up marrying the fish instead of eating it.

> > Stay away from fish wearing lipstick whether they look annoyed or are 
> > smiling is the best advice I can give. 

> holy ship!  we're capsizing....
> and the fish I'm with I thought was a woman...
> and she smells like fish.
> and I ate her!
> and she wears lipstick.
> but her heart is cold.
> and she hates it when I argue on the internet.
> because it is time I wasted, because I could
> have argued with her.

> happy fishing.

> 10 print "hello fish"



ALOT  - (a little off topic)

[toc] | [prev] | [next] | [standalone]

#1102

On Friday, January 10, 2014 8:39:44 AM UTC-8, gid...@sasktel.net wrote: 
> 
> > 10 print "hello fish"
> 
> ALOT  - (a little off topic)

I included a line of applesoft.

Thanks for all the fish.

Rich

[toc] | [prev] | [next] | [standalone]

#1031

On Wednesday, January 1, 2014 1:18:23 PM UTC-6, Matt wrote:
> On 02/01/14 06:15, gids.rs@sasktel.net wrote:

> > I am not familiar with the speed of aztec c, but I am proficient with ML, so if you'd care to share the .sys file, I can optimize it for you.
 
> http://code.mattsmith.org.nz/MAIN.SYS

> ML is Machine Language right? Is that the binary code the processor 

> understands natively - lower level again than 6502 assembly?
Thanks very much for looking at this :-)

> Matt


Is 1294 the answer?  Because if it is, this is an invalid number.  You are only supposed to have 6 numbers or colors in the answer.  Which means you can only use numbers 0 to 5.  Otherwise you basically have 10 colors/numbers and 4 slots.

Rob

[toc] | [prev] | [next] | [standalone]

#1032

On 02/01/14 19:28, gids.rs@sasktel.net wrote:
> Is 1294 the answer?  Because if it is, this is an invalid number.  You are only supposed to have 6 numbers or colors in the answer.  Which means you can only use numbers 0 to 5.  Otherwise you basically have 10 colors/numbers and 4 slots.

1294 is the index of the answer. There are 6 to the power of 4 possible 
codes. In the code:

#define ALL 1296

typedef struct{...}mcode;

mcode all_codes[ALL];

//fill all_codes using the nested loops Bill mentioned

for(int i=0; i < PEGS; i++)
   printf("%d", all_codes[1294].code[i]);
printf("\n%d\n", all_codes[1294].knuth_number);//knum is how many 
guesses the algorithm solves it in

 >----<
$./a.out
5554
5
 >----<

Previously I had it giving the following output
 >---<
solve 5554
guess 0011 0,0
guess ...
guess ...
guess ...
guess 5554 4,0
solve 5554 K5
 >---<

which gives people more of a clue. I ended up with printfs all over the 
show and 3 or 4 #defines governing different verbosity levels and I got 
sick of it since by that stage I was totally confident in what the code 
was doing I just wanted (want) more speed.

Also I've been writing it in GNU C then changing it for aztec so the the 
aztec code has had comments excised etc and is a little messier all 
round. This approach has to go by the board now since it's clear aztec 
is a totally different animal. In both cases you write the code in C but 
that's where the similarity ends.

Matt.

[toc] | [prev] | [next] | [standalone]

#1034

"Matt" <matt@clickertraining.co.nz> wrote:
>Also I've been writing it in GNU C then changing it for aztec ...
>This approach has to go by the board now since it's clear aztec is a 
>totally different animal.

One might even say you have been writing in GNA C

Then chnaging it for ANG (no I do not mean angry C:)

Bill

[toc] | [prev] | [next] | [standalone]

#1036

On Thursday, January 2, 2014 1:40:50 PM UTC-6, Matt wrote:
> On 02/01/14 19:28, gids.rs@sasktel.net wrote:

> > Is 1294 the answer?  Because if it is, this is an invalid number.  You are only supposed to have 6 numbers or colors in the answer.  Which means you can only use numbers 0 to 5.  Otherwise you basically have 10 colors/numbers and 4 slots.

> 1294 is the index of the answer. There are 6 to the power of 4 possible 
> codes. In the code:
 
> #define ALL 1296

> typedef struct{...}mcode;

> mcode all_codes[ALL];

> //fill all_codes using the nested loops Bill mentioned

> for(int i=0; i < PEGS; i++)
>    printf("%d", all_codes[1294].code[i]);
> printf("\n%d\n", all_codes[1294].knuth_number);//knum is how many 
> guesses the algorithm solves it in
 
>  >----<
> $./a.out
> 5554
> 5
>  >----<

> Previously I had it giving the following output
>  >---<
> solve 5554
> guess 0011 0,0
> guess ...
> guess ...
> guess ...
> guess 5554 4,0
> solve 5554 K5
>  >---<

> which gives people more of a clue. I ended up with printfs all over the 

> show and 3 or 4 #defines governing different verbosity levels and I got 
> sick of it since by that stage I was totally confident in what the code 
> was doing I just wanted (want) more speed.

> Also I've been writing it in GNU C then changing it for aztec so the the 
> aztec code has had comments excised etc and is a little messier all 
> round. This approach has to go by the board now since it's clear aztec 
> is a totally different animal. In both cases you write the code in C but 
> that's where the similarity ends.

> Matt.



Looks like BREADTH wins over KNUTH

http://sartak.org/nh/mastermind.html

[toc] | [prev] | [next] | [standalone]

#1037

On 03/01/14 18:05, gids.rs@sasktel.net wrote:
> Looks like BREADTH wins over KNUTH
>
> http://sartak.org/nh/mastermind.html

Interesting stuff, thx

[toc] | [prev] | [next] | [standalone]

#1035

"Matt" <matt@clickertraining.co.nz> wrote in message 
news:la0kks$qcu$1@news4.open-news-network.org...
>I wrote some code using Bill's AppleX distro of aztec c65.
>
> It can be viewed at http://code.mattsmith.org.nz

I spent a little time looking at your code and then a bit of time looking 
around the net for the original algorithm. From what I can tell your code is 
more or less a straight port from the original language used to demonstrate 
the algorithm.

I suppose the first thing I'd do is try to figure out where the time is 
really being spent. How much is spent on the initialization section? How 
much in getscore()? How much in managing the calls to getscore()?

I might also re-factor at least getscore(). Something like this, maybe:

int getfmatch(secret, guess, total)
int *score, *guess, *total;
{

  int i;
  int fmatch;

  i = fmatch = 0;
  do {
    if(*guess == *secret){
      fmatch++;
      total[*guess]++;
    }
    guess++;
    secret++;
   } while ( ++i < PEGS );

   return fmatch;
}

int getcmatch(secret, guess, total)
int *score, *guess, *total;
{

  int i, j;
  int hmany, cmatch;

  i = cmatch = 0;
  do {
    if(*guess != *secret){
    /*
    * if the secret includes more of this color than the number of
    * totalms already given for this color then give a cm
    */
      j = hmany = 0;
      do {
 if(*(secret+j) == *guess)
   hmany++;
      } while ( ++j < PEGS );

      if(hmany > total[*guess]){
 cmatch++;
 total[*guess]++;
      }
    }
    guess++;
    secret++;
  } while ( ++i < PEGS );

  return cmatch;
}

void getscore(secret, guess, score)
int *secret, *guess, *score;
{
  int i;
  int totalms[COLORS];

  for(i=0; i < COLORS; i++)
    totalms[i] = 0;

  /* been a long time since I used C; the third parameter should be a 
pointer to totalms[] */
  /* ...also not too clear on why two consecutive integers are necessary for 
return, but whatever... */

  *score++ = getfmatch( secret, guess, &totalms[] );
  *score =   getcmatch( secret, guess, &totalms[] );
}

Mostly to get rid of a whole lot of pointer additions that I suspect might 
take up time. Perhaps easier to time separately as well.

- Anton Treuenfels

[toc] | [prev] | [next] | [standalone]

#1038

On 03/01/14 13:58, Anton Treuenfels wrote:

>
> I spent a little time looking at your code

Thanks I appreciate that.

> and then a bit of time
> looking around the net for the original algorithm. From what I can tell
> your code is more or less a straight port from the original language
> used to demonstrate the algorithm.

Not sure exactly what you mean by "original language
  used to demonstrate the algorithm." Looking at a timestamp it looks 
like I first implemented the algorithm in 2007 in objective C code which 
was subsequently obsoleted by a library change in Debian GNU/Linux. The 
only description of the algorithm I ever looked at was a brief paragraph 
on wikipedia which was in english as opposed to C or some other 
programming language. Whenever I've implemented the algo since then 
(including the one you looked at) I've just done it using my own 
recollection of how it works.

>
> I suppose the first thing I'd do is try to figure out where the time is
> really being spent.

Good idea. Not sure how I would do this though. Don't have the tools 
available in Debian. Also any information gathered by by building the 
code in Debian and measuring things could easily be useless. I got the 
time to solve all possible secrets on my modern system down from 20 min 
to 7 min but it made no difference when I incorporated the changes in to 
the apple version.

Thinking about it now I guess it is possible it will just be highly 
manual and tedious which I'm starting to realise is par for the course 
with this stuff. Modern dev tools really are amazing in comparison. 
Remind me - why am I doing this ? lol

>
> I might also re-factor at least getscore(). Something like this, maybe:
>
<snip>
>
> Mostly to get rid of a whole lot of pointer additions that I suspect
> might take up time. Perhaps easier to time separately as well.

Thanks for taking the time. I'll try this stuff and see what happens

Matt.

[toc] | [prev] | [next] | [standalone]

#1043

"Matt" <matt@clickertraining.co.nz> wrote in message 
news:la5rb1$b5r$1@news4.open-news-network.org...
> On 03/01/14 13:58, Anton Treuenfels wrote:
>
>>
>> I spent a little time looking at your code
>
> Thanks I appreciate that.
>
>> and then a bit of time
>> looking around the net for the original algorithm. From what I can tell
>> your code is more or less a straight port from the original language
>> used to demonstrate the algorithm.
>
> Not sure exactly what you mean by "original language
>  used to demonstrate the algorithm." Looking at a timestamp it looks like 
> I first implemented the algorithm in 2007 in objective C code which was 
> subsequently obsoleted by a library change in Debian GNU/Linux. The only 
> description of the algorithm I ever looked at was a brief paragraph on 
> wikipedia which was in english as opposed to C or some other programming 
> language. Whenever I've implemented the algo since then (including the one 
> you looked at) I've just done it using my own recollection of how it 
> works.

I meant Knuth's original algorithm. I haven't looked at it yet but I did 
find this (which is definitely not C):

http://delphiforfun.org/Programs/MasterMind.htm

I understand Level 1 and Level 2. I even understand what he's saying about 
Level 3. It's the part where he generates the scoresets I don't get. That 
is, it's not clear to me how they could be derived except with reference to 
the actual secret code - and if you need to know that to produce the 
scoresets, what's the "secret"?

>
>>
>> I suppose the first thing I'd do is try to figure out where the time is
>> really being spent.
>
> Good idea. Not sure how I would do this though. Don't have the tools 
> available in Debian. Also any information gathered by by building the code 
> in Debian and measuring things could easily be useless. I got the time to 
> solve all possible secrets on my modern system down from 20 min to 7 min 
> but it made no difference when I incorporated the changes in to the apple 
> version.

You can get a ballpark idea just by printing a character to the screen every 
time something "interesting" happens. It's the parts where you find yourself 
staring at the screen wondering when the next character is going to appear 
that probably are taking the most time.

> Thinking about it now I guess it is possible it will just be highly manual 
> and tedious which I'm starting to realise is par for the course with this 
> stuff. Modern dev tools really are amazing in comparison. Remind me - why 
> am I doing this ? lol
>
>>
>> I might also re-factor at least getscore(). Something like this, maybe:
>>
> <snip>
>>
>> Mostly to get rid of a whole lot of pointer additions that I suspect
>> might take up time. Perhaps easier to time separately as well.
>
> Thanks for taking the time. I'll try this stuff and see what happens

Ah, actually that's pretty bad code, now that I think about it. Just to get 
the position+color and color-only matches it might be simpler to do 
something like this:

void getscores(secret, guess, score)
int *secret, *guess, *score;
{
    int pcmatch, cmatch;
    int i, j, peg;
    int code[ MAX_PEGS ];

   i = 0;
  do {
      code[ i ] = *secret++;
  } while ( ++i < MAX_PEGS );


    i = pcmatch = cmatch = 0;
   do {
      peg = *guess++;
      j = 0;
      do {
         if ( peg == code[j] ) {          /* color matches */
            if ( i == j )                          /* position matches */
               pcmatch++;
            else
               cmatch++;
            code[ j ] = -1;                  /* prevent another match here 
(eg, two or more guess pegs the same color) */
            break;                              /* done with this peg */
      } while ( ++j < MAX_PEGS );
   } while ( ++i < MAX_PEGS );

   *score++ = pcmatch;
   *score = cmatch;
}

...I think, anyway. Still no clue as to what to do with it once it's got 
(aside from the obvious).

- Anton Treuenfels 

[toc] | [prev] | [next] | [standalone]

#1044

"Anton Treuenfels" <teamtempest@yahoo.com> wrote:
>Still no clue as to what to do with it once it's got

Me neither... I'd rather finish-off my BMP to SHR converter. But it's an 
interesting thread and gives me a good read when I stop for a break:)

Bill 

[toc] | [prev] | [next] | [standalone]

#1045

> I understand Level 1 and Level 2. I even understand what he's saying about 
> Level 3. It's the part where he generates the scoresets I don't get. That 
> is, it's not clear to me how they could be derived except with reference to 
> the actual secret code - and if you need to know that to produce the 
> scoresets, what's the "secret"?


No, you are not comparing with the real answer.  What you are comparing with to derive the score test is,  you compare your guess with each of the 1296 possible answers and eliminate the ones that would not give you the score that you feed it.

Technically, you would not tell the computer what the answer is so it can compare with it.  It usually has a fixed first guess of 0011.  You then feed the computer the result of his guess with, something like, 1 right color right spot, 1 right color wrong spot (or whatever the case may be).  Then the computer should be able to calculate the next best guess by comparing the results with all 1296 possible answers.

The comparison with the real answer is just eliminating the input you would normally feed it.  It just uses the real score just to calculate the input that you would normally feed it.

If it makes you feel any better, you can leave that part of the programming out and instead program it to allow user input so you can tell it what its score is.

Rob

[toc] | [prev] | [next] | [standalone]

#1052

<gids.rs@sasktel.net> wrote in message 
news:b5bdfe6d-0671-400a-87e0-c8a8c9cc0de3@googlegroups.com...
> I understand Level 1 and Level 2. I even understand what he's saying about
> Level 3. It's the part where he generates the scoresets I don't get. That
> is, it's not clear to me how they could be derived except with reference 
> to
> the actual secret code - and if you need to know that to produce the
> scoresets, what's the "secret"?


No, you are not comparing with the real answer.  What you are comparing with 
to derive the score test is,  you compare your guess with each of the 1296 
possible answers and eliminate the ones that would not give you the score 
that you feed it.

Technically, you would not tell the computer what the answer is so it can 
compare with it.  It usually has a fixed first guess of 0011.  You then feed 
the computer the result of his guess with, something like, 1 right color 
right spot, 1 right color wrong spot (or whatever the case may be).  Then 
the computer should be able to calculate the next best guess by comparing 
the results with all 1296 possible answers.

The comparison with the real answer is just eliminating the input you would 
normally feed it.  It just uses the real score just to calculate the input 
that you would normally feed it.

If it makes you feel any better, you can leave that part of the programming 
out and instead program it to allow user input so you can tell it what its 
score is.

Rob

========================

O-kay, I'm spending much more time than I should with this. With respect to

http://delphiforfun.org/Programs/MasterMind.htm

and without looking at any of the actual code, here's my best guess as to 
what Level 2 looks like in pseudo code:

solvelevel2(secret) {

  # all possible patterns are eligible solutions

  initpatterns()

  # the first guess is fixed
  # - has been marked ineligible so it won't be used again

  guess = "RRGG"

  # loop until solved

  while ( guess != secret ) {

      # compare guess to secret

      guessscore = getscore( secret, guess )

      # look for another guess

      i = patternscore = -1

      do {

          if ( pattern[++i].eligible ) {

            # we will never use this pattern again in any case

            pattern[ i ].eligible = FALSE

            # a symmetry: score(secret, guess) == score(guess, secret)

            patternscore = getscore( guess, pattern[i].value )

          }

       # if scores don't match this pattern is not in solution set...

       } while ( patternscore != guessscore )

       # ...but if they do this pattern is the next guess

       guess = pattern[ i ].value

   }

   return( guess )

   # ...of course "guess" and "secret" are identical...

}

Pretty straightforward. Progressing to Level 3 and its goal of picking the 
"best" next guess w/r/t reducing the total number of guesses is much more 
complicated, as far as I can tell. It also increases the time factor 
enormously. Again this is my interpretation of what I've read so far, so I 
could still be horribly wrong. Feel free to correct if you know better:

solvelevel3(secret) {

  # all possible patterns are eligible solutions

  initpatterns()

  # the first guess is fixed
  # - has been marked ineligible so it won't be used again

  guess = "RRGG"

  # loop until solved

  while ( guess != secret ) {

      # compare guess to secret

      guessscore = getscore( secret, guess )

      # find the set of patterns with a matching score

      for ( i = 0; i < MAX_PATTERNS; i++ )

          patternscore = -1

          if ( pattern[i].status == T_ELIGIBLE )

            # a symmetry: score(secret, guess) == score(guess, secret)

            patternscore = getscore( guess, pattern[i].value )

          # if scores match this pattern is in solution set, otherwise not
          # - note that this also changes any T_POSSIBLE from the previous 
round to T_INELIGIBLE

          pattern[ i ].status = ( patternscore == guessscore ) ? T_POSSIBLE 
: T_INELIGIBLE

       }

       # find the pattern that likely most reduces the remaining 
possibilities

       min_score_count = MAX_PATTERNS

       for ( i = 0; i < MAX_PATTERNS; i++ ) {

          # pattern in solution set ?

          if ( pattern[i].status == T_POSSIBLE ) {

             for ( j = 0; j < MAX_SCORES; j++ )

                score[ j ] = 0

             # compare against all other possible patterns

             thisguess = pattern[ i ].value

             for ( j = 0; j < MAX_PATTERNS; j++ ) {

                if ( pattern[j].status == T_POSSIBLE && i != j )

                   score[ getscore(thisguess, pattern[j].value) ]++
             }

             # which score showed up most often ?
             # - the _MAX part of MINI_MAX

             max_guess_scores = 0

             for ( j = 0; j < MAX_SCORES; j++ ) {

                if ( max_guess_scores < score[j] )

                   max_guess_scores = score[ j ]
             }

             # is it less than what we have ?
             # - the MINI_ part of MINI_MAX
             # - the last setting of this will become our next guess

             if ( max_guess_scores < min_score_count ) {

                min_score_count = max_guess_scores

                guess = thisguess

             }

          }

       }


   }

   return( guess )

   # ...of course "guess" and "secret" are identical...

}

Is this as bad as it looks? Possibly not. The first guess of "RRGG" (or any 
similar two-repeated-color guess) reduces the maximum possible number of 
solutions to 256 or thereabouts. So the first round should be the longest as 
the greatest triage of possibilities occurs. Still, if 256 remain that's 
2^16 or so more calls to getscore(). Quite a few. If you're looking for the 
fastest solution, Level 2 may make a few more guesses but likely a whole lot 
fewer calls to getscore().

I've skipped over a lot about the data structures, but one thing I've 
assumed is that the 25 possible ordered pairs referred to in the linked 
document (of which only 14 represent actual possibilities) are coded into a 
single integer by simple multiplication (eg, "(m,n)" is returned as "m*8+n" 
or somesuch - the important thing is to preserve their uniqueness in 
whatever transformation is used).

That could be taken further. Since all 1296 possibilities are unique 
(assuming 6*6*6*6 puzzles), there's no need to actually store anything about 
them except their status. Their "values" can be derived by decoding their 
"solution numbers". If space is more of an issue than time. Maybe not even 
then, if decoding is fast compared to manipulating stored values.

- Anton Treuenfels 

[toc] | [prev] | [next] | [standalone]

#1049

On 04/01/14 13:17, Anton Treuenfels wrote:

> it's not clear to me how they could be derived except with
> reference to the actual secret code

Robs explanation of this is a good one. I've occasionly had a moment of 
doubt when I've been implementing k5g along the lines of "sh*t I hope 
I'm not cheating" but quickly realised that it's not cheating it's just 
a brute force algorithm that no human could hope to implement as a 
strategy unless they are some kind of savant.

>
> You can get a ballpark idea just by printing a character to the screen
> every time something "interesting" happens. It's the parts where you
> find yourself staring at the screen wondering when the next character is
> going to appear that probably are taking the most time.
>

That's true but you need to be pretty selective about where you put the 
character printing code if it's going to get repeated a whole bunch of 
times. The other day when I had solve implemented as more than one 
function I had a call to printf() at the start of a function called 
least() and this slowed the program down drastically. Like that thing in 
physics - "the act of observation changes that which bla bla ..."

>
> Ah, actually that's pretty bad code, now that I think about it.

I've said the same thing to myself loads of times:-)

The code for scoring a guess is interesting actually because it's one of 
those things you do as a human without even knowing how you do it, which 
then turns out to be non-trivial to explain to a computer. I had a 
redundant loop in getscore which a guy on comp.lang.c pointed out to me. 
I never would have discovered that and learned how to fix it if I hadn't 
started this retroprogramming thing.

Matt.

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.sys.apple2.programmer

csiph-web