You can subscribe to this list here.
2004 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}


2005 
_{Jan}
(1) 
_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2009 
_{Jan}

_{Feb}

_{Mar}
(1) 
_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}
(17) 
_{Sep}
(34) 
_{Oct}

_{Nov}

_{Dec}

2010 
_{Jan}

_{Feb}
(100) 
_{Mar}
(122) 
_{Apr}
(5) 
_{May}

_{Jun}
(17) 
_{Jul}
(36) 
_{Aug}
(9) 
_{Sep}
(111) 
_{Oct}
(92) 
_{Nov}
(76) 
_{Dec}
(26) 
2011 
_{Jan}
(3) 
_{Feb}
(35) 
_{Mar}
(36) 
_{Apr}
(10) 
_{May}
(9) 
_{Jun}
(2) 
_{Jul}
(3) 
_{Aug}
(2) 
_{Sep}

_{Oct}
(7) 
_{Nov}
(12) 
_{Dec}

2012 
_{Jan}
(19) 
_{Feb}
(1) 
_{Mar}
(4) 
_{Apr}
(1) 
_{May}
(6) 
_{Jun}
(69) 
_{Jul}
(21) 
_{Aug}
(12) 
_{Sep}
(14) 
_{Oct}
(1) 
_{Nov}
(3) 
_{Dec}

2013 
_{Jan}
(6) 
_{Feb}
(1) 
_{Mar}
(6) 
_{Apr}
(3) 
_{May}
(6) 
_{Jun}
(1) 
_{Jul}

_{Aug}

_{Sep}

_{Oct}
(2) 
_{Nov}
(3) 
_{Dec}

2014 
_{Jan}

_{Feb}

_{Mar}
(6) 
_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 


1
(6) 
2
(4) 
3

4
(1) 
5
(5) 
6

7

8

9
(2) 
10
(2) 
11
(13) 
12
(8) 
13

14
(6) 
15
(8) 
16

17

18

19
(1) 
20
(5) 
21

22

23
(3) 
24

25

26
(4) 
27
(6) 
28

29
(2) 
30





From: Lukasz Kaiser <lukaszkaiser@gm...>  20101129 20:23:49

I just added an extra function matches_post in ContunuousRule and changed the handler in Arena to return the right matches. In this way we get the right moves in the GUI, but functions in Play must check postconditions separately, so beware! This is in a sense a hack, but I think a useful one: we get the right moves and almost no performance penalty. Since postconditions for chess are of the form not (WinningCondition) with just a little smarter hashing we should get them with no performance penalty at all for the alphabeta algorithm in chess. Anyway  for now this hack seems to work well as the chess moves seem to be right and computed in reasonable time. I think that our chess definition is now complete except for rochade and repeatedpositionschecking. Rochade should not be hard and the second thing we might skip for now I think. So we are almost ready, but first please check and test if there are no mistakes with the current moves. I hope not. Best! Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101129 17:46:27

I started defining check in chess, but we need postconditions to work for that  until now we never checked if a postcondition holds. There is a problem with postconditions in our definitions: in the concurrent setting it is much harder to tell if a postcondition will hold or not, this depends on the moves of other players. But we can check assuming noone else moves, does this make sense? And still  the way to check is to do the rewriting and evaluate  it will be bad for performance, even in the current setting. Do you have any ideas how we should handle this? I can change ContinuousRule.matches to filter only these matchings which survive postcondition, but I'm not sure this is the right way to go. And we need postconditions to check if a check occurs after move, so this is practically important. Ideas? Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101127 22:32:43

I made some complete test plays today and while it plays breakthrough quite well at depth 3 and gomoku very nice even at depth 2 I still observed two problems. Problem 1, in BreakthroughTest2. At depth 2 it moves forward even though it will be killed then. Why? In my understanding of alpha_beta this should not happen, but perhaps I misunderstood something. It is ok at depth 3. Problem 2, in GomokuTest4. First note that this is a very good state  white is winning, and this was played against gridlock hard (through GomokuState4) which is very hard to win against even for me. But there is one clear winning move in this state  d4  and at depth 2 white is not taking it and moves to b7  a very funny move, no advance given, so I have no idea for what reason it decides to play that. Once the stuff with formulas and FFSolver is behind us, please take a look at these two problems. We are really near to winning against gridlock in just one order more time, so I find it very exciting. But still one small step to go! Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101127 21:43:08

