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 1 of 3  [1] 2 3  Next page →

#1022 — Suggestions for improving speed of .SYS program.

I wrote some code using Bill's AppleX distro of aztec c65.

It can be viewed at http://code.mattsmith.org.nz

It produces the following output:

<output>
0
1
2
3
4
1294 K5
</output>

Not exactly a sound and light show :-) What it's doing is using the 5 
guess algorithm for solving the secret code in the mastermind board 
game. The 1295th possible code is 5554. Guess 0 is 0011 receiving score 
0,0 (No pegs correct color correct place, No pegs correct color wrong 
place) until guess 4 is 5554 receiving 4,0. So far so good but here's a 
more informative version of the output:

<output>
0[wait 13.5 minutes]
1
2
3
4
1294 K5
</output>

Originally the wait was 20 mins. I got it down by correcting my sloppy 
code with help from the guys on comp.lang.c. I can't see where there are 
more gains to be made this way.

I'm running the program in the linapple emulator at speed 40(max). 
Applewin (actually wine applewin) at speed fastest is slower again.

Eric from comp.lang.c remembers writing a mastermind game for the IBM 
System/370 145 in which the computer made it's guesses faster then he 
could make his, so he thinks that there is something wrong with my setup 
somehow. I'm assuming computing_power(S/370) <= computing_power(Apple //e).

It was suggested that this might be an emulator issue of some sort. 
Doesn't seem likely to me but in any case I don't have access to a //e 
to test this.

If anyone can shed any light on this or just suggest how I might 
continue to investigate it that would be great.

Matt.

[toc] | [next] | [standalone]

#1024

On Wednesday, January 1, 2014 2:40:34 AM UTC-6, Matt wrote:
> I wrote some code using Bill's AppleX distro of aztec c65.

> It can be viewed at http://code.mattsmith.org.nz

> It produces the following output:

> <output>
> 0
> 1
> 2
> 3
> 4
> 1294 K5
> </output>

> Not exactly a sound and light show :-) What it's doing is using the 5 
> guess algorithm for solving the secret code in the mastermind board 
> game. The 1295th possible code is 5554. Guess 0 is 0011 receiving score 
> 0,0 (No pegs correct color correct place, No pegs correct color wrong 
> place) until guess 4 is 5554 receiving 4,0. So far so good but here's a 
> more informative version of the output:

> <output>
> 0[wait 13.5 minutes]
> 1
> 2
> 3
> 4
> 1294 K5
> </output>

> Originally the wait was 20 mins. I got it down by correcting my sloppy 
> code with help from the guys on comp.lang.c. I can't see where there are 
> more gains to be made this way.
> 

> I'm running the program in the linapple emulator at speed 40(max). 
> Applewin (actually wine applewin) at speed fastest is slower again.

> Eric from comp.lang.c remembers writing a mastermind game for the IBM 
> System/370 145 in which the computer made it's guesses faster then he 
> 
> could make his, so he thinks that there is something wrong with my setup 
> somehow. I'm assuming computing_power(S/370) <= computing_power(Apple //e).

> It was suggested that this might be an emulator issue of some sort. 
> Doesn't seem likely to me but in any case I don't have access to a //e 
> to test this.

> If anyone can shed any light on this or just suggest how I might 
> continue to investigate it that would be great.


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.

Rob

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

#1026

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

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

#1027

"Matt" <matt@clickertraining.co.nz> wrote:
>Thanks very much for looking at this :-)

I looked at it too, moved some lines around, then abandoned it, not even 
bothering to save... so I have the source here and see many nested loops (4 
levels) and structures in use. One big buffer would be a place to start with 
afew pointers. Keeping in mind that like the others in here, I seldom 
sleep... and I have a calculator in my hand and a peeks and pokes chart on 
the wall at all times.

The style is too high level for my taste and reminiscent of modern 
compilers.

I hardly think that optimizing in ML is the way to go right now, but I 
haven't the time to make this work quickly right now either. My own projects 
are more important to me.

Aztec C outputs in Assembler. It is stack intensive as C compilers of the 
day were, but deals with pointers efficiently. 4 level nested loops of 
structures don't belong in a retro C program is your first clue I think.

