alexshendi has quit [Read error: No route to host]
rob_w has joined #picolisp
<Nistur>
mornin'
orivej has joined #picolisp
<Regenaxer>
Hi Nistur
NB0X-Matt-CA has quit [Ping timeout: 268 seconds]
NB0X-Matt-CA has joined #picolisp
<Nistur>
hellooo
<razzy>
mornin'
<razzy>
viaken i believe it does
xkapastel has joined #picolisp
<Regenaxer>
Hi razzy
<razzy>
hmm, what if i want two symbols pointing at the same list of data. i want first symbol behave as ussual, pointing at data-list. i want second symbol adressing the same data list in reverse order. so i could cadddr from top of data-list, caddr from bottom of data-list. sort it once. use it as que etc. is there easy way?
<razzy>
push pop from both ends
<Regenaxer>
You must build a doubly-linked list then
<Regenaxer>
ie each element consists of 2 cells
<Regenaxer>
Is that really necessary?
<Regenaxer>
Better use 'fifo' perhaps
<Regenaxer>
or 'pop' and 'rot'/'pop' on a normal list
<Regenaxer>
Also, you can find the cell *before* a given cell with 'prior' if needed
<Regenaxer>
So there are many ways
<Regenaxer>
If you want to go with doubly linked lists: The grid in the lib/simul.l is an example where the cells are linked in all directions
<razzy>
Regenaxer: not necessary. i just thing it is handy. computationally efficient
<Regenaxer>
I don't think it is. Too much overhead
<Regenaxer>
Only for lists longer than say 1000 elements
<Regenaxer>
And then another structure is better
<razzy>
example of better structure?
<Regenaxer>
Depends on *what* you want to do
<razzy>
ok thx
<Regenaxer>
As I said, a 'fifo' is *very* efficient
* razzy
puts another "great" idea in a box
<Regenaxer>
(cdr (rot L)) is fastest to remove a last element
<Regenaxer>
or (con (tail 2 L))
<Regenaxer>
Experiment around with it
<razzy>
what do you think about duplicated data-list?
<Regenaxer>
Possible, but quite complicated, bigger and thus perhaps slower
<razzy>
first sorted from hi second sorted from low
<Regenaxer>
yes, reversed
<Regenaxer>
not necessarily sorted
<razzy>
i have surplus of memory
<Regenaxer>
thats not the point
<Regenaxer>
the structures need to be mbintained on every operation
<Regenaxer>
so slower
<Regenaxer>
unless they are very long lists
<razzy>
maintained?
<Regenaxer>
yes, when changed
<Regenaxer>
maintain the links in all directions
<Regenaxer>
try it!
<Regenaxer>
make an example
<Regenaxer>
It will be slower than operating with normal primitives on a single list
<Regenaxer>
No preliminary optimizations :)
<Regenaxer>
If it ain't broken, don't fix it
<Regenaxer>
Don't solve problems before they exist
<razzy>
aye
<Regenaxer>
"preliminary" was the wrong word - what is the term?
<Regenaxer>
premature?
<razzy>
i would rather think about it as learning oportunity
<razzy>
when you explore future-action tree.
<razzy>
but i agree, i do too much exploring, too little doing
<Regenaxer>
Well, exploring is very good
<Regenaxer>
Good exercise. But in this case it is hard to decide where to start, without a typical use case where it makes sense
<Regenaxer>
eg the 'grid' function builds nodes with links in north, south east and west
<Regenaxer>
so a typical 2-dimensional use case
<Regenaxer>
But for a plain fifo we already have the perfectly efficient 'fifo' function
<Regenaxer>
You can also pop from such a fifo with 'cdr' and 'con'
<razzy>
pop from top? pop from bottom?
<Regenaxer>
no matter how long the list is, because it is a circular list with direct access to the last (and thus the first with 'cadr')
<Regenaxer>
both
<Regenaxer>
Above 'cdr' is wrong, must be 'cadr'
<Regenaxer>
Experiment!
<razzy>
hmm, need to
<Regenaxer>
(fifo 'A 1 2 3)
<Regenaxer>
: A
<Regenaxer>
-> 3
<Regenaxer>
-> (3 1 2 .)
<Regenaxer>
(fifo 'A) pops off the last
<razzy>
hm, circular list could do the job
<Regenaxer>
hehe, 'cadr' is wrong too
<Regenaxer>
no cheap way, needs (rot A) (fifo 'A)
<Regenaxer>
OK, found it
<Regenaxer>
The cheap way is (prog1 (car A) (set A (cadr A)) (con A (cddr A)))
<razzy>
uh i will store it
<Regenaxer>
This pops off '3'
<Regenaxer>
Just (fifo 'A) pops off '1' from the other end
<Regenaxer>
both independent on list length
<Regenaxer>
afp
<razzy>
thx
rob_w has quit [Quit: Leaving]
<Regenaxer>
ret
jibanes has quit [Ping timeout: 252 seconds]
jibanes has joined #picolisp
ubLIX has joined #picolisp
ubLIX has quit [Quit: ubLIX]
ubLIX has joined #picolisp
<razzy>
hmm what about multiple lists that contain same data. is it called list of lists? it is database structure
<Regenaxer>
What do you mean? (a b c) and (d b e) contain the same date, i.e. the symbol 'a'
<razzy>
there was even wiki page. i could not find at the moment
<razzy>
Regenaxer: btw, are you sure that your alphabeta-search go through every possibility? i have problems printing it out
<Regenaxer>
As it is alpha-beta, it does not tarverse the whole tree
<Regenaxer>
for 6 levels about 1/1000
<Regenaxer>
(estimated
<Regenaxer>
I measured 200 thousand 'cost' evaluations
<Regenaxer>
for an estimated 300 to 600 million nodes
<Regenaxer>
So it is quite efficient
<Regenaxer>
It is said chess has a branching factor of 30 per ply
<Regenaxer>
means 720 million positions at 6 levels
<Regenaxer>
(if I calculated right)
<razzy>
hm, i think it make list of every possibility 6 moves ahead,than evaluate best move from maximum depth, than move depth-1 and evaluate best move by cost is answer. am i close or i get it completelly wrong
<Regenaxer>
no, it generates the around 30 moves for each position
<Regenaxer>
then moves the first, and recurses
<Regenaxer>
so a depth-first search
<Regenaxer>
the first branch goes down all 6 levels
<Regenaxer>
then evaluates all 30 positions
<Regenaxer>
the result is backed up one level
<Regenaxer>
then next move on that level down
<Regenaxer>
As soon as finding a worse move, this branch is stopped
<Regenaxer>
In this way it needs to search only a small part of the tree
<Regenaxer>
because the pruned branches are *known* to be worse
<Regenaxer>
the opponent will pick that one, cause it is better for *him*
<Regenaxer>
so we don't need to search it further
<Regenaxer>
(something like that, look up wikipedia for a better description)
<razzy>
hmm i see you guess best move six lvl deep. and than compare others options until worse or better is found
<Regenaxer>
yes
<razzy>
if worse you stop search. if better you start with better one
<Regenaxer>
The point is to sort each level in a way to have a good estimyation
<Regenaxer>
If your guess is good initially, the pruning will be better
<razzy>
reasonably good search
<Regenaxer>
yeah
<razzy>
several asuptionsare made
<Regenaxer>
not many assumptions
<Regenaxer>
it is game theory
<Regenaxer>
zero sum game with full information
<Regenaxer>
So the 'game' function actually calls 'cost' in two places
<Regenaxer>
first to sort the 30 or so generated moves on each level
<Regenaxer>
and finally on the bottom to evaluate the position
<Regenaxer>
ah
<Regenaxer>
So my 200 thousand above are even too high
<Regenaxer>
I counted *all* calls to 'cost'
<razzy>
the assumption i think about is that you assume the cost function is "smooth". and that there are not local maxima.
<Regenaxer>
It does not matter. Just the efficiency is better with a better cost function
<razzy>
with chess i agree
<Regenaxer>
ha!
<razzy>
?
<Regenaxer>
If I call cost only for bottom nodes, it goes down to 85892
<razzy>
bottom nodes?
<Regenaxer>
so not 1/1000 but 1/6000 or so
<Regenaxer>
yes, on depth-first
<Regenaxer>
the nodes at level 6 in this case
<razzy>
i thinked about other improvement. if picochess starts with task finding 6 unique best moved the propability of local maximum is greatly reduced
<Regenaxer>
the final positions investigated
<Regenaxer>
There is no local max or min in alpha/beta
<Regenaxer>
plain discrete comparisons
<Regenaxer>
It is not a genetic algo
<Regenaxer>
see 'gen' in @lib/simul.l btw
<Regenaxer>
for a genetic algorithm
<razzy>
i will look at genetics algo
<razzy>
but i am not sure there are not local maxima. i will have to study your alphabeta :]
alexshendi has quit [Read error: Connection reset by peer]
<Regenaxer>
There is nothing continuous in such game position evaluation
<Regenaxer>
each move may have a dramatically different result
<Regenaxer>
from complete win to complete lose
<razzy>
well, cost function is smoothed out heuristic ussually
<razzy>
less material= worse
<razzy>
btw, for evaluation of branch you are using cost of position at maximum depth right?
<razzy>
which is worst case scenario for picochess player
<Regenaxer>
yes, but also before that on each level to decide *which* move to investigate *first*
<Regenaxer>
As I wrote above
<razzy>
which is prudent
<Regenaxer>
yes
<Regenaxer>
pruned
<razzy>
that too
<Regenaxer>
prudent too :)
<Regenaxer>
So the above test showed about 200 thousand total calls to 'cost', of which 85 thousand were at the final depth
<Regenaxer>
For a theoretical tree of 728 million
<Regenaxer>
729
<Regenaxer>
30^6
<razzy>
yes
<Regenaxer>
Interesting. I never did such measurements before
<Regenaxer>
Just now out of interest
<razzy>
not much to improve here ithink
<Regenaxer>
true
<razzy>
so change the cost function :))
<Regenaxer>
yes, that would be a way
<Regenaxer>
But not simple
<Regenaxer>
not easy
<razzy>
i have plan
<Regenaxer>
ok, good
<razzy>
not easy, but hopefully simple
<Regenaxer>
cool
alexshendi has joined #picolisp
<razzy>
btw, chess people usually find a desired state, and than trying to move towards it. they are doing from-end backward search
<Regenaxer>
yeah, completely different from such a simple algorithm
<Regenaxer>
lots of patterns
<razzy>
i think you were doing it with attacks no?
<razzy>
like "i want to kill that piece" how to do it
<Regenaxer>
I think not. Just simple lists of attackers and material calc
<Regenaxer>
a kind of correction to the material count
<razzy>
hm
<Regenaxer>
the "real" material, after removing pieces which are lost in that situation
<razzy>
that should handle search tree imho
<razzy>
so i will change cost function :]
<razzy>
so it value mobility
<Regenaxer>
Good luck!
<Regenaxer>
Hmm, mobility also just results in board control, ie attacks
<Regenaxer>
Perhaps use a genetic algo
<razzy>
on top of mobility stats
<Regenaxer>
to generate cost functions and let them play against each other
<Regenaxer>
massive parallel
<Regenaxer>
Find the optimal cost function that way
<razzy>
if i do not understand cost function, it will be nightmare
<razzy>
and it need simple bootstrap
<Regenaxer>
hmm
<Regenaxer>
vary parameters and weights in cost
<razzy>
or i could have multiple parameter neural net on top of mobility stats
<razzy>
which is setup gen. algo
<Regenaxer>
perhaps, yes
<Regenaxer>
big project ;)
<razzy>
tear down cost function should be realtively easy
<razzy>
no bigger than picochess
xkapastel has quit [Quit: Connection closed for inactivity]