Tuesday, April 5, 2016

Just for fun - the 6kb chess engine - NanoChess68 ...

Just for fun - Cut and paste the following Algol code at: Execute Algol online...
#!/usr/bin/a68g --script #
# -*- coding: utf-8 -*- #
 
COMMENT
# Toledo Nanochess (c)2009 Oscar Toledo G. #
# http://www.nanochess.org/ #
 
# Algol-68 translation (c)2010 Neville C. Dempsey #
# http://sourceforge.net/projects/algol68 #
 
# v0.4   - Tue Jul 9 21:23:49 EST 2013 #
# v0.4.1 - Tue Apr 5 20:54:20 NZST 2016 - fix []INT overflow #
END COMMENT
 
INT bb,i,y,u,b:=666;# b is used before it is defined! #
[0:666]INT ii;
FOR i FROM LWB ii TO UPB ii DO ii[i]:=0 OD;
INT gg:=120,x:=10,z:=15,mm:=10000;
 
[]INT l=[]INT(5,3,4,6,2,4,3,5,1,1,1,1,1,1,1,1,9,9,9,9,9,9,9,9,13,11,
12,14,10,12,11,13,0,99,0,306,297,495,846,-1,0,1,2,2,1,0,-1,-1,1,-10,
10,-11,-9,9,11,10,20,-9,-11,-10,-20,-21,-19,-12,-8,8,12,19,21)[@0];
 
PRIO <<=5;# Should be 5.5 to match C #
OP <<=(INT i,s)INT: ABS (SBIN i SHL s );
 
OP SBA=(INT i)BOOL: i NE 0;# Cast a INT into an BOOL #
 
OP SBIN = (INT i)BITS: (i>=0 | BIN i | NOT BIN ABS (i+1) ); # 2s compliment #
PRIO XOR=2;# 2.5 to match C #
OP XOR=(INT a,b)INT: ABS ((SBIN a OR SBIN b)&NOT (SBIN a&SBIN b) );
PRIO XORAB=1;
OP XORAB=(REF INT lhs,INT i)VOID: lhs:=lhs XOR i;
 
OP INC=(REF INT lhs)VOID: lhs+:=1;
OP DEC=(REF INT lhs)VOID: lhs-:=1;
OP POSTINC=(REF INT lhs)INT:(INT out=lhs;lhs+:=1;out);
OP POSTDEC=(REF INT lhs)INT:(INT out=lhs;lhs-:=1;out);
OP PREINC=(REF INT lhs)INT: lhs+:=1;
OP PREDEC=(REF INT lhs)INT: lhs-:=1;
 
PRIO BOR=2,BAND=3;# Caution: should be 3.2 and 3.3 #
OP BOR=(INT a,b)INT:ABS (SBIN a OR SBIN b);
OP BAND=(INT a,b)INT:ABS (SBIN a&SBIN b);
OP BOR=(INT a,BOOL b)INT: a BOR ABS b;
OP BOR=(BOOL a,INT b)INT: ABS a BOR b;
OP BAND=(INT a,BOOL b)INT: a BAND ABS b;
OP BAND=(BOOL a,INT b)INT: ABS a BAND b;
 
OP NOT=(INT i)INT: ABS(i=0);
 
PROC ww=VOID: BEGIN
  bb:=b;
# FOR # INT p:=21;WHILE p<99 DO
# Uncomment 'unicode' to show graphics in Linux, Jul/04/2011 O.T.G. #
    piece OF element[p]:=#unicode# pieces[ii[p] BAND z];
    moved OF element[p]:=p=bb;
    p+:=(SBA(p%*x-8)|1|3)
  OD
END;
 