Switching registers a gazillion times is your second clue. This was always 
the case with other C's of the day too... including Microsoft C and Turbo C 
on the PC and 16 bit code. Those damned segments kepty getting reloaded and 
the only way to stop it was to generate an assembler pass then tweak it... 
for doing that in Aztec C, use the compiler option:

c65 -a -t main.c

This will produce an assembly listing with comments called main.a

This is the same code that Aztec C65 assembles using AS65 behind the scenes 
normally. The function calls offest the automatics (stack variables) and 
restore the stack when done. The register areas are on zero page (see 
zeropage.h in your include directory).

The most important thing here is to see how the 6502 registers get loaded, 
using primitive control structures in your program rather than higher level 
stuff.

And if I went running for an assembler every time I wrote an inefficient C 
program, I would never have been able to feed my family in the 80's and 90's 
is your third clue. So I stay away from assmbler until I have ruled-out my 
other options... including the use of a simple goto and linear arrays that 
require limited instructions to load offsets... this style is borrowed 
heavily from the sgemented architecture on the intel chips of the day... the 
motorola guys didn't need to worry about that so never really got the hang 
of it... linear memory makes one lazy. The 6502 for all intents and purposes 
follows the same methodology as a segmented approach, but on an 8 bit rather 
than 16 bit scale.

Anyone who can work in Qt can solve this... (and much more I should add) but 
I'll bet that running this algo on some old piece of big blue iron in PL1 or 
whatever some guy did back then wouldn't have run much better than what you 
put here, not meaning to be unkind, but just saying.

Stay away from the ML. That's a different culture. Download cc65 and compile 
this there too and do some of your own tests with that too. cc65 is an 
optimizing compiler, and not a retro-compiler. It doesn't make such use of 
the stack nor does it stay with integer data types like Aztec C65.

But from my experience with Aztec C, which is self-evident, your code should 
run at speeds that come close to cc65 on the Apple II. An understanding of 
the 6502 is a good thing too and using ML to speed-up an Aztec C or any C 
program requires intimate knowledge of the stack use of the Compiler and how 
registers are saved and restored, and the run-time environment of the link 
libraries etc.

Pseudo registers in Aztec C using pointers and using the inline assembly 
feature combined with assembly modules that are written with knowledge of 
the runtime are a good thing... cc65 doesn't provide inline assembly... 
that's a retro-compiler feathure.

To sum-up, take-out your biggest hammer and knock your structures apart, use 
pointers instead, with indexing on subscripts rather than incrementing the 
things. The assembler that this will generate is far better for porting to 
ml later. Goto's work well. Certainly that's all you will get with ML from 
most Apple II guys... using structured assmbly with vector dispatch tables 
and jump adresses  is unlikely from what I have seen so far... but that is 
just what I think.

Remember, your biggest hammer! The game is to beat the compiler... the year 
is  1986. If you write the thing well-enough your family will get groceries 
for the week... if you fail they will get peanut-butter sandwiches, not to 
mention the rent won't be paid!

Also, the professional reputation that you just got last week will be in the 
toilet and you'll need to go back to the drawing office, or finishing 
concrete again!

Anyway, if bllod-sport mentality doesn't get your adrenaline flowing, and it 
should pass that there is no enlightenment from your own private pain, never 
hesitate to email me what you can and it will not be tossed, just ignored 
for awhile. I should also refer you to the manuals on the website, but it is 
admittedly more fun to fly by the seat of ones pants when using something 
like this at the beginning. Remember this thing never really took-off on the 
Apple II. No C compiler did.

For very good reason, or many very good reasons. The biggest main one that I 
see from the top of the mountain is that given a local solution in assembly, 
few learned low-level C the way we did on the IBM-PC... the 6502 sucks too, 
but that makes it even more fun.

Give a man an 8086 or Z-80 C Compiler and what you will have is a man with a 
Compiler and no problems... but give a man a 6502 C compiler and Zero Page, 
and you'll get a man who will either run for BASIC and ML, or who will 
become a better C programmer.

Explore this stuff, and then let's get Qt up and start writing some 
cross-platform Apple II utilities with widgets and a proper UI. You've got 
the time I assume since you're doing your homework right now. You sure 
picked a hard way to go though:)

HNY

Bill 

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

#1028

On 02/01/14 09:44, Bill Buckels wrote:
> Explore this stuff,