> reasons and voices against it, I will change the situation and > make subst_vars do the check by default  so please change > to subst_vars_nocheck wherever you really want to avoid it. There seemed to be no reason not to check, so I changed it. Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101127 21:01:37

To be able to use compare performance using mso with firstorder only formulas and solvers I added a less general firstorder version of transitive closure. Writing tc K x, y phi(x, y, z) where K is an integer will generate a Kstep transitive closure (firstorder) formula. If you know an upper bound on the needed number of steps, you might thus replace the general tc with such formulas. Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101127 20:57:22

> but subst_vars_check will return ex y0 R(y0, y). Of course I meant ex y0 R (y, y0) sorry! Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101127 20:55:57

Hi. I just added a new function for substituting free variables in a formula, so we now have the old subst_vars and a new function subst_vars_check. It is good to realize that in most cases you probably want to use the new subst_vars_check, because the old one fails on clashes with quantified vars. Example: subst_vars x < y on ex y R(x, y) gives ex y R(y, y) (!), but subst_vars_check will return ex y0 R(y0, y). If you used subst_vars, please think if it is not a good time to review the code. I added another function subst_vars_nocheck, which at present is an alias to subst_vars. But if there are no reasons and voices against it, I will change the situation and make subst_vars do the check by default  so please change to subst_vars_nocheck wherever you really want to avoid it. Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101127 14:33:33

I just added an extension of our formula syntax to handle transitive closures. A formula of the form: tc x, y phi(x, y, z) will be translated to an MSO formula which denotes the transitive and reflexive closure of phi(x, y) with z free. Note that after the translation the formula has the same set of free variables, so you can write e.g. x != y and not E(x, y) and tc x, y E(x, y) to denote the transitive closure of E excluding equal elements and those already in E. Another example is to say there is a free row from x to y: tc x, y (R(x, y) and free(y)). Lukasz 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101126 19:37:17

> Yes absolutely, this nuance escaped me for a while. I think there are quite a few people who use interpretation for both things, even in papers  but let's stick to the fully nuanced meaning, at least it makes clear what is what :). Lukasz 
From: Lukasz Stafiniak <lukstafi@gm...>  20101126 19:32:52

On Fri, Nov 26, 2010 at 8:19 PM, Lukasz Kaiser <lukaszkaiser@...> wrote: > > If you > use "interpretation" for predicate logic it means the model, i.e. > both the structure in question and the assignment of free variables. Yes absolutely, this nuance escaped me for a while. 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101126 19:19:46

> I've been using the term "substitution" an the shortcuts "subst" and > "sb" where I really should be using terms "assignment" or > "interpretation". Should I go over my code and rename? Is there a > reason that you use "assignment" exclusively and not "interpretation"? In computer science logic, I think the convention is as follows.  "Interpretation" is normally used in the context of propositional logic, i.e. it assigns variables either true or false, 0 or 1. If you use "interpretation" for predicate logic it means the model, i.e. both the structure in question and the assignment of free variables. This is consistent with the use for propositional logic as there the structure is always the same, the Boolean algebra.  "Substitution" is indeed an assignment to variables, but it does assign syntactic object, e.g. other formulas or variables, not semantic objects as in (standard) assignment, which assigns elements  Thus I think "assignment" is right  is assigns to variables of the formula elements of the structure. For propositional logic this is similar to interpretation because the structure (Boolean algebra) is fixed, but normally an interpretation is a pair: structure+assignment. This is why I think the name "assignment" is the correct one. But this is not very important  do not spend too much time on that! Lukasz 
From: Lukasz Stafiniak <lukstafi@gm...>  20101126 16:11:09

I've been using the term "substitution" an the shortcuts "subst" and "sb" where I really should be using terms "assignment" or "interpretation". Should I go over my code and rename? Is there a reason that you use "assignment" exclusively and not "interpretation"? 
From: Lukasz Stafiniak <lukstafi@gm...>  20101123 09:28:51