PROC xx=(INT w,c,h,e,ss,s)INT: BEGIN
  INT out;
  INT t,o,ll,ee,d,oo:=e,
  INT nn:=-mm*mm,
  INT kk:=78-h<<x,p,g,n,m,aa,q,r,cc,jj,a:=(SBA y|-x|x);
 
  y XORAB 8;
  INC gg;
  d:=ABS(SBA w OREL ((SBA s ANDTH s>=h ) ANDTH xx(0,0,0,21,0,0)>mm ));
  WHILE (
    IF SBA(o:=ii[p:=oo])THEN
      q:=o BAND z XOR y;
      IF q<7 THEN
        aa:=(SBA(POSTDEC q BAND 2)|8|4);
        cc:=(SBA(o-9 BAND z)|(q+1|53,47,61,51,47,47)|57);
        WHILE (
          r:=ii[p+:=l[cc]];
          IF SBA(NOT w BOR p=w)THEN
            g:=(SBA(q BOR p+a-ss)|0|ss);
            IF ((SBA(NOT r BAND SBA(NOT NOT q BOR aa<3)) OREL SBA NOT NOT g) OREL ((r+1 BAND z XOR y)>9 ANDTH SBA(q BOR aa>2)))THEN
              IF SBA(m:=NOT (r-2 BAND 7))THEN y XORAB 8;ii[POSTDEC gg]:=oo;out:=kk;return FI;
              jj:=n:=o BAND z;
              ee:=ii[p-a] BAND z;
              t:=(SBA(q BOR ee-7)|n|n+:=2;6 XOR y);
              WHILE n<=t DO
                ll:=(SBA r|l[r BAND 7 BOR 32]-h-q|0);
                IF SBA s THEN ll+:=(SBA(1-q)|
                  l[(p-p%*x)%x+37]-l[(oo-oo%*x)%x+37]+ l[p%*x+38]*(SBA q|1|2)-l[oo%*x+38]+ (o BAND 16)%2|NOT NOT m*9)+ (SBA NOT q|
                NOT (ii[p-1] XOR n)+NOT (ii[p+1] XOR n)+ l[n BAND 7 BOR 32]-99+ NOT NOT g*99+ABS(aa<2)|0)+ NOT (ee XOR y XOR 9) FI;
                IF s>h OREL ((1<s #B#&s=h ) ANDTH SBA(ll>z BOR d)) THEN
                  ii[p]:=n;ii[oo]:=(SBA m|(ii[g]:=ii[m];ii[m]:=0)|(SBA g|ii[g]:=0|0));
                  ll-:=xx((SBA(s>h BOR d#?#)|0|p),ll-nn,h+1,ii[gg+1],jj:=(SBA(q BOR aa>1)|0|p),s);
                  IF SBA NOT ((((SBA h OREL SBA(s-1 BOR bb-oo) ) BOR i-n ) BOR p-b ) BOR ll<-mm) THEN ww;DEC gg;u:=jj;out:=u;return FI;
                  jj:=ABS(((SBA(q-1 BOR aa<7) OREL SBA m) OREL SBA(NOT s BOR d BOR r BOR o<z) ) OREL xx(0,0,0,21,0,0)>mm);
                  ii[oo]:=o;
                  ii[p]:=r;
                  (SBA m|(ii[m]:=ii[g];ii[g]:=0)|(SBA g|ii[g]:=9 XOR y|0) )
                FI;
                IF ll>nn OREL (((s>1 ANDTH ll=nn) ANDTH SBA NOT h) ANDTH next random<.4) THEN
                  ii[gg]:=oo;
                  IF s>1 THEN
                    IF SBA h ANDTH c-ll<0 THEN y XORAB 8;DEC gg;out:=ll;return FI;
                    IF SBA NOT h THEN i:=n;bb:=oo;b:=p FI
                  FI;
                  nn:=ll
                FI;
                n+:=ABS(SBA jj OREL SBA (g:=p;m:=(p<oo|g-3|g+2);((SBA(ii[m]<z BOR ii[ m+oo-p])) OREL SBA ii[p+:=p-oo])|1|0))
              OD
            FI
          FI;
        # WHILE # (SBA(NOT r BAND ABS(q>2)) OREL (p:=oo;SBA(q BOR aa>2 BOR o>z BAND NOT r) ANDTH SBA(PREINC cc * PREDEC aa)))
        ) DO ~ OD
      FI
    FI;
  # WHILE # SBA(PREINC oo>98|oo:=20|e-oo)
  ) DO ~ OD;
  y XORAB 8;DEC gg;out:=(SBA(nn+mm*mm) ANDTH SBA(ABS(nn>-kk+1924) BOR d)|nn|0);
  return: out
END;
bb:=i:=y:=u:=0;
WHILE POSTINC bb<120 DO
  ii[bb-1]:=(SBA(bb%*x)|
    (bb%x%*x<2 #B#OR bb%*x<2|7|
      (SBA(bb%x BAND 4)|0|l[POSTINC i] BOR 16) )
|7)
OD;
 
MODE ELEMENT=STRUCT (
  STRING piece,
  BOOL moved,
  INT index
);
 
[0:98#?#]ELEMENT element;
FOR i FROM LWB element TO UPB element DO # ~ Extra #
  element[i]:=("",FALSE,0)
OD;
 
PROC print page=VOID:(
  STRING a:=" ";
  FOR i TO 8 DO a+:=" "+REPR(ABS "a"+i-1) OD;
  a+:=REPR 10;
  FOR bb FROM 0 TO 8-1 DO
    a+:=whole(8-bb,-0);
    STRING sep:=" ";
    FOR i FROM 21 TO 29-1 DO
      INT id=bb*x+i;
      STRING sq:=piece OF element[id];
      ((ODD bb=ODD id)&sq=" "|sq:="+" );
      IF moved OF element[id] THEN
        a+:="["+sq+"]";sep:=""
      ELSE
        a+:=sep+sq;sep:=" "
      FI
    OD;
    a+:=sep+REPR 10
  OD;
  print(a); print(new line)
);
 
[]STRING pieces=[]STRING(" ","♟","♚","♞","♝","♜","♛",~,~,"♙","♔","♘","♗","♖","♕")[@0],
   ascii pieces=[]STRING(" ","p","k","n","b","r","q",~,~,"P","K","N","B","R","Q")[@0];

 
ww;
 
PROC yy=(INT s)VOID: BEGIN
  i:=(ii[s] XOR y) BAND z;
  IF i>8 THEN
    b:=s;
    ww
  ELIF SBA bb ANDTH i<9 THEN
    b:=s;
    i:=ii[bb] BAND z;
    IF (i BAND 7)=1 #B#& (b<29 #B#OR b>90) THEN i:=14-index OF element[0] XOR y FI;
    xx(0,0,0,21,u,1);
    IF SBA y THEN xx(0,0,0,21,u,3#ply#);xx(0,0,0,21,u,1) FI
  FI
END;
 
first random(ENTIER(seconds*1024));
 
WHILE
  [2]CHAR move;
  print page;
  print("Enter your move: ");
  read(move);print(new line);
# WHILE # NOT string in string(move,NIL,"win won lose loss draw stalemate quit exit") DO
  INT imove:=ABS move[1]-ABS "a"+(ABS "9" - ABS move[2])*10+11;
  IF LWB ii > imove ORF imove > UPB ii THEN
    print(("Enter moves as eg: g2<enter>g3<enter>..., or 'qu' to quit", new line))
  ELSE
    yy(imove)
  FI
OD

Wednesday, March 9, 2016

The sun rising and Algol68's parallel matrix multi[plication...

The sun rose again this morning and presented me with the urge to multiply a matrix with its own inverse... ;-)

I posted the below set of Algol68 Linear Algebra Operators sometime back, code could do with an update to handle sparse matrices... but as it stands it is a cute example of how you can use those extra CPUs and FPUs on your modern laptop...  The next step (ignoring stability) might be to augment with Strassen's O(n^log2(7)) recursive matrix multiplication algorithm, but again using Algol68's parallel processing... O(n^log2(7))/n(cpus) ... Enjoy!

int default upb := 3;
mode field = long real;
mode vector = [default upb]field;
mode matrix = [default upb, default upb]field;

¢ crude exception handling ¢
proc void raise index error := void: goto exception index error;

sema idle cpus = level ( 8 - 1 ); ¢ 8 = number of CPU cores minus parent CPU ¢

¢ define a operators to slice array into quarters ¢
op top = (matrix m)int: ( ⌊m + ⌈m ) %2,
   bot = (matrix m)int: top m + 1,
   left = (matrix m)int: ( 2 ⌊m + 2 ⌈m ) %2,
   right = (matrix m)int: left m + 1,
   left = (vector v)int: ( ⌊v + ⌈v ) %2,
   right = (vector v)int: left v + 1; 
prio top = 8, bot = 8, left = 8, right = 8; ¢ Operator priority - same as LWB & UPB ¢

op × = (vector a, b)field: ( ¢ dot product ¢
  if (⌊a, ⌈a) ≠ (⌊b, ⌈b) then raise index error fi;
  if ⌊a = ⌈a then
    a[⌈a] × b[⌈b]
  else
    field begin, end;
    []proc void schedule=( ¢ of threads ¢
      void: begin:=a[:left a] × b[:left b], 
      void: end  :=a[right a:] × b[right b:]
    );
    if level idle cpus = 0 then ¢ use current CPU ¢
      for thread to ⌈schedule do schedule[thread] od
    else 
      par ( ¢ run vector in parallel ¢
        schedule[1], ¢ assume parent CPU ¢
        ( ↓idle cpus; schedule[2]; ↑idle cpus)
      ) 
    fi;
    begin+end
  fi
);

op × = (matrix a, b)matrix: ¢ matrix multiply ¢
  if (⌊a, 2 ⌊b) = (⌈a, 2 ⌈b) then
    a[⌊a, ] × b[, 2 ⌈b] ¢ dot product ¢
  else
    [⌈a, 2 ⌈b] field out;
    if (2 ⌊a, 2 ⌈a) ≠ (⌊b, ⌈b) then raise index error fi;
    []struct(bool required, proc void thread) schedule = ( ¢ of threads ¢
      ( true, ¢ calculate top left corner ¢
        void: out[:top a, :left b] := a[:top a, ] × b[, :left b]), 
      ( ⌊a ≠ ⌈a, ¢ calculate bottom left corner ¢
        void: out[bot a:, :left b] := a[bot a:, ] × b[, :left b]), 
      ( 2 ⌊b ≠ 2 ⌈b, ¢ calculate top right corner ¢
        void: out[:top a, right b:] := a[:top a, ] × b[, right b:]), 
      ( (⌊a, 2 ⌊b) ≠ (⌈a, 2 ⌈b) , ¢ calculate bottom right corner ¢
        void: out[bot a:, right b:] := a[bot a:, ] × b[, right b:])
    );
    if level idle cpus = 0 then ¢ use current CPU ¢
      for thread to ⌈schedule do (required →schedule[thread] | thread →schedule[thread] ) od
    else 
      par ( ¢ run vector in parallel ¢
        thread →schedule[1], ¢ thread is always required, and assume parent CPU ¢
        ( required →schedule[4] | ↓idle cpus; thread →schedule[4]; ↑idle cpus),
           ¢ try to do opposite corners of matrix in parallel if CPUs are limited ¢
        ( required →schedule[3] | ↓idle cpus; thread →schedule[3]; ↑idle cpus),
        ( required →schedule[2] | ↓idle cpus; thread →schedule[2]; ↑idle cpus)
      )
    fi;
    out
  fi;

format real fmt = $g(-6,2)$; ¢ width of 6, with no '+' sign, 2 decimals ¢
proc real matrix printf= (format real fmt, matrix m)void:(
  format vector fmt = $"("n(2 ⌈m-1)(f(real fmt)",")f(real fmt)")"$;
  format matrix fmt = $x"("n(⌈m-1)(f(vector fmt)","lxx)f(vector fmt)");"$;
  ¢ finally print the result ¢
  printf((matrix fmt,m))
);

¢ Some sample matrices to test ¢
matrix a=((1,  1,  1,   1), ¢ matrix A ¢
          (2,  4,  8,  16),
          (3,  9, 27,  81),
          (4, 16, 64, 256));

matrix b=((  4  , -3  ,  4/3,  -1/4 ), ¢ matrix B ¢
          (-13/3, 19/4, -7/3,  11/24),
          (  3/2, -2  ,  7/6,  -1/4 ),
          ( -1/6,  1/4, -1/6,   1/24));

matrix c = a × b; ¢ actual multiplication example of A x B ¢

print((" A x B = Product of a and b",new line));
real matrix printf(real fmt, c).

exception index error: 
  putf(stand error, $x"Exception: index error."l$)
 
Output:
 A x B = Product of a and b
  (( 1.00, -0.00, -0.00, -0.00),
   ( -0.00, 1.00, -0.00, -0.00),
   ( -0.00, -0.00, 1.00, -0.00),
   ( -0.00, -0.00, -0.00, 1.00));

Friday, October 30, 2015

Sometimes Python's multiple inheritance has me scratching my head...

I was trying to figure out and demonstrate python's Member Resolution Order (python2.7)... In particular, in the following, I suggest you pay attention to the member functions __new__ and __init__. Bear in mind that the following code (save for the calls to functions 'begin' & 'end') use only the minimum of code infrastructure to create subclass Class ABC from ClassAB and ClassAC (of ClassA) using multiple inheritance. If you wondered why this was so hard, then read on...
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
depth=0
 
def begin(*arg_l,**arg_d):
  global depth
  print "  "*depth+"BEGIN",arg_l,",".join("%s=%s"%item for item in arg_d.items())
  depth+=1
 
def end(*arg_l):
  global depth
  depth-=1
  print "  "*depth+"END",arg_l
 
class ClassA(object): 
 
  def __new__(SubClass,a,kwA="kwA",*arg_l,**arg_d):
    begin("new.ClassA",SubClass,a,*arg_l,**arg_d)
    out_instance=super(ClassA,SubClass).__new__(SubClass,*arg_l) # ,**arg_d) # IGNORE init kwabc
# ./new_init.py:99: DeprecationWarning: object.__new__() takes no parameters
    end("new.ClassA INSTANCE!",out_instance)
    return out_instance
 
  def __init__(self,a,kwa="kwa",*arg_l,**arg_d):
    begin("init.ClassA",self,a,*arg_l,**arg_d)
    none=super(ClassA,self).__init__(*arg_l) # ,**arg_d) # IGNORE new kwABC
# ./new_init.py:99: DeprecationWarning: object.__init__() takes no parameters
    end("init.ClassA",none)
    return none # Always None
 
class ClassAB(ClassA):
  def __new__(SubClass,ab,ac,a,kwAB="kwAB",*arg_l,**arg_d):
    begin("new.ClassAB",SubClass,ab,ac,a,*arg_l,**arg_d)
    out_instance=super(ClassAB,SubClass).__new__(SubClass,ac,a,*arg_l,**arg_d)
    end("new.ClassAB INSTANCE!",out_instance)
    return out_instance
  def __init__(self,ab,ac,a,kwab="kwab",*arg_l,**arg_d):
    begin("init.ClassAB",self,ab,ac,a,*arg_l,**arg_d)
    none=super(ClassAB,self).__init__(ac,a,*arg_l,**arg_d)
    end("init.ClassAB",none)
    return none # Always None
 
class ClassAC(ClassA):
  def __new__(SubClass,ac,a,kwAC="kwAC",*arg_l,**arg_d):
    begin("new.ClassAC",SubClass,ac,a,*arg_l,**arg_d)
    out_instance=super(ClassAC,SubClass).__new__(SubClass,a,*arg_l,**arg_d)
    end("new.ClassAC INSTANCE!",out_instance)
    return out_instance
  def __init__(self,ac,a,kwac="kwac",*arg_l,**arg_d):
    begin("init.ClassAC",self,ac,a,*arg_l,**arg_d)
    none=super(ClassAC,self).__init__(a,*arg_l,**arg_d)
    end("init.ClassAC",none)
    return none # Always None
 
class ClassABC(ClassAB,ClassAC):
  def __new__(SubClass,abc,ab,ac,a,kwABC="kwABC",*arg_l,**arg_d):
    begin("new.ClassABC",SubClass,abc,ab,ac,a,*arg_l,**arg_d)
    out_instance=super(ClassABC,SubClass).__new__(SubClass,ab,ac,a,*arg_l,**arg_d)
    end("new.ClassABC INSTANCE!",out_instance)
    return out_instance
  def __init__(self,abc,ab,ac,a,kwabc="kwabc",*arg_l,**arg_d):
    begin("init.ClassABC",self,abc,ab,ac,a,*arg_l,**arg_d)
    none=super(ClassABC,self).__init__(ab,ac,a,*arg_l,**arg_d)
    end("init.ClassABC",none)
    return none # Always None
 
print ClassABC(
  "ABC","AB","AC","A",
  kwABC="kwABC",kwAB="kwAB",kwAC="kwAC",kwA="kwA",
  kwabc="kwabc",kwab="kwab",kwac="kwac",kwa="kwa"
)
 

Output:

 
BEGIN ('new.ClassABC', <class '__main__.ClassABC'>, 'ABC', 'AB', 'AC', 'A') kwa=kwa,kwA=kwA,kwabc=kwabc,kwAC=kwAC,kwab=kwab,kwac=kwac,kwAB=kwAB
  BEGIN ('new.ClassAB', <class '__main__.ClassABC'>, 'AB', 'AC', 'A') kwa=kwa,kwA=kwA,kwabc=kwabc,kwac=kwac,kwab=kwab,kwAC=kwAC
    BEGIN ('new.ClassAC', <class '__main__.ClassABC'>, 'AC', 'A') kwa=kwa,kwA=kwA,kwabc=kwabc,kwac=kwac,kwab=kwab
      BEGIN ('new.ClassA', <class '__main__.ClassABC'>, 'A') kwa=kwa,kwab=kwab,kwac=kwac,kwabc=kwabc
      END ('new.ClassA INSTANCE!', <__main__.ClassABC object at 0x7f631d0bd4d0>)
    END ('new.ClassAC INSTANCE!', <__main__.ClassABC object at 0x7f631d0bd4d0>)
  END ('new.ClassAB INSTANCE!', <__main__.ClassABC object at 0x7f631d0bd4d0>)
END ('new.ClassABC INSTANCE!', <__main__.ClassABC object at 0x7f631d0bd4d0>)
BEGIN ('init.ClassABC', <__main__.ClassABC object at 0x7f631d0bd4d0>, 'ABC', 'AB', 'AC', 'A') kwa=kwa,kwA=kwA,kwABC=kwABC,kwAC=kwAC,kwab=kwab,kwac=kwac,kwAB=kwAB
  BEGIN ('init.ClassAB', <__main__.ClassABC object at 0x7f631d0bd4d0>, 'AB', 'AC', 'A') kwa=kwa,kwA=kwA,kwABC=kwABC,kwac=kwac,kwAB=kwAB,kwAC=kwAC
    BEGIN ('init.ClassAC', <__main__.ClassABC object at 0x7f631d0bd4d0>, 'AC', 'A') kwa=kwa,kwA=kwA,kwABC=kwABC,kwAC=kwAC,kwAB=kwAB
      BEGIN ('init.ClassA', <__main__.ClassABC object at 0x7f631d0bd4d0>, 'A') kwA=kwA,kwAB=kwAB,kwAC=kwAC,kwABC=kwABC
      END ('init.ClassA', None)
    END ('init.ClassAC', None)
  END ('init.ClassAB', None)
END ('init.ClassABC', None)
<__main__.ClassABC object at 0x7f631d0bd4d0>

Conclusion:

Similar to a MS-Word Template document, Python classes appear temptingly easy, that is until you need to do multiple inheritance, and then there is copious amounts of syntactic-salt & syntactic-vinegar that the coder needs carefully balance to get the right taste.
Note that arg_l is virtually unusable because of a clash with keyword arguments. And positional arguments need to be carefully counted and consumed, otherwise each class with "TypeError: __new__() got multiple values for keyword argument 'kwABC'". Even restricting yourself to keyword arguments only is problematic, in particular __new__ and __init__ of the same should "consume" exactly the same keyword argument, otherwise you will get the warnings: "DeprecationWarning: object.__init__() takes no parameters" etc.
However... maybe... with an appropriate argument naming convention the probability of a coder putting bullet hole in their own foot would be reduced.
Hints welcomed.

Thursday, September 10, 2015

Algol68 code samples, view on-line...

View... and then run on-line...

Maybe you want to hack your first "Hello, world!" program and run it on-line right NOW:
To see how easy Concurrent computing is, paste this specimen:
  PAR(
    print("Enjoy "),
    print("Rosetta "),
    print("Code ")
  )

See also: Have you ever wanted to test drive Algol68?... are ANY of the rumours true?

The Algol68 code specimen samples:

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Y

Z