Yea I just have to get it out of my system now that I've started.

> and then let's get Qt up and start writing some
> cross-platform Apple II utilities with widgets and a proper UI. You've got
> the time I assume since you're doing your homework right now.

I might like to contribute to something like that if I could. I'm really 
a novice programmer though. 
http://code.mattsmith.org.nz/qmastermind-20110702.tar.gz is pretty much 
what I've done up to this point.

> You sure
> picked a hard way to go though:)

Yep I dunno why I do that :-)

Thanks for the reply - there's a lot there for me to follow up on.

Matt.

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

#1029

"Matt" <matt@clickertraining.co.nz> wrote:
> I'm really a novice programmer...

Me too compared to some of the other guys around.

Jack Crenshaw for example who programmed the trajectory for the Apollo 
Mission and is currently do the same to put a Ranger on the Moon for some 
kind of google project.

>there's a lot there for me to follow up on.

Yeah, them's fighting words, for sure!

Bill

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

#1030

On 01/02/2014 05:49 AM, Bill Buckels wrote:
> "Matt" <matt@clickertraining.co.nz> wrote:
>> I'm really a novice programmer...
>
> Me too compared to some of the other guys around.
>
> Jack Crenshaw for example who programmed the trajectory for the Apollo
> Mission and is currently do the same to put a Ranger on the Moon for some
> kind of google project.

Amen.  Jack has arguably forgotten more about numerical methods than I could 
hope to learn in a decade.

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

#1033

"Steven Hirsch" <snhirsch@gmail.com> wrote:
>Amen.  Jack has arguably forgotten more about numerical methods than I 
>could hope to learn in a decade.

For me that would be a lifetime:)

Jack began his BSC in Physics the year I was born: 1952. Jack Crenshaw wrote 
his first computer program in 1956. He thinks he might be beginning to get 
the hang of it. Jack also wrote 16 articles on compiler creation from 1988 
to 1995

Jack and I shot some email between ourselves afew weeks ago. Here are some 
highlights:

>You may remember that I wanted to port CP/M to the Rabbit.  If I were to do 
>it now, I'd want to port it to an ARM.

>Crenshaw's First Law is:  There is an infinite number of ways to take a 
>simple problem and make it seem hard.  Only a handful of ways to take a 
>hard problem and make it seem simple.  Simplicity is the Holy Grail for me.

>You may recall that it was you who encouraged me to get into HTML and write 
>my own site from scratch.  I actually did that, and was pleased with the 
>result... All that changed with the advent of WordPress.  I guess you 
>noticed, that's the way I built the current site.

>Don't know if I ever mentioned it, but I dang near died in 2008.
>I guess that's when I stopped working on the website.

>In 2009, Google announced a new X-Prize, to send a rover to the Moon.  I 
>got asked to join one of the teams, and as an old refugee of Apollo, how 
>could I say no?  Here's our website:
http://ptscientists.com/


>Since 2009, I've been working real hard on the trajectory  analysis (same 
>thing I did in 1959-69).  I've had to dredge up all the skills I learned 
>the hard way, plus a lot of new ones.  I've been focusing on that, not just 
>to the detriment of the website, but my paid job for Embedded.com, as well. 
>I don't regret it for a second though. I'm having a blast.



Anyway, there was more, but suffice to say that Jack is still very much a 
part of us.

Bill

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

#1039

On 02/01/14 09:44, Bill Buckels wrote:
> Remember this thing never really took-off on the
> Apple II. No C compiler did.

Bearing that in mind I want to take a step back and ask: Am I even using 
the right tools for the job? I was a software user when I had a //e, 
everything I've learned about programming has come from experience with 
GNU/Linux on x86 machines.

Say the goal back in the day had been to produce a mastermind game 
running on the //e for the educational software market, which employed 
the knuth algorithm as the ai for the computer opponent. What tools 
would you Bill have chosen. What would other developers have chosen?

Maybe I'd be just as well writing it in applesoft basic? I just assumed 
C, compiled, fast. Basic, interpreted, slow. But I'm starting to realise 
that many of my assumptions don't apply when it comes to programming the 
//e.

Matt.

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

#1040