And now the fixed tree: suggest: toss: alpha_beta_ord ev game, timer started... [   ] "   . P Q   . P .   +Q . . " [   ] "   . P Q   . P .   Q +P . ", leaf 1 heur: 1. [   ] "   . P Q   . P .   Q . +P ", leaf 1 heur: 0.888888888889 [   ] "   . P Q   +P P .   Q . . ", leaf 1 heur: 0.777777777778 [   ] "   . P Q   . P +P   Q . . ", leaf 1 heur: 0.777777777778 [   ] "   +P P Q   . P .   Q . . ", leaf 1 heur: 0.777777777778 , best 0 maximax: 1.. [   ] "   . P Q   . P .   . +Q . " [   ] "   . P Q   . P .   +P Q . ", leaf 1 heur: 0.222222222222 [   ] "   . P Q   . P .   . Q +P ", leaf 1 heur: 0.555555555556 [   ] "   . P Q   +P P .   . Q . ", leaf 1 heur: 0.444444444444 [   ] "   . P Q   . P +P   . Q . ", leaf 1 heur: 0.444444444444 [   ] "   +P P Q   . P .   . Q . ", leaf 1 heur: 0.444444444444 , best 0 maximax: 0.555555555556. [   ] "   . P Q   . P .   . . +Q " [   ] "   . P Q   . P .   +P . Q ", leaf 1 heur: 0.222222222222 [   ] "   . P Q   . P .   . +P Q ", leaf 1 heur: 0.666666666667 , best cut 0 maximax: 0.666666666667. [   ] "   . P Q   +Q P .   . . . " [   ] "   . P Q   Q P .   +P . . ", leaf 1 heur: 0.555555555556 [   ] "   . P Q   Q P .   . +P . ", leaf 1 heur: 1. , best cut 0 maximax: 1.. [   ] "   . P Q   . P +Q   . . . " [   ] "   . P Q   . P Q   +P . . ", leaf 1 heur: 0.333333333333 [   ] "   . P Q   . P Q   . +P . ", leaf 1 heur: 0.777777777778 , best cut 0 maximax: 0.777777777778. [   ] "   +Q P Q   . P .   . . . " [   ] "   Q P Q   . P .   +P . . ", leaf 1 heur: 0.555555555556 [   ] "   Q P Q   . P .   . +P . ", leaf 1 heur: 1. , best cut 0 maximax: 1.. 24 nodes, 145 size, 0.084005 elapsed time moving to state [   ] " . P Q . P . . +Q . " suggest: pos 1 
From: Lukasz Stafiniak <lukstafi@gm...>  20101123 09:22:00

