We are pleased to announce that details of the "ILC 2007 Programming
Contest" will be revealed at 14:00 GMT on Saturday 2007-02-03
(universal time 3379500000). The contest will involve playing a
game. Prizes in various categories will be awarded at the conference.
http://www.international-lisp-conference.org/2007/contest
Have fun.
- nick
Contest goes live in just over an hours time. Enjoy.
- nick
On 19 Jan, 15:29, "Nick Levine" <····@ravenbrook.com> wrote:
> We are pleased to announce that details of the "ILC 2007 Programming
> Contest" will be revealed at 14:00 GMT on Saturday 2007-02-03
> (universal time 3379500000). The contest will involve playing a
> game. Prizes in various categories will be awarded at the conference.
>
> http://www.international-lisp-conference.org/2007/contest
>
> Have fun.
>
> - nick
On Sat, 03 Feb 2007 13:44:25 +0100, Nick Levine <···@ravenbrook.com> wrote:
> Contest goes live in just over an hours time. Enjoy.
>
> - nick
>
>
> On 19 Jan, 15:29, "Nick Levine" <····@ravenbrook.com> wrote:
>> We are pleased to announce that details of the "ILC 2007 Programming
>> Contest" will be revealed at 14:00 GMT on Saturday 2007-02-03
>> (universal time 3379500000). The contest will involve playing a
>> game. Prizes in various categories will be awarded at the conference.
>>
>> http://www.international-lisp-conference.org/2007/contest
>>
>> Have fun.
>>
>> - nick
>
>
Sound fun. Of course the contest was only revealed after the deadline was
over.
I note that you are one of the judges.
Never the less I think I will have a shot at creating my own version.
There is a alternate algorithm for Hex created by Claude Shannon that I
think
could be adapted to this [1]. Should be a lot faster than minimax and more
suited for the
problem. As before I will display the source for a playable version in my
website [2].
1. http://home.earthlink.net/~vanshel/VAnshelevich-01.pdf
2. http://home.chello.no/~jthing
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Sat, 03 Feb 2007 15:47:51 +0100, John Thingstad
<··············@chello.no> wrote:
>
> Sound fun. Of course the contest was only revealed after the deadline
> was over.
Oops. Blinked on the date.
"The deadline for submissions will be 2pm GMT on Saturday 2007-03-03"
So actually one month from now.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad wrote:
> There is a alternate algorithm for Hex created by Claude Shannon that I
> think
> could be adapted to this [1]. Should be a lot faster than minimax and more
> suited for the problem.
Some time ago I wrote a Hex implementation ( http://jhex.sf.net/ ), which
uses a minimax algorithm and I don't see how this algorithm or the resistor
network or theorem proving algorithm described by the paper can be applied
to a single player Continuo game. But in general the idea to use a theorem
prover might be a good idea, but requires some research to find some good
theorems.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 3 Feb 2007 04:44:25 -0800, "Nick Levine" <···@ravenbrook.com> tried to
confuse everyone with this message:
>Contest goes live in just over an hours time. Enjoy.
>
"In order to qualify for a prize, the entrant must register for at least one day
of the conference."
So, is there a point in participiating if I don't plan to visit the conference?
--
|Don't believe this - you're not worthless ,gr---------.ru
|It's us against millions and we can't take them all... | ue il |
|But we can take them on! | @ma |
| (A Wilhelm Scream - The Rip) |______________|
On Sat, 03 Feb 2007 17:25:31 +0100, Timofei Shatrov <····@mail.ru> wrote:
> On 3 Feb 2007 04:44:25 -0800, "Nick Levine" <···@ravenbrook.com> tried to
> confuse everyone with this message:
>
>> Contest goes live in just over an hours time. Enjoy.
>>
>
> "In order to qualify for a prize, the entrant must register for at least
> one day
> of the conference."
>
> So, is there a point in participiating if I don't plan to visit the
> conference?
>
No! Price for registering for the entire conference is 350�.
For one day 150�. the price on the other hand if just a medal.
I'll make a solution just for fun, but will only publish after
the 3/3-2007 when the contest expires so as not to bias the
outcome (any further).
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
I wondered how the rules for the 42 cards were. I think it is the following:
(defun all-cards ()
(let ((result '()))
(loop for i in '(R G B Y) do
(loop for j in '(R G B Y) do
(loop for k in '(R G B Y) do
(loop for l in '(R G B Y) do
(when (and (unpaired i j k l)
(no-four-colours i j k l)
(unique i j k l result))
(push (list i j k l) result))))))
result))
(defun unpaired (a b c d)
(not (or (eq a b) (eq b c) (eq c d))))
(defun no-four-colours (a b c d)
(or (eq a b) (eq a c) (eq a d) (eq b c) (eq b d) (eq c d)))
(defun unique (a b c d list)
(not (find (reverse (list a b c d)) list :test #'equal)))
CL-USER> (all-cards)
((Y G B Y) (Y R B Y) (Y R G Y) (B Y B Y) (B Y G Y) (B Y R Y) (B G Y B)
(B G B Y) (B R Y B) (B R B Y) (B R G B) (G Y B Y) (G Y G Y) (G Y G B)
(G Y R Y) (G B Y B) (G B Y G) (G B G Y) (G B G B) (G B R B) (G R Y G)
(G R B G) (G R G Y) (G R G B) (R Y B Y) (R Y G Y) (R Y R Y) (R Y R B)
(R Y R G) (R B Y B) (R B Y R) (R B G B) (R B R Y) (R B R B) (R B R G)
(R G Y G) (R G Y R) (R G B G) (R G B R) (R G R Y) (R G R B) (R G R G))
CL-USER> (length *)
42
So, we don't have to build Deep Thought.
--
Bernd
Two algorithms come into my mind:
1) Consider the current card only an try to get maximum score at one time.
2) Because the cards are known, a kind of backtracking algorithm can be
used for the current card and the remaining cards, in order to increase
the score. (Algorithm #1 can be emulated with depth=1).
I'm not sure whether #2 will produce better results with random cards
stacks.
--
Bernd
On Sat, 03 Feb 2007 17:38:43 +0100, Bernd Beuster <·············@lycos.de>
wrote:
> I wondered how the rules for the 42 cards were. I think it is the
> following:
>
> (defun all-cards ()
> (let ((result '()))
> (loop for i in '(R G B Y) do
> (loop for j in '(R G B Y) do
> (loop for k in '(R G B Y) do
> (loop for l in '(R G B Y) do
> (when (and (unpaired i j k l)
> (no-four-colours i j k l)
> (unique i j k l result))
> (push (list i j k l) result))))))
> result))
>
>
> (defun unpaired (a b c d)
> (not (or (eq a b) (eq b c) (eq c d))))
>
>
> (defun no-four-colours (a b c d)
> (or (eq a b) (eq a c) (eq a d) (eq b c) (eq b d) (eq c d)))
>
>
> (defun unique (a b c d list)
> (not (find (reverse (list a b c d)) list :test #'equal)))
>
>
Or using some more general functions:
(defun number-base (number base length)
"Given a number a base and a length return a string of length characters
containing
number expressed in that base right justified.
ex: (number-base 5 2 4) --> "0101")
(let* ((*print-base* base)
(*print-pretty* nil)
(array (make-string base :initial-element #\0))
(string (string-trim '(#\Space #\NewLine)
(with-output-to-string (stream)
(print number stream)))))
(loop with start-pos = (- base (length string))
for ch across string
for i from 0 do
(setf (aref array (+ start-pos i)) ch))
array))
(defun to-number (character)
(- (char-code character) (char-code #\0)))
(defun permute (list function)
(let* ((length (length list))
(array (make-array length :initial-contents list))
(*print-base* length))
(dotimes (i (expt length length))
(funcall function
(loop for ch across (number-base i length length)
collect (aref array (to-number ch)))))))
(defmacro with-permutations ((element list) &body body)
`(permute ,list (lambda (,element) (progn ,@body))))
(defun unpaired-p (list)
(loop with match = nil
for rest on list do
(when (equal (first rest) (second rest))
(setf match t))
finally (return (not match))))
(defun dissimular-p (list)
(if (or (atom list) (= (length list) 1))
nil
(not (= (1- (length list))
(loop with first = (first list)
for element in (rest list)
summing (if (equal first element) 1 0))))))
(defun no-four-colours (list)
(destructuring-bind (a b c d) list
(or (eq a b) (eq a c) (eq a d) (eq b c) (eq b d) (eq c d))))
(defun unique-p (element list)
(null (find element list :test #'equal)))
(defun all-cards ()
(let (result)
(with-permutations (element '(R G Y B))
(when (and (unpaired-p element)
(no-four-colours element)
(unique-p (reverse element) result))
(push element result)))
result))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Sat, 03 Feb 2007 22:02:52 +0100, John Thingstad
<··············@chello.no> wrote:
Oops.. Missed some last minute corrections
> (defun number-base (number base length)
> "Given a number a base and a length return a string of length
> characters containing
> number expressed in that base right justified.
> ex: (number-base 5 2 4) --> "0101")
> (let* ((*print-base* base)
> (*print-pretty* nil)
(array (make-string length :initial-element #\0))
> (string (string-trim '(#\Space #\NewLine)
> (with-output-to-string (stream)
> (print number stream)))))
(loop with start-pos = (- length (length string))
> for ch across string
> for i from 0 do
> (setf (aref array (+ start-pos i)) ch))
> array))
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Sat, 03 Feb 2007 22:02:52 +0100, John Thingstad
<··············@chello.no> wrote:
(defun number-base (number base length)
"Given a number a base and a length return a string of length characters
containing number expressed in base radix right justified.
ex: (number-base 5 2 4) --> 0101"
(let* ((*print-base* base)
(*print-pretty* nil)
(array (make-string length :initial-element #\0))
(string (string-trim '(#\Space #\NewLine)
(with-output-to-string (stream)
(print number stream)))))
(loop for i = (- length (length string)) then (1+ i)
for ch across string
(setf (aref array i) ch))
array))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> On Sat, 03 Feb 2007 22:02:52 +0100, John Thingstad
> <··············@chello.no> wrote:
>
> (defun number-base (number base length)
> "Given a number a base and a length return a string of length characters
> containing number expressed in base radix right justified.
> ex: (number-base 5 2 4) --> 0101"
> (let* ((*print-base* base)
> (*print-pretty* nil)
> (array (make-string length :initial-element #\0))
> (string (string-trim '(#\Space #\NewLine)
> (with-output-to-string (stream)
> (print number stream)))))
PRIN1-TO-STRING
> (loop for i = (- length (length string)) then (1+ i)
> for ch across string
> (setf (aref array i) ch))
> array))
WRITE-TO-STRING
Or just FORMAT:
(defun number-base (number base width)
(format nil "~V,V,'0R" base width number))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pour moi, la grande question n'a jamais �t�: �Qui suis-je? O� vais-je?�
comme l'a formul� si adroitement notre ami Pascal, mais plut�t:
�Comment vais-je m'en tirer?� -- Jean Yanne
Nick Levine wrote:
> http://www.international-lisp-conference.org/2007/contest
Nice contest. To make it more interesting, I don't think that source code
or card sequences should be published before the end of the contest, but if
someone wants to compare how good an alogrithm is, I suggest the following
random test:
(defun test ()
(clear)
(loop for card in
'(:GYGB :RBYR :BRBY :BGBY :GYRY :GRGB :BRYB
:RGYR :GRGY :YRBY :RYRB :BGYB :RGYG :BYGY
:BYBY :BYRY :BRGB :RBGB :RYRY :GRBG :RBRY
:GBRB :RGBR :YRGY :RYGY :GRYG :GYGY :YGBY
:RGRG :RGRB :RBRG :RGRY :RBRB :GBYB :GBYG
:RGBG :RBYB :GBGY :GBGB :RYBY :GYBY :RYRG)
sum (car (last (play card)))))
Don't optimize the algorithm for this sequence, but write it like explained
on the contest web page: the play function is called for each move and
requires a move decision for each call.
My first naive implementation, which may be wrong, results in 778.
I've setup a wiki for recording the scores:
http://ilc-contest.pbwiki.com/
Password is ilc2007
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> My first naive implementation, which may be wrong, results in 778.
And it looks a bit like modern art :-)
http://www.frank-buss.de/tmp/continuo.png
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss schrieb:
>> My first naive implementation, which may be wrong, results in 778.
>
> And it looks a bit like modern art :-)
>
> http://www.frank-buss.de/tmp/continuo.png
Nice! BTW, how is the rule for 1st card :RBRB and 2nd card :GYGY?
- keep in hand
- or, put it back to the deck and draw again
- or, place it freely
- or, ...
--
Bernd
Bernd Beuster wrote:
> Nice! BTW, how is the rule for 1st card :RBRB and 2nd card :GYGY?
>
> - keep in hand
> - or, put it back to the deck and draw again
> - or, place it freely
> - or, ...
I'll try to give a more formal description of the contest rules: There are
42 cards (see other postings for the list) and you'll get one after the
other each turn, in random order, until all cards are placed, but with the
same sequence for each contest program. A card is made up of 4x4 cells.
Each card has to be placed, no cards in hand, no put back. Valid placing
means no cell overlaps a cell of an already placed card and possible places
are at grid position, where grid resolution is cell size, and adjacent to
at least one other card. Adjacent means that at least one cell of the new
card and one cell of an already placed card are adjacent. Adjacent cells
are cells which shares one side. Scoring a card placement means summing
chains. A chain is made up of adjacent cells of the same color. All chains
are summed, which span the new card and at least one other card. The sum of
a chain is the number of cells in this chain. Summed chains are not
remembered, the next card can sum them again, if all other rules are
matched. The final score of one game is the sum of each card placement
score. One winning rule is to write a program which achieves the highest
score.
With these rules the score for the 2nd placement for 1st card :RBRB and 2nd
card :GYGY is 0, but you have to place the 2nd card adjacent to the 1st
card.
Maybe this description could be used for a straight forward implementation
with a rule based system like Prolog?
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
I just noticed that I'm one of the eight winners of the contest at
http://www.international-lisp-conference.org/2007/contest
This is my program:
http://www.frank-buss.de/ilc2007/continuo.lisp
Entry points are #'test, which plays the game, #'print-board for
printing the current board (it is global) in ASCII and creating a TGA
output of it and #'cards, which creates all cards of the game as a
postscript file (please don't print out and use it without permission
of the copyright holder of the game).
My algorithm is very straightforward: For every new card, it just
tries every possible placements and tests the score. To make it a bit
faster, I've defined an array, where all cards are placed and
invididual cells are accessible. Some improvement was to add the
weighted distance to the current center of all placements, because my
assumption was, that with clusters you'll get more points later, even
if you could get more game points for the current turn, if you build
long structures, because with clusters, chances are higher that cells
are counted multiple times.
I'm looking forward to the other implementations, especially the head-
to-head play of four algorithms from Peter Salvi, because in
multiplayer mode of this game, there are other interesting things to
do for archieving high scores, or to avoid that the opponent gets too
many points.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de http://www.it4-systems.de
On 1 Apr., 20:46, ····@frank-buss.de wrote:
> I just noticed that I'm one of the eight winners of the contest at
>
> http://www.international-lisp-conference.org/2007/contest
I have to say that I noticed it at a printed paper at the conference,
but now there are all solutions available for downloading at the
contest page. Anyone who wants to write a program for a tournament
between the algorithms :-) ?
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de http://www.it4-systems.de