On 1/3/2014 3:42 AM, Matt wrote:
> On 02/01/14 09:44, Bill Buckels wrote:
>> Remember this thing never really took-off on the
>> Apple II. No C compiler did.
>
> Bearing that in mind I want to take a step back and ask: Am I even using
> the right tools for the job? I was a software user when I had a //e,
> everything I've learned about programming has come from experience with
> GNU/Linux on x86 machines.

The right tool for the job, at least at first, is the one that you're 
comfortable with.  If raw speed is what you crave - you need finely 
tuned assembly language.  If turn-efficiency is what turns you on - then 
the algorithm discussion in http://sartak.org/nh/mastermind.html is 
where it's at.  I don't know if Breadth3 would actually execute faster 
than Naive4 - the amount of time spent on each "turn" for each algorithm 
isn't listed; only the number of turns required.  They're different for 
each of the algorithms: execution speed wasn't sartak's goal.  Turn 
efficiency was.

> Say the goal back in the day had been to produce a mastermind game
> running on the //e for the educational software market, which employed
> the knuth algorithm as the ai for the computer opponent. What tools
> would you Bill have chosen. What would other developers have chosen?

Not-Bill answer: no sense in leaving something in BASIC.  If I weren't 
capable of writing in assembly, I would at least have some form of 
compiled language so the laziest of my customers couldn't simply LIST my 
code.  Understanding of course anyone one square to the right of lazy 
can read a disassembly.

> Maybe I'd be just as well writing it in applesoft basic? I just assumed
> C, compiled, fast. Basic, interpreted, slow. But I'm starting to realise
> that many of my assumptions don't apply when it comes to programming the
> //e.

If you write a good algorithm in BASIC, using some tuning techniques 
like unrolling loops and keeping loop contents as simple as possible 
(because they run lots of times), using variables instead of constants, 
and so on - then you'll likely have a passable result.  You can speed 
that up quite a bit with an Applesoft compiler essentially for free - no 
need to learn anything else.  In the end, you need to be able to turn 
your algorithm into code; naive algorithms are really easy to do in 
BASIC, but finely tuned ones that really leverage the machine 
architecture will not come from any interpreter or compiler.  And a 
crappy algorithm will behave crappily in whatever language it starts out in.

I'll leave you with an example from Michael Mahon and Scott Hemphill, 
who in 2006 wrote a Sodoku solver in assembly.  It started from an 
algorithm in C, and progressed through ever more clever assembly 
iterations.  In the end, it is a fairly brute-force solver that doesn't 
try to be perfect in terms of turn efficiency - it tries out a bunch of 
possibilities and sees what the outcome is.  It doesn't spend undue 
amounts of work to thin out the game tree; and in the Apple II's case, 
for this solution space, it paid off handsomely.

http://home.comcast.net/~mjmahon/Sudoku.html

What was the right language for this?  They ended up using quite a few 
of the 6502's characteristics that probably would have been awkward in a 
higher-level language; or at least it would require a way to shake free 
of a compiler and simply say "pass this to the assembler instead..."

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

#1041

"David Schmidt" <schmidtd@my-deja.com> wrote:
>Not-Bill answer: no sense in leaving something in BASIC.

Not really my question to answer either. But clearly we all know that 6502 
Assembler is the way to go for anything time critical on the Apple II, and 
we also know that the BASIC run-time on the Apple II is very close to the 
processor, but still needs a runtime. But then so do compiled languages.

The Aztec C runtime has a large footprint compared to cc65, and just because 
I like to collect Aztec C compilers and keep them alive, doesn't mean that 
they are the best tool for the job. It just means that I enjoy them.

Michael Mahon's approach wins everytime when talking about writing Apple II 
programs, but if your direction is C language specific you owe it to 
yourself to explore both the C compilers for the Apple II.

If you like Pascal or Forth, then you can go with those as well. If y7ou 
like Basic a BASIC compiler with assembly modules for time-critical portions 
of a program is probably a pretty decent choice.

And pure ML is a brave direction. But wouldn't be my answer, nor would 
BASIC, but then I am just playing, and not really looking for speed so much 
as how I can extend an old compiler for my own nefarious purposes.

Bill

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

#1042

On 04/01/14 02:15, David Schmidt wrote:
<snip>