On Tue, Nov 23, 2010 at 10:01 AM, Lukasz Stafiniak <lukstafi@...> wrote: > Gr! I'm sorry. The bug is that the cutoff value is assumed as the > value of the pruned subtree. Then some pruned subtrees, which can > include the worst subtree, have the same value as the best subtree and > one of them is selected randomly. > > I'm sorry to have let it slip through for so long! P.S. I encourage you to use the debug logging when you want to study the results of tree search algorithms. It can be activated even for the GUI (the output's in the terminal window), from command line option 'd'. Below is the offending tree: suggest: toss: alpha_beta_ord ev game, timer started... [   ] "   . P Q   . P .   +Q . . " [   ] "   . P Q   . P .   Q +P . ", leaf 1 heur: 1. [   ] "   . P Q   . P .   Q . +P ", leaf 1 heur: 0.888888888889 [   ] "   . P Q   +P P .   Q . . ", leaf 1 heur: 0.777777777778 [   ] "   . P Q   . P +P   Q . . ", leaf 1 heur: 0.777777777778 [   ] "   +P P Q   . P .   Q . . ", leaf 1 heur: 0.777777777778 , best 0 maximax: 1.. [   ] "   . P Q   . P .   . +Q . " [   ] "   . P Q   . P .   +P Q . ", leaf 1 heur: 0.222222222222 [   ] "   . P Q   . P .   . Q +P ", leaf 1 heur: 0.555555555556 [   ] "   . P Q   +P P .   . Q . ", leaf 1 heur: 0.444444444444 [   ] "   . P Q   . P +P   . Q . ", leaf 1 heur: 0.444444444444 [   ] "   +P P Q   . P .   . Q . ", leaf 1 heur: 0.444444444444 , best 0 maximax: 0.555555555556. [   ] "   . P Q   . P .   . . +Q " [   ] "   . P Q   . P .   +P . Q ", leaf 1 heur: 0.222222222222 [   ] "   . P Q   . P .   . +P Q ", leaf 1 heur: 0.666666666667 , best cut 0 maximax: 0.666666666667. [   ] "   . P Q   +Q P .   . . . " [   ] "   . P Q   Q P .   +P . . ", leaf 1 heur: 0.555555555556 , best cut 0 maximax: 0.555555555556. [   ] "   . P Q   . P +Q   . . . " [   ] "   . P Q   . P Q   +P . . ", leaf 1 heur: 0.333333333333 [   ] "   . P Q   . P Q   . +P . ", leaf 1 heur: 0.777777777778 , best cut 0 maximax: 0.777777777778. [   ] "   +Q P Q   . P .   . . . " [   ] "   Q P Q   . P .   +P . . ", leaf 1 heur: 0.555555555556 , best cut 0 maximax: 0.555555555556. 22 nodes, 133 size, 0.072004 elapsed time moving to state [   ] " +Q P Q . P . . . . " suggest: pos 5 
From: Lukasz Stafiniak <lukstafi@gm...>  20101123 09:02:07

Gr! I'm sorry. The bug is that the cutoff value is assumed as the value of the pruned subtree. Then some pruned subtrees, which can include the worst subtree, have the same value as the best subtree and one of them is selected randomly. I'm sorry to have let it slip through for so long! 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101120 17:55:14

> My is a rather straightforward implementation of an idea, it has no > caching at all. (It has "locality benefits" in that more recent > variables are earlier in the substitution list.) I did not play till the end  try to run the test yourself. It is not good when even getting the moves takes a few seconds and a hint at depth 2 takes almost an hour. But this must be due to computing WinW / WinB many many times  if you could cache just this toplevel conjunct it should help a lot, or am I really wrong on this one? But there is another problem more pressing for me now. I tried to play Breakthrough and it played very stupid, but even worse  at the end there are no payoffs, i.e. both are zero. See the attached toss file  game ends, but only zeros! I still do not know where the problem is on this one. Lukasz 
From: Lukasz Stafiniak <lukstafi@gm...>  20101120 17:34:49

On Sat, Nov 20, 2010 at 5:36 PM, Lukasz Kaiser <lukaszkaiser@...> wrote: >> Perhaps it's ok to have high adv_ratio. It would be difficult to find >> counterexamples, since low adv_ratio just increases exploration... Ouch, I used a very wrong word here. Low adv_ratio increases "diversification". > One bigger problem is that performance degrades seriously when > more pieces are on the board. Attached is a good test position in > which there is only one good move. It made this move at depth 2 > so it is nice, but it took quite long to compute  try it yourself. And > you can add this test for the future to always be sure just in case. > Is it possible that we could cache a bit more in the solver to make > things faster? My was caching too much, but perhaps your is not > caching enough and recomputing too much with full board? My is a rather straightforward implementation of an idea, it has no caching at all. (It has "locality benefits" in that more recent variables are earlier in the substitution list.) 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101120 16:36:51

> Perhaps it's ok to have high adv_ratio. It would be difficult to find > counterexamples, since low adv_ratio just increases exploration... It seems to be quite ok with adv_ratio 5. I'm playing at depth 2 and it will most probably end undecided, but all moves were quite ok (except for the second one, but openings are of course another story). One bigger problem is that performance degrades seriously when more pieces are on the board. Attached is a good test position in which there is only one good move. It made this move at depth 2 so it is nice, but it took quite long to compute  try it yourself. And you can add this test for the future to always be sure just in case. Is it possible that we could cache a bit more in the solver to make things faster? My was caching too much, but perhaps your is not caching enough and recomputing too much with full board? Lukasz 
From: Lukasz Stafiniak <lukstafi@gm...>  20101120 13:50:42

On Sat, Nov 20, 2010 at 11:12 AM, Lukasz Stafiniak <lukstafi@...> wrote: > Thanks! I've bumped adv_ratio to 5 (for monotonic games that means the > number of pieces in a line is raised to 5th power) which solves this > problem, but ultimately it is a tree search issue. It wouldn't happen > if alphabeta had special treatment for terminal subtrees Perhaps it's ok to have high adv_ratio. It would be difficult to find counterexamples, since low adv_ratio just increases exploration... 
From: Lukasz Stafiniak <lukstafi@gm...>  20101120 10:13:22

Thanks! I've bumped adv_ratio to 5 (for monotonic games that means the number of pieces in a line is raised to 5th power) which solves this problem, but ultimately it is a tree search issue. It wouldn't happen if alphabeta had special treatment for terminal subtrees (I can add it but the initial idea was to keep alphabeta simple). UCT would also be smarter here, obviously. On Sat, Nov 20, 2010 at 12:15 AM, Lukasz Kaiser <lukaszkaiser@...> wrote: > I played Gomoku against Gridlock again today at depth 2 and 4. > It indeed plays much better, but there is a stupid mistake at the > end. When there is a single move preventing loss, it makes other > things regardless. Appears both at depth 2 and 4. Test attached. > > Lukasz > 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101119 23:16:05

I played Gomoku against Gridlock again today at depth 2 and 4. It indeed plays much better, but there is a stupid mistake at the end. When there is a single move preventing loss, it makes other things regardless. Appears both at depth 2 and 4. Test attached. Lukasz 
From: Lukasz Stafiniak <lukstafi@gm...>  20101115 23:21:08

On Tue, Nov 16, 2010 at 12:08 AM, Lukasz Kaiser <lukaszkaiser@...> wrote: >> (Just a margin note to casual readers: heuristics do depend on >> location even now, but not in a smart way; they should better not >> depend on locations in the way they do currently, that is just being >> generated from the payoff of the location, ignoring payoffs in other >> locations.) > > Thanks for the note! I realize the caveat in the note is yet another reason to do the roundingup! (But it is still very suboptimal in the general case, we've been discussing already that a heuristic could for example be generated from a sum of payoffs guarded by conditions on rules that lead to their locations). > By the way: I just made the first > en passant capture in Toss chess, so we are on track :). That's great :) It motivates me to be less lazy! (It sometimes takes me _a lot_ of time to dive into the code after a break, even if it's short.) 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101115 23:09:16

> (Just a margin note to casual readers: heuristics do depend on > location even now, but not in a smart way; they should better not > depend on locations in the way they do currently, that is just being > generated from the payoff of the location, ignoring payoffs in other > locations.) Thanks for the note! By the way: I just made the first en passant capture in Toss chess, so we are on track :). Lukasz 
From: Lukasz Stafiniak <lukstafi@gm...>  20101115 23:04:30

On Mon, Nov 15, 2010 at 11:59 PM, Lukasz Kaiser <lukaszkaiser@...> wrote: > > Yes, I think locationbased is ok. One day we could even think > about stopping at different locations (odd ply) but then using > different heuristics, dependent on the location. But I think that > enforcing the same location is a good start! (Just a margin note to casual readers: heuristics do depend on location even now, but not in a smart way; they should better not depend on locations in the way they do currently, that is just being generated from the payoff of the location, ignoring payoffs in other locations.) 
From: Lukasz Kaiser <lukaszkaiser@gm...>  20101115 22:59:55

> ply depth. But are you convinced that locationbased "general moves" > (I'd rather use the word "turn" because "move" sounds like "rule > application" to me) are better than playerbased "general moves"? Yes, I think locationbased is ok. One day we could even think about stopping at different locations (odd ply) but then using different heuristics, dependent on the location. But I think that enforcing the same location is a good start! Lukasz 