>If raw speed is what you crave - you need finely
> tuned assembly language.  If turn-efficiency is what turns you on - then
> the algorithm discussion in http://sartak.org/nh/mastermind.html is
> where it's at.

1. If the user has to twiddle their thumbs for 10 minutes while the 
computer player is "thinking" the program is not usable (raw speed).

2. If the turn efficiency is too low the game will not challenge anyone 
with half a brain and is not usable for this reason. In my qt version of 
the standard 4 peg, 6 color game the computer solves using the standard 
knuth 5guess (k5g) and picks it's own secret pseudorandomly from all 
possibilities. Anyone with half a brain beats the computer consistently 
just by always choosing a secret with a knuth number of 5. So anything 
with less turn efficiency than k5g would be unsatisfactory imo.

So what do I crave? A bit of both I suppose.

<snip>
>
> I'll leave you with an example from Michael Mahon and Scott Hemphill,
> who in 2006 wrote a Sodoku solver in assembly.

This jumped out at me:

> he posted the C source code, and a quick examination convinced me that it would fit nicely on an Apple II.

Since I feel like I'm banging my head against a wall at the moment what 
I might do is concentrate on implementing k5g in modern C in such a way 
that it meets Michael's criteria for "fitting nicely on an apple II", 
and meanwhile try to get my fet wet with 6502 assembly.

To do this I need help:

When Michael knew straight away from Scott's C code that it would fit 
nicely how exactly did he know this? How will I know if my code is 
moving closer to this ideal?

Should I implement k5g as lots of short functions, or fewer longer ones?

Any recommended learning resources for wetting my feet?

Thanks David,

Matt.

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

#1048

Matt <matt@clickertraining.co.nz> wrote:
> On 04/01/14 02:15, David Schmidt wrote:
> <snip>
> 
>> If raw speed is what you crave - you need finely
>> tuned assembly language.  If turn-efficiency is what turns you on - then
>> the algorithm discussion in http://sartak.org/nh/mastermind.html is
>> where it's at.
> 
> 1. If the user has to twiddle their thumbs for 10 minutes while the
> computer player is "thinking" the program is not usable (raw speed).
> 
> 2. If the turn efficiency is too low the game will not challenge anyone
> with half a brain and is not usable for this reason. In my qt version of
> the standard 4 peg, 6 color game the computer solves using the standard
> knuth 5guess (k5g) and picks it's own secret pseudorandomly from all
> possibilities. Anyone with half a brain beats the computer consistently
> just by always choosing a secret with a knuth number of 5. So anything
> with less turn efficiency than k5g would be unsatisfactory imo.
> 
> So what do I crave? A bit of both I suppose.
> 
> <snip>
>> 
>> I'll leave you with an example from Michael Mahon and Scott Hemphill,
>> who in 2006 wrote a Sodoku solver in assembly.
> 
> This jumped out at me:
> 
>> he posted the C source code, and a quick examination convinced me that
>> it would fit nicely on an Apple II.
> 
> Since I feel like I'm banging my head against a wall at the moment what I
> might do is concentrate on implementing k5g in modern C in such a way
> that it meets Michael's criteria for "fitting nicely on an apple II", and
> meanwhile try to get my fet wet with 6502 assembly.
> 
> To do this I need help:
> 
> When Michael knew straight away from Scott's C code that it would fit
> nicely how exactly did he know this? How will I know if my code is moving
> closer to this ideal?

Space is often the limiting factor for an algorithm that allocates space
dynamically. Since Scott's algorithm was based on recursion, it was
important to determine the upper bound on stack depth. In this case, the
bound was 81 stack frames, each less than a 6502 page in size, which could
be comfortably accommodated in an Apple II. 

Any static tables used to reduce computation should also be
considered--perhaps the most important thing for your algorithm. 

Note that SUDOKU.SOLVER does not use exhaustive tables of "board
configurations".  Instead, it uses three rather small fixed-length tables
to 1) quickly locate "neighboring" cells whose status is affected by
changing a given cell, 2) quickly determining the population count of a
byte, and 3) quickly loading an index register with twice the value in the
other index register. 

> Should I implement k5g as lots of short functions, or fewer longer ones?
> 
> Any recommended learning resources for wetting my feet?

It's a lot like how you get to Carnegie Hall--"Practice, practice,
practice."  ;-)

Seriously, it is a problem of optimizing a constrained design, which is the
prototype of all interesting design problems. So your question is like,
"How do I learn to write great literature?"

My recommendation would be to proceed in parallel down two paths:  study
elegant designs, and make several attempts of your own. 

"Several attempts" is a critical component of learning, since learning
results from critical analysis of both successes and failures--usually more
failures. ;-). (That's why I say that our most important design tool is our
wastebasket. ;-)
-- 
-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

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

#1050

On 04/01/14 23:11, Michael J. Mahon wrote:
> your question is like,
> "How do I learn to write great literature?"
lol!

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

#1046

 
> http://home.comcast.net/~mjmahon/Sudoku.html

> What was the right language for this?  They ended up using quite a few 
> of the 6502's characteristics that probably would have been awkward in a 
> higher-level language; or at least it would require a way to shake free 
> of a compiler and simply say "pass this to the assembler instead..."


They used the one thing that tremendously speeds up the execution time.  And that is tables of every possible answer.

Any language can use tables, basic, pascal, cc65, any compiler.  This greatly reduces the number of calculations to achieve the answer, when every possible answer can be compared to the current situation until one answer fits.

This is how master mind is being compared as well.  The initial guess is already a given (usually 0011) and a comparison of the guess to all 1296 possible answers is done to compare with the score that was potentially fed back to the computer.  The computer is just set up to calculate the score for itself instead of having a user input it in for it.

The most calculated loop is the one where the guess is compared to each of the 1296 possible answers to get the score that should have been fed into the computer.  A table with a score to all the comparisons would have to be pre-generated for fast look up.

Rob

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

#1051

On 04/01/14 20:55, gids.rs@sasktel.net wrote:
>
>> http://home.comcast.net/~mjmahon/Sudoku.html
>
>> What was the right language for this?  They ended up using quite a few
>> of the 6502's characteristics that probably would have been awkward in a
>> higher-level language; or at least it would require a way to shake free
>> of a compiler and simply say "pass this to the assembler instead..."
>
>
> They used the one thing that tremendously speeds up the execution time.  And that is tables of every possible answer.
>
> Any language can use tables, basic, pascal, cc65, any compiler.  This greatly reduces the number of calculations to achieve the answer, when every possible answer can be compared to the current situation until one answer fits.
>
> This is how master mind is being compared as well.  The initial guess is already a given (usually 0011) and a comparison of the guess to all 1296 possible answers is done to compare with the score that was potentially fed back to the computer.  The computer is just set up to calculate the score for itself instead of having a user input it in for it.
>
> The most calculated loop is the one where the guess is compared to each of the 1296 possible answers to get the score that should have been fed into the computer.  A table with a score to all the comparisons would have to be pre-generated for fast look up.
>
> Rob
>

Let's see if I understand what you're saying.

At a high level, leaving out the best case worst case stuff:

for every possible guess
   for every possible score
     count_the_eliminations(this_guess, this_score);

count_the_eliminations(this_guess, this_score)
{
   if I played this_guess and got this_score
     for every remaining possible secret
       if this_one were the actual secret
         woudget = getscore(this_one, this_guess);
	  if wouldget is NOT the same as this_score
	    eliminations++;
}

So count_the_eliminations gets called 1296*15 times.

I happen to know that for my test case of all_codes[1294] being 5554 the 
number of remaining possibilities (npos) goes like this with successive 
passes of the algo:

1296 256 18 3 1

It's between 256 and 18 that the big wait happens.

so in that pass getscore would be called from count_the_eliminations 
(1296*15) * 256 times.

So in what I outlined above there are quite a few spots where a function 
has to look something up by index in these two data structures:

int all_codes[1296][4];
int all_scores[15][2];

So what you're suggesting is that I should construct more or different 
data structures?

What would they be?

A data structure containing all 1296*15 possible guess/score combinations?

This is doing my head in a bit:-)

Matt.

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

#1053

 
> This is doing my head in a bit:-)
> Matt.


Looks good.  Now remove the calculation of the results and set up a user input for the results.

Also, It would be neat to see the best guess at each turn and how many eliminations were made with that best guess.

The program could be sped up tremendously by using a lookup table for the result but how to go about making the table.  There are 1296 combinations compare with 1296 combinations for a total of 1,679,616 comparisons.

Since there are only 14 results, we can use nybbles to depict the results which cuts the table in half the size, and remove a lot of redundancy and duplication can save quite a bit of space.  a guess of 0011 compared with possible answer of 1100 is the same as a guess of 1100 compare with a possible answer of 0011. 

An 800 kb table is still pretty big.  A 1 meg ram card would come in handy here.

0 = no pegs
1 = 1 white
2 = 2 white
3 = 3 white
4 = 4 white
5 = 1 black
6 = 1 black 1 white
7 = 1 black 2 white
8 = 1 black 3 white
9 = 2 black
A = 2 black 1 white
B = 2 black 2 white
C = 3 black
D = 4 black

Note: 3 black 1 white is not needed because you can't have 3 right color right posn and 1 right color wrong posn


Rob

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

#1055

On 05/01/14 17:24, gids.rs@sasktel.net wrote:

>
> Also, It would be neat to see the best guess at each turn and how many eliminations were made with that best guess.
>

http://code.mattsmith.org.nz/complete/qmastermind-20110702.tar.gz gives 
the user full access to the internals of the algorithm in the form of 
cheats and a "hint". Goals for the first version of ][mind might need to 
be a bit more modest though, if only for me to avoid feeling 
overwhelmed. How to eat an elephant and all that. Using the one word 
"programming" to describe programming in qt and programming the ][ 
really is kind of a misnomer imo.

>
> Note: 3 black 1 white is not needed because you can't have 3 right color right posn and 1 right color wrong posn
>

Never thought of that. Thx. I've rewritten my Debian mastermind code to 
take pegs and colors from the command line. Here's how I've been getting 
the number of possible scores (nscrs) based on the value of pegs:

 >----<
nscrs = 0;
int start = pegs + 1;
while(start){
   nscrs += start;
   start--;
}
 >----<

Having to add 1 to pegs struck me as anomalous somehow so maybe that is 
related to what you have pointed out. Or not I will have to check.

Come hell or high water I will write a mastermind game for the ][. When 
that will reach fruition is a little hard to assess. I'm going to finish 
ncurses mastermind for Debian first (god I love modern C!) and I'm going 
through "principles and practice" by Stroustrup for some light relief. 
Also being (relatively) young and having no formal training I lack a lot 
of background knowledge of fundamental stuff that's been referred to in 
this thread. Realistically writing ][mind is going to involve getting to 
grips with a lot of this stuff. That's kind of the point though.

Matt.

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

#1070

On 06/01/14 11:11, Matt wrote:
>>
>> Note: 3 black 1 white is not needed because you can't have 3 right
>> color right posn and 1 right color wrong posn
>>
>
> Never thought of that. Thx. I've rewritten my Debian mastermind code to
> take pegs and colors from the command line. Here's how I've been getting
> the number of possible scores (nscrs) based on the value of pegs:
>
>  >----<
> nscrs = 0;
> int start = pegs + 1;
> while(start){
>    nscrs += start;
>    start--;
> }
>  >----<
>
> Having to add 1 to pegs struck me as anomalous somehow so maybe that is
> related to what you have pointed out. Or not I will have to check.

Unrelated. As far as I can see though there is only 1 "impossible score" 
regardless of the value of PEGS - namely the one where 
yesColorYesPosition == PEGS - 1 so I just added nscrs-- after the above 
code and didn't assign that one in setup_data().

Btw I implemented Kooi's breadth algorithm and it is quite a bit faster 
than Knuth. 1m - 1m30s to solve 1296 codes on my pc vs 10m for Knuth. 
Hopefully this will make it a better candidate for the apple code. 
That'll let me get this out of my system and write some 21st century 
code for a while but still have apple-Knuth there for a challenge:-)

Thanks Rob for pointing out the Breadth algo. Comparison run just finished:

 >----<
$./a.out 4 6
[...]
knuth 4.76003
kooi  4.37346
 >----<

Speed, turn efficiency - nothing like having your cake!

Matt.

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

#1072

 
> Speed, turn efficiency - nothing like having your cake!

> Matt.


I also am a fan of compact efficient code.  I wouldn't mind a copy of the finished system file when your done.  I don't have the means to compile this myself.

Rob

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web